# Are there non-stabilizer multi-qubit states that are easy to simulate?

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?

• 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.
– John
Commented Sep 22, 2022 at 11:36
• 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? Commented Nov 3, 2022 at 12:35
• 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.
– John
Commented Nov 4, 2022 at 13:18
• 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.
– John
Commented Nov 4, 2022 at 13:19