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

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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.