Fast estimation of outcome probabilities for quantum circuits

Abstract

We present two classical algorithms for the simulation of universal quantum circuits on $n$ qubits constructed from $c$ instances of Clifford gates and $t$ arbitrary-angle $Z$-rotation gates such as $T$ gates. Our algorithms complement each other by performing best in different parameter regimes. The $\mathtt{Estimate}$ algorithm produces an additive precision estimate of the Born rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (which scales like $\approx 1.17^t$ for $T$ gates). Our algorithm is state-of-the-art for this task: as an example, in approximately $13$ hours (on a standard desktop computer), we estimated the Born rule probability to within an additive error of $0.03$, for a $50$-qubit, $60$ non-Clifford gate quantum circuit with more than $2000$ Clifford gates. Our second algorithm, $\mathtt{Compute}$, calculates the probability of a chosen measurement outcome to machine precision with run-time $O(2^{t-r}t)$ where $r$ is an efficiently computable, circuit-specific quantity. With high probability, $r$ is very close to $\min \{t,n-w\}$ for random circuits with many Clifford gates, where $w$ is the number of measured qubits. $\mathtt{Compute}$ can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+$T$ circuits with $n=55$, $w=5$, $c=10^5$ and $t=80$ $T$ gates, and then compute the Born rule probability with a run-time consistently less than $10$ minutes using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden shift algorithm and the quantum approximate optimization algorithm (QAOA).

arXiv commentPublished in PRX Quantum. 15+28 pages, 8 figures. Version 3 contains new benchmarks, changes suggested by reviewers, and various other improvements. Comments welcome

References in corpus (36)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Supervised learning with quantum enhanced feature spaces
• Quantum computational advantage using photons
• Quantum Teleportation is a Universal Computational Primitive
• Improved Simulation of Stabilizer Circuits
• Quantum Computational Supremacy
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Direct Fidelity Estimation from Few Pauli Measurements
• Simulating quantum computation by contracting tensor networks
• Positive Wigner functions render classical simulation of quantum computation efficient
• Efficient Classical Simulation of Continuous Variable Quantum Information Processes
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Discrete phase space based on finite fields
• Negative Quasi-Probability as a Resource for Quantum Computation
• Methodology for quantum logic gate constructions
• Hudson's Theorem for finite-dimensional quantum systems
• Classical simulation of noninteracting-fermion quantum 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
• Massive Parallel Quantum Computer Simulator
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Matchgates and classical simulation of quantum circuits
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Massively parallel quantum computer simulator, eleven years later
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Quantum Supremacy Is Both Closer and Farther than It Appears
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• From estimation of quantum probabilities to simulation of quantum circuits
• Reducing the quantum computing overhead with complex gate distillation
• Efficient Inner-product Algorithm for Stabilizer States
• Clifford recompilation for faster classical simulation of quantum circuits

Cited by in corpus (23)

• Partially Fault-tolerant Quantum Computing Architecture with Error-corrected Clifford Gates and Space-time Efficient Analog Rotations
• Bell sampling from quantum circuits
• Error mitigation with Clifford quantum-circuit data
• Classical simulation of non-Gaussian fermionic circuits
• Stabilizer Tensor Networks with Magic State Injection
• Non-equilibrium quantum Monte Carlo algorithm for stabilizer Renyi entropy in spin systems
• Improved simulation of quantum circuits dominated by free fermionic operations
• Bridging Entanglement and Magic Resources within Operator Space
• Classical simulation of non-Gaussian bosonic circuits
• Abstraqt: Analysis of Quantum Circuits via Abstract Stabilizer Simulation
• Faster Born probability estimation via gate merging and frame optimisation
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• Possibilistic simulation of quantum circuits by classical circuits
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Improving the efficiency of learning-based error mitigation
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• On the role of coherence for quantum computational advantage
• Efficient Eigenstate Preparation in an Integrable Model with Hilbert Space Fragmentation
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
• GCAMPS: A Scalable Classical Simulator for Qudit Systems
• Efficient classical simulation of cluster state quantum circuits with alternative inputs