Estimating outcome probabilities of quantum circuits using quasiprobabilities

Abstract

We present a method for estimating the probabilities of outcomes of a quantum circuit using Monte Carlo sampling techniques applied to a quasiprobability representation. Our estimate converges to the true quantum probability at a rate determined by the total negativity in the circuit, using a measure of negativity based on the 1-norm of the quasiprobability. If the negativity grows at most polynomially in the size of the circuit, our estimator converges efficiently. These results highlight the role of negativity as a measure of non-classical resources in quantum computation.

5 pages + 1 page appendix, 1 figure, comments welcome; v2 published version

References in corpus (5)

• Wigner function negativity and contextuality in quantum computation on rebits
• Classicality in discrete Wigner functions
• Framed Hilbert space: hanging the quasi-probability pictures of quantum theory
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Nonnegative subtheories and quasiprobability representations of qubits

Cited by in corpus (159)

• Error mitigation for short-depth quantum circuits
• Application of a resource theory for magic states to fault-tolerant quantum computing
• 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
• Scalable mitigation of measurement errors on quantum computers
• Resource theory of quantum non-Gaussianity and Wigner negativity
• Convex resource theory of non-Gaussianity
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Many-body quantum magic
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Quantifying the magic of quantum channels
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Contextuality and Wigner function negativity in qubit quantum computation
• Scalable measures of magic resource for quantum computers
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Circuit knitting with classical communication
• Review of Distributed Quantum Computing. From single QPU to High Performance Quantum Computing
• Efficiently computable bounds for magic state distillation
• Conformal field theories are magical
• Easing the Monte Carlo sign problem
• A quasiprobability distribution for heat fluctuations in the quantum regime
• Fast quantum circuit cutting with randomized measurements
• Phase space simulation method for quantum computation with magic states on qubits
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Extending quantum probabilistic error cancellation by noise scaling
• Optimal resource cost for error mitigation
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Resources for bosonic quantum computational advantage
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Machine Learning meets Quantum Foundations: A Brief Survey
• Quantum Advantage from Sequential-Transformation Contextuality
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Axiomatic and operational connections between the $l_1$-norm of coherence and negativity
• Unbiased Simulation of Near-Clifford Quantum Circuits
• Quasiprobability representation of quantum coherence
• Quasiprobability representations of quantum mechanics with minimal negativity
• From estimation of quantum probabilities to simulation of quantum circuits
• Negativity of quasiprobability distributions as a measure of nonclassicality
• Properties and Applications of the Kirkwood-Dirac Distribution
• A hidden variable model for universal quantum computation with magic states on qubits
• Symmetric Informationally Complete Measurements Identify the Irreducible Difference between Classical and Quantum Systems
• Universal and Operational Benchmarking of Quantum Memories
• Symmetry-protected sign problem and magic in quantum phases of matter
• Critical behaviors of non-stabilizerness in quantum spin chains
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Detecting and quantifying entanglement on near-term quantum devices
• Error mitigation and quantum-assisted simulation in the error corrected regime
• The computational landscape of general physical theories
• Quasiprobability distributions for quantum-optical coherence and beyond
• Framework for resource quantification in infinite-dimensional general probabilistic theories
• Fast estimation of outcome probabilities for quantum circuits
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Stabilizer extent is not multiplicative
• A single $T$-gate makes distribution learning hard
• Operational applications of the diamond norm and related measures in quantifying the non-physicality of quantum maps
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Quantum machine learning with adaptive linear optics
• Cutting multi-control quantum gates with ZX calculus
• Virtual quantum resource distillation
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Probability representation of quantum dynamics using pseudostochastic maps
• Qutrit and Ququint Magic States
• Magic of quantum hypergraph states
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Quantum Advantage in Information Retrieval
• Doubly optimal parallel wire cutting without ancilla qubits
• Numerical study of Wigner negativity in one-dimensional steady-state resonance fluorescence
• Contextuality bounds the efficiency of classical simulation of quantum processes
• Classical simulation of non-Gaussian fermionic circuits
• Handbook for Quantifying Robustness of Magic
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Quantum backflow effect and nonclassicality
• Gravitational back-reaction is magical
• Negativity Bounds for Weyl-Heisenberg Quasiprobability Representations
• The role of cohomology in quantum computation with magic states
• Optimal joint cutting of two-qubit rotation gates
• Fluctuating work in coherent quantum systems: proposals and limitations
• Quantum Complexity Fluctuations from Nuclear and Hypernuclear Forces
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Quasistates and quasiprobabilities
• Quantum state engineering by non-deterministic noiseless linear amplification
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Sharp complexity phase transitions generated by entanglement
• Epistemically restricted phase space representation, weak momentum value, and reconstruction of quantum wave function
• Verifying single-mode nonclassicality beyond negativity in phase space
• Minimal informationally complete measurements for probability representation of quantum dynamics
• Quantum Bayesian Inference in Quasiprobability Representations
• Hierarchies of resources for measurement-based quantum computation
• Contextual bound states for qudit magic state distillation
• A Hardware-Aware Gate Cutting Framework for Practical Quantum Circuit Knitting
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Exact and Efficient Simulation of Concordant Computation
• Experimental virtual distillation of entanglement and coherence
• Stoquasticity in circuit QED
• Phase-space negativity as a computational resource for quantum kernel methods
• Universal resources for quantum computing
• Quantifying fermionic nonlinearity of quantum circuits
• SCIM MILQ: An HPC Quantum Scheduler
• Efficient classical simulation and benchmarking of quantum processes in the Weyl basis
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Algorithmic quantum simulation of memory effects
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Snapshotting Quantum Dynamics at Multiple Time Points
• Optimal wire cutting with classical communication
• Quasiprobability fluctuation theorem behind the spread of quantum information
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Classical simulation and quantum resource theory of non-Gaussian optics
• Computing quantum magic of state vectors
• Automatic Test Pattern Generation for Robust Quantum Circuit Testing
• Counting stabiliser codes for arbitrary dimension
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Approximating outcome probabilities of linear optical circuits
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Certifying nonstabilizerness in quantum processors
• Faster computation of nonstabilizerness
• Two-mode light states before and after delocalized single-photon addition
• Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
• Polytopes of Absolutely Wigner Bounded Spin States
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Sequency Hierarchy Truncation (SeqHT) for Adiabatic State Preparation and Time Evolution in Quantum Simulations
• Grand Unification of All Discrete Wigner Functions on $d\times d$ Phase Space
• Noise-adaptive test of quantum correlations with quasiprobability functions
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Perspectives on Utilization of Measurements in Quantum Algorithms
• Coherence as a resource for phase estimation
• Improved Strong Simulation of Universal Quantum Circuits
• Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise
• Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
• The Kirkwood-Dirac representation associated to the Fourier transform for finite abelian groups: positivity
• On the stabilizer complexity of Hawking radiation
• How contextuality and antidistinguishability are related
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• Double-Bracket Master Equations: Phase-Space Representation and Classical Limit
• Circuit cutting with classical side information
• Characterization of non-adaptive Clifford channels
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• Sampling and the complexity of nature
• On the Hardness of Measuring Magic
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Power of photonic states: from quantum computation to cosmology
• Efficient Classical Simulation of the DQC1 Circuit with Zero Discord
• The symplectic rank of non-Gaussian quantum states
• Resourcefulness of non-classical continuous-variable quantum gates
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories
• Classical algorithms for measurement-adaptive Gaussian circuits
• Almost no experiments have classical Kirkwood-Dirac representations
• Robust Negativity in the Quantum-to-Classical Transition of Kerr Dynamics
• The Interplay between Quantum Contextuality and Wigner Negativity
• Circuit connectivity boosts by quantum-classical-quantum interfaces
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states
• All fundamental non-contextuality inequalities are unique