Simulation of quantum circuits by low-rank stabilizer decompositions

By Sergey Bravyi, Dan E. Browne, Padraic Calpin, Earl T. Campbell, David Gosset, Mark Howard. Quantum, 2018

437 citations recorded by the source corpus.

Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of stabilizerrank, which for a pure state ψ is defined to be the smallest integer χ such that ψ is a superposition of χ stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of χ∼106 stabilizer states and sample from the full n-bit output distribution, improving on previous simulations which used ∼103 stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 T gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/2c626f454070acc8860813fdc72292c617ad3e92

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Evidence for the utility of quantum computing before fault tolerance (2023, methodology): “On the other hand, the classical simulations may also be improved by methods besides the pure-state tensor networks considered here, such as Heisenberg operator evolution methods, which have recently been applied to non-Clifford simulations 38 .”
Logical quantum processor based on reconfigurable atom arrays (2023, background): “Simulation of such logical circuits is challenging because of the high connectivity (rendering tensor networks inefficient) and large numbers of non-Cliffords 50 .”
The future of quantum computing with superconducting qubits (2022, background): “This is far beyond the limit of existing classical algorithms that can simulate Cliﬀord+ T circuits with about 50 T -gates 84,85 .”
Many-Body Quantum Magic (2020, methodology): “• Stabilizer extent [7]: The stabilizer extent for pure state ψ is defined as ξ(ψ) :=”