Efficient Classical Simulation of Quantum Circuits beyond the Stabilizer Formalism

The Gottesmann-Knill theorem states that stabilizer states and operations can be simulated efficiently on a classical computer. Using quasi-probability distributions over stabilizer states and operations, a 2017 algorithm by Bennink et al. achieves efficient simulation of mixed states and quantum channels whenever the distribution is non-negative. We extend their algorithm to arbitrary quasi-probability representations that need not be restricted by the stabilizer formalism. This opens the possibility for efficient classical simulation of larger regions of quantum mechanics. Since negative quasi-probability is a manifestation of quantum contextuality, this analysis highlights a connection between efficient classical simulation and non-contextuality.