# Is it possible to make a Toffoli gate using only CNOTS and ancillas?

I have tried to make a Toffoli gate using only CNOTs and some ancilla qubits but I do not get the unitary. It seems it is not possible without additional gates? What could I do to prove it?

I have tried something like CNOT(c0,a0),CNOT(c1,a0),X(a0),CNOT(a0,t) (and then reversing the whole operation for the ancilla) , where c are the control qubits, a are the ancilla qubits and t is the target. This method does not work because when c0 and c1 are both 0 then it also changes the target qubit.

I know that you can generalize Toffoli to $$n$$ qubits using normal Toffolis and ancillas.

No this is not possible. One argument is the following:

Toffoli + Hadamard are universal for quantum computation, so if you can make Toffoli from controlled-not then controlled-not + Hadamard would be universal.

However, we know (Gottesman-Knill theorem) that the effects of controlled-not + Hadamard can be classically simulated, and so if we believe that there are algorithms that have a (more than polynomial) quantum speedup, it must be that controlled-not + Hadamard is not universal.

Update: I like Markus Heinrich's comment because it does simplify this specific argument. It helps us to focus more on the key properties of my original statement. We know that Hadamard+Toffoli is universal for quantum computation. That means, at least within some big subspace, and, specifically, starting from the all-0 state, any unitary can be created. On the other hand, the Gottesman-Knill theorem tells us that the Clifford gates (including c-NOT and Hadamard) form a finite group when acting on the input of all-0s. As such, they cannot recreate the action of Toffoli.

• Thanks that makes sense. Do you know if I could I reduce the number of cnots to make a Toffoli using ancillas and single qubit gates? (probably I should open another question for that) May 25, 2021 at 10:15
• I believe you don't get any improvement over the standard construction. There are papers such as this: arxiv.org/abs/0803.2316 which claim to prove that 6 cNOTs is the minimum. I assume that applies to the case with ancillas as well, but have not checked. May 25, 2021 at 10:18
• It seems that you argument uses heavy machinery and unproven complexity-theoretic assumptions:) There should be a way to settle the problem in simple terms, should not it? May 25, 2021 at 11:45
• @MarkS I also agree that it's a purely classical question as posed. Presumably my argument could be reduced to a classical one - Toffoli is universal for reversible classical computation. I presume (although I wouldn't know off the top of my head how to prove it) that controlled-not is not universal for reversible classical computation. May 25, 2021 at 12:45
• @DaftWullie no complexity-theoretic assumption needed. The group generated by CNOT and Hadamard is simply finite. May 26, 2021 at 12:53

Inspired by the discussion in @DaftWullie's answer above, note that we can construct a lattice/Hasse diagram of all classes of Boolean functions realizable/synthesizable with various gate sets. Such a lattice will indicate whether a given gate set is universal for the given class.

For classical (not necessarily reversible) computation, Emil Post did this in the 40's. Thus we have, for example, the well-known results that the [0, 1, ∧, ∨] are only able to synthesize "monotone" functions.

Apparently the same question went mostly unasked throughout most of the history of reversible computation; nonetheless, not too long ago Aaronson, Grier, and Schaeffer were able to build such a lattice. Their full classification allows for ancillas, and clocks in at 68 pages, but their Theorem 3 separates the class of functions realizable with CNOTs from those realizable with Toffoli gates.

Briefly and from a quick perusal of the above paper, CNOT gates (even with extra ancillas) are affine over $$\mathbb{F}_2$$, while CCNOT gates (Toffoli gates) are not. Thus CNOT gates alone cannot synthesize non-affine functions, while Toffoli gates can.

Being affine means that, for a circuit $$G$$ (including ancillas initialized arbitrarily to $$0$$ or $$1$$ if necessary), then there exists an invertible matrix $$A\in\mathbb{F}_2^{k\times k}$$ and a vector $$b$$ such that $$G(x)=Ax\otimes b$$ for all $$x$$.

If your inputs are bits $$b_1, ..., b_n$$ and you can only use NOT gates and CNOT gates, then your outputs are always parities. Your outputs are always of the form $$c_0 + \sum_{k=1}^n c_k b_k$$ where $$c_k \in \{0, 1\}$$ are bits you can pick and also all arithmetic is modulo 2. For example, you can output $$\lnot b_1$$ and you can output $$b_1 + b_3$$ but you can't output $$b_1 \cdot b_3$$ or $$b_1 \cdot b_3 + b_2$$.

With a Toffoli gate, you can easily output a bit equal to $$b_1 \cdot b_3 + b_2$$. Just perform a Toffoli controlled by bits 1 and 3 targeting bit 2. Since the Toffoli gate enables you to do something you can't do with NOTs and CNOTs, you can't build a Toffoli out of NOTs and CNOTs.