Simulation of quantum circuits by low-rank stabilizer decompositions

Abstract

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 stabilizer rank, which for a pure state $\psi$ is defined to be the smallest integer $\chi$ such that $\psi$ is a superposition of $\chi$ 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 $\chi \sim 10^6$ stabilizer states and sample from the full n-bit output distribution, improving on previous simulations which used $\sim 10^3$ 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.

References in corpus (7)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• Massive Parallel Quantum Computer Simulator
• Novel constructions for the fault-tolerant Toffoli gate
• Fast simulation of stabilizer circuits using a graph state representation
• Wigner function negativity and contextuality in quantum computation on rebits
• Catalysis and activation of magic states in fault tolerant architectures
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States

Cited by in corpus (196)

• Logical quantum processor based on reconfigurable atom arrays
• Stim: a fast stabilizer circuit simulator
• The Future of Quantum Computing with Superconducting Qubits
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Information Scrambling in Computationally Complex Quantum Circuits
• Building a fault-tolerant quantum computer using concatenated cat codes
• Stabilizer Rényi entropy
• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Many-body quantum magic
• Quantum advantage with noisy shallow circuits in 3D
• Quantifying nonstabilizerness of matrix product states
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Stabilizer entropies and nonstabilizerness monotones
• Quantifying magic for multi-qubit operations
• Scalable measures of magic resource for quantum computers
• Universal Variational Quantum Computation
• Conformal field theories are magical
• No-Go Theorems for Quantum Resource Purification
• Efficiently computable bounds for magic state distillation
• Stabilizer entropies are monotones for magic-state resource theory
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Nonstabilizerness via matrix product states in the Pauli basis
• Fast quantum circuit cutting with randomized measurements
• Benchmarking one-shot distillation in general quantum resource theories
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Phase transition in magic with random quantum circuits
• Nonstabilizerness determining the hardness of direct fidelity estimation
• ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling
• Efficient quantum algorithms for stabilizer entropies
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• On the statistical complexity of quantum circuits
• Fundamental limitations on distillation of quantum channel resources
• Resource theory of quantum scrambling
• Experimental Demonstration of Logical Magic State Distillation
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Complexity of frustration: a new source of non-local non-stabilizerness
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Improved upper bounds on the stabilizer rank of magic states
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• No-go theorems for quantum resource purification II: new approach and channel theory
• Symmetry-protected sign problem and magic in quantum phases of matter
• Characterization of solvable spin models via graph invariants
• Lower bound for the T count via unitary stabilizer nullity
• Pseudomagic Quantum States
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
• Framework for resource quantification in infinite-dimensional general probabilistic theories
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Stabilizer extent is not multiplicative
• Fast estimation of outcome probabilities for quantum circuits
• Tight constraints on probabilistic convertibility of quantum states
• A single $T$-gate makes distribution learning hard
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Fourier expansion in variational quantum algorithms
• Magic-induced computational separation in entanglement theory
• Fast Stabiliser Simulation with Quadratic Form Expansions
• How to simulate quantum measurement without computing marginals
• Bell sampling from quantum circuits
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Nonstabilizerness of Permutationally Invariant Systems
• A Family of Quantum Codes with Exotic Transversal Gates
• Phase transition in Stabilizer Entropy and efficient purity estimation
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• The Fermionic Quantum Emulator
• Just Like the Real Thing: Fast Weak Simulation of Quantum Computation
• Simulating quench dynamics on a digital quantum computer with data-driven error mitigation
• Magic of quantum hypergraph states
• Magic Resources of the Heisenberg Picture
• Universal limitations on implementing resourceful unitary evolutions
• Probing quantum complexity via universal saturation of stabilizer entropies
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Classical simulation of non-Gaussian fermionic circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• Quantum Error Mitigation by Pauli Check Sandwiching
• Efficient mutual magic and magic capacity with matrix product states
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• One-Shot Yield-Cost Relations in General Quantum Resource Theories
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Handbook for Quantifying Robustness of Magic
• Quantum Non-Local Nonstabilizerness
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Gravitational back-reaction is magical
• Doped stabilizer states in many-body physics and where to find them
• Chaos and magic in the dissipative quantum kicked top
• Stabilizer Tensor Networks with Magic State Injection
• Non-equilibrium quantum Monte Carlo algorithm for stabilizer Renyi entropy in spin systems
• Stabilizer rank and higher-order Fourier analysis
• Simulation of quantum optics by coherent state decomposition
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Optimal quantum circuit cuts with application to clustered Hamiltonian simulation
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Clifford recompilation for faster classical simulation of quantum circuits
• Magic of Random Matrix Product States
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Improved simulation of quantum circuits dominated by free fermionic operations
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Sharp complexity phase transitions generated by entanglement
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Bridging Entanglement and Magic Resources within Operator Space
• Magic transition in measurement-only circuits
• Nonstabilizerness of a Boundary Time Crystal
• Classical simulation of non-Gaussian bosonic circuits
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• A nonstabilizerness monotone from stabilizerness asymmetry
• Extracting randomness from magic quantum states
• Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
• Overcoming entropic limitations on asymptotic state transformations through probabilistic protocols
• Universal resources for quantum computing
• Simulation of Quantum Computers: Review and Acceleration Opportunities
• Improved Graph Formalism for Quantum Circuit Simulation
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Fermionic Magic Resources of Quantum Many-Body Systems
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
• Imperfect quantum networks with tailored resource states
• Deep Quantum Circuit Simulations of Low-Energy Nuclear States
• Abstraqt: Analysis of Quantum Circuits via Abstract Stabilizer Simulation
• Faster Born probability estimation via gate merging and frame optimisation
• Lower Bounds on Stabilizer Rank
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Quantum Ruzsa Divergence to Quantify Magic
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Reduce&chop: Shallow circuits for deeper problems
• Efficient witnessing and testing of magic in mixed quantum states
• Maximal Magic for Two-qubit States
• New techniques for bounding stabilizer rank
• Classical simulation and quantum resource theory of non-Gaussian optics
• Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions
• Computing quantum magic of state vectors
• Simulating Quantum Computations with Tutte Polynomials
• Fast simulation of planar Clifford circuits
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Synthesizing quantum circuits via numerical optimization
• Accelerating Simulation of Quantum Circuits under Noise via Computational Reuse
• Non-stabilizerness of Neural Quantum States
• Computational self-testing for entangled magic states
• Possibilistic simulation of quantum circuits by classical circuits
• Unconditional quantum magic advantage in shallow circuit computation
• Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation
• Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Certifying nonstabilizerness in quantum processors
• Faster computation of nonstabilizerness
• Lower T-count with faster algorithms
• Role of quantum state texture in probing resource theories and quantum phase transition
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Wasserstein Complexity of Quantum Circuits
• Single-copy stabilizer testing
• Fast algorithms for classical specifications of stabiliser states and Clifford gates
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Rise and fall of nonstabilizerness via random measurements
• Non-stabilizerness and entanglement from cat-state injection
• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits
• PAC-learning of free-fermionic states is NP-hard
• Analyzing the free states of one quantum resource theory as resource states of another
• Toolchain for Faster Iterations in Quantum Software Development
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• Chasing shadows with Gottesman-Kitaev-Preskill codes
• On the Hardness of Measuring Magic
• Quantifying magic via quantum $(\alpha ,\beta )$ Jensen-Shannon divergence
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
• Fast Classical Simulation of Quantum Circuits via Parametric Rewriting in the ZX-Calculus
• Efficient simulation of logical magic state preparation protocols
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• Characterization of non-adaptive Clifford channels
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Spectral signatures of nonstabilizerness and criticality in infinite matrix product states
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Harvesting stabilizer entropy and non-locality from a quantum field
• Agnostic Tomography of Stabilizer Product States
• A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Efficient Classical Simulation of the DQC1 Circuit with Zero Discord
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• Noncontextual Pauli Hamiltonians
• GCAMPS: A Scalable Classical Simulator for Qudit Systems
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
• Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography
• Pseudoentanglement Ain't Cheap
• Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Duality theory for Clifford tensor powers
• Limits of Clifford Disentangling in Tensor Network States