LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
arXiv:2108.00931 · doi:10.22331/q-2023-09-11-1108
Abstract
Efficient methods for the representation and simulation of quantum states and quantum operations are crucial for the optimization of quantum circuits. Decision diagrams (DDs), a well-studied data structure originally used to represent Boolean functions, have proven capable of capturing relevant aspects of quantum systems, but their limits are not well understood. In this work, we investigate and bridge the gap between existing DD-based structures and the stabilizer formalism, an important tool for simulating quantum circuits in the tractable regime. We first show that although DDs were suggested to succinctly represent important quantum states, they actually require exponential space for certain stabilizer states. To remedy this, we introduce a more powerful decision diagram variant, called Local Invertible Map-DD (LIMDD). We prove that the set of quantum states represented by poly-sized LIMDDs strictly contains the union of stabilizer states and other decision diagram variants. Finally, there exist circuits which LIMDDs can efficiently simulate, while their output states cannot be succinctly represented by two state-of-the-art simulation paradigms: the stabilizer decomposition techniques for Clifford + circuits and Matrix-Product States. By uniting two successful approaches, LIMDDs thus pave the way for fundamentally more powerful solutions for simulation and analysis of quantum computing.
References in corpus (23)
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Improved Simulation of Stabilizer Circuits
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Trading classical and quantum computational resources
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Matchgates and classical simulation of quantum circuits
- Reducing T-count with the ZX-calculus
- Classical simulation versus universality in measurement based quantum computation
- Entanglement on mixed stabiliser states--I: Normal Forms and Reduction Procedures
- Anonymous transmission in a noisy quantum network using the W state
- Quantum secure communication scheme with W state
- Local unitary versus local Clifford equivalence of stabilizer states
- Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
- Computational power of matchgates with supplementary resources
- As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation
- Symmetries and entanglement of stabilizer states
- Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
- Efficient Inner-product Algorithm for Stabilizer States
- Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
- Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
- Approximate Equivalence Checking of Noisy Quantum Circuits
- Quantum Circuit Designs of Integer Division Optimizing T-count and T-depth
- The Parameterized Complexity of Quantum Verification