Improved Graph Formalism for Quantum Circuit Simulation
arXiv:2109.10210 · doi:10.1103/PhysRevA.105.022432
Abstract
Improving the simulation of quantum circuits on classical computers is important for understanding quantum advantage and increasing development speed. In this paper, we explore a new way to express stabilizer states and further improve the speed of simulating stabilizer circuits with a current existing approach. First, we discover a unique and elegant canonical form for stabilizer states based on graph states to better represent stabilizer states and show how to efficiently simplify stabilizer states to canonical form. Second, we develop an improved algorithm for graph state stabilizer simulation and establish limitations on reducing the quadratic runtime of applying controlled-Pauli gates. We do so by creating a simpler formula for combining two Pauli-related stabilizer states into one. Third, to better understand the linear dependence of stabilizer states, we characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli algorithm, we improve runtime for inner product computation from to where is the maximum degree of the graph.
arXiv comment16 pages, 2 figures
References in corpus (12)
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Multi-party entanglement in graph states
- A Theory of Fault-Tolerant Quantum Computation
- Stim: a fast stabilizer circuit simulator
- Graphical description of the action of local Clifford transformations on graph states
- Trading classical and quantum computational resources
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Fast simulation of stabilizer circuits using a graph state representation
- Graphical description of the action of Clifford operators on stabilizer states
- Efficient Inner-product Algorithm for Stabilizer States
- Stabilizer states and local realism