GK Extension Zoo: Tracking Extensions of Gottesman-Knill Theorem

[Fe-r-oz]

I think we should keep track of all the relevant works that extend the Gottesman-Knill theorem (preference: qubits, stabilizer formalism). Some may be highly relevant, others might offer low-hanging fruit, and some could simply be interesting to read.

In the first paper, there is interesting discussion about Clifford Normal Form that apparently 'highlights computational 'weakness' of the Clifford circuits'. The Clifford Normal Form, extends GK theorem to encompass full probabilistic classical computation, so it seems different from Ted's work who put emphasis on 'strong simulation' rather than the former, which is about 'weak simulation'. Hopefully, this sounds interesting.

• Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond
• Classical simulation complexity of extended Clifford circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates with complete procedure in [Feature]: two classical simulation algorithms for Clifford+T circuits #324. Also: Computing the quantity `⟨ψ|Π|φ⟩` #325
• Simulation of quantum circuits by low-rank stabilizer decompositions
• On The Stabilizer Formalism And Its Generalization
• A linearized stabilizer formalism for systems of finite dimension
• Noisy Stabilizer Formalism