Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

Question

The Gottesman-Knill theore states (from Nielsen and Chuang)

Suppose a quantum computation is performed which involves only the following elements: state preparations in the computational basis, Hadamard gates, phase gates, controlled-NOT gates, Pauli gates, and measurements of observables in the Pauli group (which includes measurement in the computational basis as a special case), together with the possibility of classical control conditioned on the outcome of such measurements. Such a computation may be efficiently simulated on a classical computer.

How does this not render quantum computation largely useless? I understand that the Toffoli gate cannot be generated by the Clifford gates, but nonetheless there are important algorithms that do not use the Toffoli gate, for instance Shor's algorithm, Grover's algorithm, quantum teleportation and I'm sure many more. It seems to me that due to this theorem, we should be able to factor numbers in polynomial time using a classical computer, by simulating Shor's algorithm, or order finding specifically, yet Shor's algorithm is celebrated as one of the most important quantum advantages, so I guess this is not possible, but why?

Answer 1

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I think of as a phase gate, which can have an arbitrary phase (but they have very specifically introduced their terminology about 3 pages earlier). This is a key difference as it means that the Toffoli gate that is not the only one missing from this gate set. Most single-qubit gates are also missing. The most commonly cited example is the $T=\sqrt{S}$ gate, $$ T=\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{i\pi/4} \end{array}\right). $$ Any efficient quantum algorithm (which doesn't have an efficient classical counterpart), such as Shor's algorithm, include a gate that is not in this set of gates. For example, Shor's algorithm includes the quantum Fourier transform (in that specific context, you'd probably use the semi-classical version) for which you have to implement phase gates with phases $\pi/4$, $\pi/8$, $\pi/16$... whose implementation cannot be efficiently simulated. (In the standard, not semi-classical, version, you need controlled-phase-gates with identical phases).

However, a comment about a couple of your other examples is warranted:

• quantum teleportation: this is a specific method that achieves a particular quantum task using, and providing, specific resources (bell pair+2 bits of classical communication=transmission of one unknown qubit state). You might be able to simulate it on a classical computer (if you had a good description of the input state), but the resources would be different. This is not a question about scaling properties of an algorithm, so the basic argument of the Gottesman-Knill theorem is irrelevant.

• Quantum search. Quantum search generally does include Toffoli gates. However, the point that I wanted to make here is that quantum search does not exhibit an exponential speed-up, but only a polynomial speed-up. So there's no problem doing a classical simulation of it with polynomial overhead. The Gottesman-Knill theorem is only relevant to rule out the possibility of an exponential (or, at least, super-polynomial) speedup over the classical case.

Answer 2

Another way to think about this: To simulate what goes on in a quantum computer we have to do a lot of matrix math using $(2^N \times 2^N)$ matrices$^1$, and the action of (most) of the clifford gates can be actually be accomplished by applying some non-linear, low complexity matrix operation instead of a matrix multiplication.

For example, the Pauli-X gate, CNOT, and SWAP gates are both permutation matrices. If you think carefully about which qubits they act on, you don't have to do matrix math at all, you just copy and/or shuffle around the amplitudes of $|\psi \rangle$ in a clever way. Similarly with Pauli-Z - you just negate a subset of your amplitudes and sidestep the matrix math.

But quantum computing is about more interesting operations than permutations, and the effects of gates involving rotation ($R_x$, $R_y$, $R_z$) and ugly phases ($T$) don't have nice shortcuts. And for whatever we can't efficiently simulate, we expect the quantum computer to have an advantage.

---

1. This is not the most efficient method, but the operations I'm describing can often perform multiplication by single-qubit clifford gate saturating the $\mathcal{O}(2^N)$ lower bound on complexity for computing amplitudes of an $N$-qubit state, making these methods better than or equal to any other method available.