Quantifying quantum speedups: improved classical simulation from tighter magic monotones

Abstract

Consumption of magic states promotes the stabilizer model of computation to universal quantum computation. Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones. Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity. We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits. Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds. Our third simulator trades precision for speed by discarding negative quasiprobabilities. We connect each algorithm's performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds. Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones. For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators' performance scaling. Furthermore, our monotones establish several asymptotic and non-asymptotic bounds on state interconversion and distillation rates. Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.

24+13 pages, 8 figures; final author copy. Since v1: restructured with additional discussion, proof sketches and examples. Since v3: minor revisions to improve clarity, additional acknowledgments

References in corpus (74)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Mixed State Entanglement and Quantum Error Correction
• Quantifying Coherence
• Quantum Coherence as a Resource
• The logarithmic negativity: A full entanglement monotone that is not convex
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Error mitigation for short-depth quantum circuits
• Quantum Resource Theories
• Quantum Nonlocality without Entanglement
• A Theory of Fault-Tolerant Quantum Computation
• Operational Resource Theory of Coherence
• Robustness of entanglement
• Roads towards fault-tolerant universal quantum computation
• Robustness of coherence: An operational and observable measure of quantum coherence
• Classical simulation of quantum many-body systems with a tree tensor network
• Noise tailoring for scalable quantum computation via randomized compiling
• The Resource Theory of Stabilizer Computation
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Entanglement Measures under Symmetry
• 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
• Negative Quasi-Probability as a Resource for Quantum Computation
• A random compiler for fast Hamiltonian simulation
• The general structure of quantum resource theories
• Hudson's Theorem for finite-dimensional quantum systems
• Classical simulation of noninteracting-fermion quantum circuits
• Further results on the cross norm criterion for separability
• 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
• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Enhanced fault-tolerant quantum computing in $d$-level systems
• Genralized Robustness of Entanglement
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Wigner function negativity and contextuality in quantum computation on rebits
• Operational Advantage of Quantum Resources in Subchannel Discrimination
• Quantum processes which do not use coherence
• Lower bounds on the non-Clifford resources for quantum computations
• Massively parallel quantum computer simulator, eleven years later
• Quantifying magic for multi-qubit operations
• Contextuality and Wigner function negativity in qubit quantum computation
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• One-Shot Operational Quantum Resource Theory
• No-Go Theorems for Quantum Resource Purification
• Efficiently computable bounds for magic state distillation
• Convex geometry of quantum resource quantification
• Resource Theory of Coherence - Beyond States
• Catalysis and activation of magic states in fault tolerant architectures
• Efficient Decoders for Qudit Topological Codes
• On Universal and Fault-Tolerant Quantum Computing
• Classical simulation of photonic linear optics with lost particles
• Benchmarking one-shot distillation in general quantum resource theories
• Phase space simulation method for quantum computation with magic states on qubits
• Roofs and Convexity
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Shorter gate sequences for quantum computing by mixing unitaries
• Quantum interference as a resource for quantum speedup
• Quantum Advantage from Sequential-Transformation Contextuality
• Unbiased Simulation of Near-Clifford Quantum Circuits
• From estimation of quantum probabilities to simulation of quantum circuits
• Logarithmic coherence: Operational interpretation of ${\ell }_1$-norm coherence
• Stabilizer extent is not multiplicative
• A new class of entanglement measures
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Clifford recompilation for faster classical simulation of quantum circuits
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Turning Gate Synthesis Errors into Incoherent Errors

Cited by in corpus (86)

• Stabilizer Rényi entropy
• Many-body quantum magic
• Quantifying nonstabilizerness of matrix product states
• Stabilizer entropies and nonstabilizerness monotones
• Measuring magic on a quantum processor
• Scalable measures of magic resource for quantum computers
• Circuit knitting with classical communication
• Benchmarking one-shot distillation in general quantum resource theories
• Measuring nonstabilizerness via multifractal flatness
• Optimal resource cost for error mitigation
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Resource theory of quantum scrambling
• Fundamental limitations on distillation of quantum channel resources
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Complexity of frustration: a new source of non-local non-stabilizerness
• Lower bound for the T count via unitary stabilizer nullity
• Operational quantification of continuous-variable quantum resources
• Pseudomagic Quantum States
• Magic in generalized Rokhsar-Kivelson wavefunctions
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Stabilizer extent is not multiplicative
• Fisher information universally identifies quantum resources
• Fast estimation of outcome probabilities for quantum circuits
• Virtual quantum resource distillation
• Magic of quantum hypergraph states
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Doubly optimal parallel wire cutting without ancilla qubits
• 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
• Handbook for Quantifying Robustness of Magic
• One-Shot Yield-Cost Relations in General Quantum Resource Theories
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Quantum Non-Local Nonstabilizerness
• Every quantum helps: Operational advantage of quantum resources beyond convexity
• Simulation of quantum optics by coherent state decomposition
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Magic of Random Matrix Product States
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Improved simulation of quantum circuits dominated by free fermionic operations
• Robustness- and weight-based resource measures without convexity restriction: Multicopy witness and operational advantage in static and dynamical quantum resource theories
• Magic transition in measurement-only circuits
• Experimental virtual distillation of entanglement and coherence
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Sufficient condition for universal quantum computation using bosonic circuits
• A nonstabilizerness monotone from stabilizerness asymmetry
• Stability of classical shadows under gate-dependent noise
• Universal resources for quantum computing
• Quantifying fermionic nonlinearity of quantum circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Quantum Ruzsa Divergence to Quantify Magic
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Optimal wire cutting with classical communication
• Classical simulation and quantum resource theory of non-Gaussian optics
• Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits
• Possibilistic simulation of quantum circuits by classical circuits
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Faster computation of nonstabilizerness
• Certifying nonstabilizerness in quantum processors
• Unconditional quantum magic advantage in shallow circuit computation
• Wasserstein Complexity of Quantum Circuits
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Wigner's Theorem for stabilizer states and quantum designs
• Rise and fall of nonstabilizerness via random measurements
• Analyzing the free states of one quantum resource theory as resource states of another
• Non-stabilizerness and entanglement from cat-state injection
• Improved Strong Simulation of Universal Quantum Circuits
• Scalable projected entangled-pair state representation of random quantum circuit states
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Characterization of non-adaptive Clifford channels
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• Optimal sampling of tensor networks targeting wave function's fast decaying tails
• General entropic constraints on CSS codes within magic distillation protocols
• On the Hardness of Measuring Magic
• Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• The entropy of quantum causal networks
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• Efficient classical simulation of cluster state quantum circuits with alternative inputs