BilQC | Selman Ipek | Improved simulation of stabilizer circuits

Abstract: The Gottesman-Knill theorem establishes that stabilizer circuits (defined previously) can be simulated efficiently on a classical computer. In arXiv:quant-ph/0406196 Aaronson and Gottesman improve the efficiency of the classical simulation and demonstrate that stabilizer circuits are (most likely) not universal for classical computation. Circuits that are otherwise stabilizer with the exception of a small number of non-Clifford gates are also considered and the complexity of such circuits scales exponentially with the number of non-Clifford gates.