The Gottesman-Knill theorem states that the following process is efficiently simulatable on a classical computer:

  1. start of with a set of qubits in a computational basis
  2. apply any amount of $H, S$ and $CNOT$ gates in any order
  3. measure all the qubits in the $Z$ basis

The states created after step 2) are known as "stabilizer states". My question is, are there multi-qubit states which are non-stabilizer states but that are also as efficient to classically simulate as the way stabilizer states are simulatable in the above procedure?

  • 4
    $\begingroup$ If you restrict your gate set to just classical ones (NOT, CNOT, Toffoli), then if your input state is a superposition of just polynomially many computational basis states, you can efficiently simulate this circuit by just sampling from this superposition modified by the classical gates. So for instance, the W-state would be 'efficiently simulable' in this setting. $\endgroup$
    – John
    Sep 22 at 11:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy