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
    Commented Sep 22, 2022 at 11:36
  • $\begingroup$ Thank you for that example! In this case, it seems like you already know the superposition state beforehand, which is since it's polynomial is size makes sense. A follow up question from me then: let's say I started with a computational basis state, and then had a circuit to create an unknown state of a superposition of just polynomially many computational basis states, and then added classical gates after, would this necessarily be efficiently simulable? $\endgroup$ Commented Nov 3, 2022 at 12:35
  • $\begingroup$ I think yes, because you can just feed-forward your computational basis state into this circuit and branch on the superpositions that get created. You will still only need to store a polynomial number of branches, so it is efficient. $\endgroup$
    – John
    Commented Nov 4, 2022 at 13:18
  • 1
    $\begingroup$ If you are interested in this question, I would suggest you look at the literature on stabilizer decompositions and the resource of stabilizer extent, as this is where I got the observation from. For instance, using this theory you can show that a stabiliser circuit with a logarithmic amount of T gates has this property of being decomposable into a polynomial number of stabiliser states, and hence is efficiently simulable. $\endgroup$
    – John
    Commented Nov 4, 2022 at 13:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.