Efficient classical simulation of Clifford circuits with nonstabilizer input states

Understand

We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states.

• First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the $l_1$ norm, of a large fraction of Clifford circuits.
• The running time of our algorithm decreases as the inputs become more mixed.
• Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured.