7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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) $\endgroup$ – Mauricio May 25 at 10:15
  • 1
    $\begingroup$ 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. $\endgroup$ – DaftWullie May 25 at 10:18
  • 1
    $\begingroup$ 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? $\endgroup$ – Weather Report May 25 at 11:45
  • 1
    $\begingroup$ @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. $\endgroup$ – DaftWullie May 25 at 12:45
  • 1
    $\begingroup$ @DaftWullie no complexity-theoretic assumption needed. The group generated by CNOT and Hadamard is simply finite. $\endgroup$ – Markus Heinrich May 26 at 12:53
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.