5
$\begingroup$

I’m trying to understand the relationship between the Toffoli gate, Clifford gates, and the classical simulation of quantum circuits.

-I know that the Toffoli gate is universal for classical computation, since it can simulate gates like NAND.
-I’m aware of the Knill-Gottesman theorem, which states that quantum circuits using only Clifford gates can be efficiently (which I interpret as "in polynomial time") simulated by classical computers.
-I also know that the Clifford set={Hadamard, CNOT, S} is not universal for quantum computation. Additionally, I understand that the Toffoli gate is non-Clifford and that the combination of Clifford gates + Toffoli forms a universal set for quantum computation (in the sense that any quantum circuit can be approximated with these gates).

Given this, my question is:
Since the Toffoli gate can simulate any classical computation, and classical computation can simulate any Clifford-only quantum circuit (via the Knill-Gottesman theorem), wouldn’t it seem that the Toffoli gate alone could simulate any circuit composed of Clifford gates + Toffoli? This conclusion doesn’t make sense, as I know the Toffoli gate by itself is not universal for quantum computation (it requires the Hadamard gate to achieve universality, for many good reasons such as superposition).

What am I getting wrong?

$\endgroup$

2 Answers 2

4
$\begingroup$

First, efficiency is important here. You can simulate any quantum circuit on a big enough classical computer, it just happens that the size of the required classical computer is exponential in the number of non-Clifford gates in it.

You cannot equate "being universal for" and "can simulate" when considering different computation models.

When you simulate a Clifford circuit with a classical computer, you do not end up building a quantum gate. Instead, you are able to get as much information from the circuit in the classical computation model as you could get from the equivalent quantum circuit (through application to stabilizer states and measurements). Gottesman-Knill essentially tells you that there is little classical advantage to get from Clifford quantum circuits if you have access to a classical computer.

When you decompose (and approximate) an arbitrary quantum gate using {Clifford + Toffoli}, you build a quantum circuit. Your circuit will behave (almost) exactly like the initial gate and this within the same quantum computation model.

Said differently:

"A is universal for B" $\to$ "A is part of B and anything from B can be done with A"

"C can simulate D" $\to$ "From the perspective of C, a black box from D can be emulated with elements from C"


A classical Toffoli gate is universal for reversible computing and in turn for classical computing. A quantum Toffoli gate can simulate a classical Toffoli gate, if given only $|0\rangle$ and $|1\rangle$ inputs.

This means you can build a quantum circuit that will mimic the behaviour of a classical computer only from quantum Toffoli gates, provided you give basis states as inputs.

If you choose this ersatz of classical computer to simulate some Clifford circuits (let's say a Hadamard gate), you can then have access to {quantum Toffoli gates + classical information that can be extracted from said circuit} i.e. some quantum Toffoli gates and the fact that the quantum circuit outputs $|+\rangle$ on $|0\rangle$ and $|-\rangle$ on $|1\rangle$.

This is very different from {quantum Toffoli + Hadamard} because you cannot apply any Hadamard gate, at most you can switch some qubits you know are in a $Z$-basis state to a $X$-basis state. Indeed, the classical simulation of the circuit is bound to take a basis-state input, so you cannot use it for an all-purpose Hadamard gate. Therefore, you cannot make interact the quantum Toffoli with the simulated Hadamard, as the simulation only transcribe the classical behaviour of the Hadamard gate

To sum up, the quantum Toffoli gate:

  • can simulate any classical computation (as it can simulate a classical Toffoli gate if given basis-state inputs)
  • can (relatively) efficiently simulate the classical behaviour of any Clifford circuit
  • can simulate the classical behaviour of any quantum circuit (although very poorly to the best of our knowledge)
  • cannot be universal for quantum computing, because it cannot implement a Hadamard gate.
$\endgroup$
3
$\begingroup$

not really an answer but too long for a comment


This is an interesting question that I was initially going to dismiss. The question is something like "Toffoli taught us that the CCNOT gate is universal for classical computation, while Gottesman-Knill teaches that the Clifford gates are classically simulable, so where is the fault in the conclusion that we should be able to use the CCNOT gate alone to simulate Clifford+CCNOT, hence achieving fully enabled quantum algorithms with CCNOT alone?"

But we also know that we can't trisect an angle or square the circle with a compass and straight-edge (even though Archimedes taught us that we can get arbitrarily close). We can also do a lot of the first five chapters of Euclid with a neusis alone. However, we can trisect the angle with a neusis, but we need a compass to draw a circle first. So, a neusis + compass is much more powerful than a compass alone or a neusis alone, much as Clifford+Toffoli is much (much) more powerful than Clifford alone or Toffoli alone.

(This isn't a perfect analogy though, and I'm not fully satisfied with it as it's not getting to the heart of the matter.)

$\endgroup$
1
  • 1
    $\begingroup$ Maybe your analogy can be completed by saying that one can sketch the principle of a neusis with a compass and straight-edge, without being able to perform a neusis construction. $\endgroup$
    – AG47
    Commented Nov 26 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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