  The Gottesman-Knill theorem asserts that a quantum circuit composed of
Clifford gates can be efficiently simulated on a classical computer. Here we
revisit this theorem and extend it to quantum circuits composed of Clifford and
T gates, where T is the single-qubit 45-degree phase shift. We assume that the
circuit outputs a bit string x obtained by measuring some subset of w qubits.
Two simulation tasks are considered: (1) computing the probability of a given
output x, and (2) sampling x from the output probability distribution. It is
shown that these tasks can be solved on a classical computer in time
$poly(n,m)+2^{0.5 t} t^3$ and $poly(n,m)+2^{0.23 t} t^3 w^3$ respectively,
where t is the number of T-gates, m is the total number of gates, and n is the
number of qubits. The proposed simulation algorithms may serve as a
verification tool for medium-size quantum computations that are dominated by
Clifford gates. The main ingredient of both algorithms is a subroutine for
approximating the norm of an n-qubit state which is given as a linear
combination of $\chi$ stabilizer states. The subroutine runs in time $\chi n^3
\epsilon^{-2}$, where $\epsilon$ is the relative error. We also develop
techniques for approximating tensor products of "magic states" by linear
combinations of stabilizer states. To demonstrate the power of the new
simulation methods, we performed a classical simulation of a hidden shift
quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50
T-gates.
