Igor Markov, University of Michigan
Abstract
The feasibility of quantum computation in laboratory experiments will increasingly depend on software tools that help bridge the gap between physics, algorithms and real-world computing requirements. Specifically, simulation-based studies are crucial for designing fault-tolerant quantum architectures, circuits and algorithms. Generic quantum-circuit simulation appears intractable for conventional computers. However, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently. Such circuits play a key role in the design and implementation of quantum error-correction (QEC) and are composed exclusively of stabilizer gates (Hadamard, Phase and CNOT). Aaronson and Gottesman generalized stabilizer-circuit simulation to additionally handle a small number of non-stabilizer gates, e.g., circuits enriched with QEC. We develop new, more efficient algorithms for such beyond-stabilizer simulation using superpositions of stabilizer states. Our technique offers more compact storage than the density-matrix approach by Aaronson and Gottesman but requires additional algorithms to maintain the global phase of each state in the superposition. Such superpositions can be restructured during simulation to improve runtime and memory usage. The resulting algorithms are practical enough to be implemented in C++, and outperform previously existing software for simulating quantum circuits.