Optimal decompositions of some standard multi-qubit gates

Question

To have a concrete example in mind: 3-qubit Toffoli gate can be decomposed into 6 $CNOT$s as shown here

I believe this is the most economic decomposition in terms of the number of $CNOT$s used. My questions are:

1. Is it proven that it is not possible to do better than with 6 $CNOT$s?
2. Could the decomposition be improved if ancilla qubits are allowed?

OK, and a 3-qubit Toffoli is really just an example, I would be interested in any results along these lines concerning some standard multi-qubits gates, say $n-$Toffoli, other multi-controlled gates etc.

Answer 1

As detailed in The simplified Toffoli gate implementation by Margolus is optimal, a construction of the simplified Toffoli (which introduces for some relative phase) cannot be constructed with fewer than $3$ controlled-not operations. Also mentioned in that paper, it is conjectured that the Toffoli gate cannot be implemented with less than six controlled-nots. Therefore, the decomposition you included in your question for the normal Toffoli is optimal.

The paper Synthesis of Quantum Logic Circuits gives methods to create general unitaries. For general unitaries, it has been shown that an $n$-qubit unitary requires $\lceil\frac{1}{4}(4^n-3n-1)\rceil$ controlled-nots. So, since your question is concerned with controlled unitaries, this bound is probably lower.

Regarding ancilla, you may find this blogpost by Craig Gidney where some techniques for constructing $C^nNOT$ gates are given. The goal of the series is to not use ancilla qubits at the end, but this first post gives some useful insights into using them. Later in the series of posts, the ancilla qubits are removed and replaced by phase shift gates. I recommend you reading the three posts about the topic.

Answer 2

I was pointed to this very nice paper On the CNOT-cost of TOFFOLI gates . The issue appears to be much more complicated than I thought. Apparently there are theses yet to be written on the decomposition of Toffoli into $CNOT$s.

First, due to identity $HXH=Z$ decompositions into $CNOT$s and $CZ$s can be translated into each others. Similarly, decomposing $n$-qubit Toffoli can be reduced to decomposing $n$-qubit controlled-$Z$ gate, which might be technically simpler as it is symmetric and diagonal.

The main result derived in the paper is that the cost of a $Z$ gate with $n-1$ controls satisfies $|C^{(n-1)}Z|_{CZ}\ge 2n$, which implies the same bound for decomposition of an $n$-qubit Toffoli into $CNOT$s: $|C^{(n-1)}X|_{CX}\ge 2n$. For $n=3$ this gives 6 $CNOT$ gates and there is a known decomposition with this amount of gates (see OP), so for $n=3$ this is also the optimal result. Already for $n=4$ the bound appears quite weak saying that one needs at least $8$ gates, but the best known decomposition (which is probably optimal) requires 14 gates.

The paper also proves that for $n=3$ adding any amount of ancilla qubits can not lower the cost. For $n\ge4$ ancilla probably can help, but coming up with explicit examples seems to be surprisingly difficult.

I do not know if there were improvements to the results of the paper, I would be interested to learn that.