7

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.

ryanhill1
  • 2,493
  • 1
  • 9
  • 37
Mauricio
  • 2,296
  • 3
  • 25

3 Answers3

8

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.

DaftWullie
  • 57,689
  • 3
  • 46
  • 124
  • 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) – Mauricio May 25 '21 at 10:15
  • 1
    I believe you don't get any improvement over the standard construction. There are papers such as this: https://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. – DaftWullie May 25 '21 at 10:18
  • Oh that make sense. Thanks again! – Mauricio May 25 '21 at 10:19
  • 1
    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? – Nikita Nemkov May 25 '21 at 11:45
  • I like @Weather_Report’s question. The OP’s problem is a question about a purely classical synthesis. Maybe you could show it by trying to prove that it could be possible, failing, adding another ancilla, failing, and then recursing. – Mark Spinelli May 25 '21 at 12:24
  • @WeatherReport I agree that complexity-theoretic machinery should be unnecessary, but it is a relatively simple argument to make. You might rather rely on proofs such as https://arxiv.org/abs/1308.4134 which explicitly calculate the minimum number of T gates when using clifford + T in order to create Toffoli (the point being it's non-zero) – DaftWullie May 25 '21 at 12:43
  • 1
    @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. – DaftWullie May 25 '21 at 12:45
  • That said (re complexity theoretic treatment), that paper explicitly excludes ancillas. – DaftWullie May 25 '21 at 12:51
  • The original answer to my question above is simple enough. for my second question see corollary 34: https://arxiv.org/pdf/0803.2316.pdf – Mauricio May 25 '21 at 13:45
  • 1
    @DaftWullie no complexity-theoretic assumption needed. The group generated by CNOT and Hadamard is simply finite. – Markus Heinrich May 26 '21 at 12:53
4

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

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
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.

Craig Gidney
  • 36,389
  • 1
  • 29
  • 95