Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

Understand

We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point.

• We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form).
• This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques.
• The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power.