Duration: 46:18

1,355 views

22

The Gottesman-Knill theorem asserts that a quantum circuit composed of Clifford gates can be efficiently simulated on a classical computer. We revisit this theorem and extend it to quantum circuits in the Clifford+T basis. Our main result is a classical simulation algorithm that allows one to sample from the output distribution of a Clifford+T circuit with a small statistical error. The runtime of our algorithm is polynomial in the number of qubits and the number of Clifford gates in the circuit but exponential in the number of T gates, or T-count. This exponential scaling is sufficiently mild that a classical simulation of Clifford+T circuits with O(100) qubits and T-count up to 50 can be performed on a laptop computer. Our algorithm may serve as a verification tool for medium-size quantum computations that are dominated by Clifford gates. The main ingredient of our algorithm is a new subroutine for approximating the norm of a multi-qubit state which is given as a linear combination of stabilizer states. We also develop new techniques for approximating tensor products of ``magic states" by linear combinations of stabilizer states.