Abstraqt: Analysis of Quantum Circuits via Abstract Stabilizer Simulation
arXiv:2304.00921 · doi:10.22331/q-2023-11-20-1185
Abstract
Stabilizer simulation can efficiently simulate an important class of quantum circuits consisting exclusively of Clifford gates. However, all existing extensions of this simulation to arbitrary quantum circuits including non-Clifford gates suffer from an exponential runtime. To address this challenge, we present a novel approach for efficient stabilizer simulation on arbitrary quantum circuits, at the cost of lost precision. Our key idea is to compress an exponential sum representation of the quantum state into a single abstract summand covering (at least) all occurring summands. This allows us to introduce an abstract stabilizer simulator that efficiently manipulates abstract summands by over-approximating the effect of circuit operations including Clifford gates, non-Clifford gates, and (internal) measurements. We implemented our abstract simulator in a tool called Abstraqt and experimentally demonstrate that Abstraqt can establish circuit properties intractable for existing techniques.
arXiv comment22 pages
References in corpus (14)
- Array Programming with NumPy
- Improved Simulation of Stabilizer Circuits
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Stim: a fast stabilizer circuit simulator
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Towards Large-scale Functional Verification of Universal Quantum Circuits
- PyZX: Large Scale Automated Diagrammatic Reasoning
- A Deductive Verification Framework for Circuit-building Quantum Programs
- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
- Quantum entanglement analysis based on abstract interpretation
- Fast estimation of outcome probabilities for quantum circuits
- Proving Quantum Programs Correct
- Analysis of Quantum Entanglement in Quantum Programs using Stabilizer Formalism