The Gottesman-Knill theorem says that a stabilizer circuit\char22{}that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates\char22{}can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by remov…