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?