Negative Quasi-Probability as a Resource for Quantum Computation

Abstract

A central problem in quantum information is to determine the minimal physical resources that are required for quantum computational speedup and, in particular, for fault-tolerant quantum computation. We establish a remarkable connection between the potential for quantum speed-up and the onset of negative values in a distinguished quasi-probability representation, a discrete analog of the Wigner function for quantum systems of odd dimension. This connection allows us to resolve an open question on the existence of bound states for magic-state distillation: we prove that there exist mixed states outside the convex hull of stabilizer states that cannot be distilled to non-stabilizer target states using stabilizer operations. We also provide an efficient simulation protocol for Clifford circuits that extends to a large class of mixed states, including bound universal states.

15 pages v4: This is a major revision. In particular, we have added a new section detailing an explicit extension of the Gottesman-Knill simulation protocol to deal with positively represented states and measurement (even when these are non-stabilizer). This paper also includes significant elaboration on the two main results of the previous version

References in corpus (14)

• Gaussian Quantum Information
• Restrictions on Transversal Encoded Quantum Gate Sets
• Evenly distributed unitaries: on the structure of unitary designs
• Negativity and contextuality are equivalent notions of nonclassicality
• Improved magic states distillation for quantum universality
• Classicality in discrete Wigner functions
• Discrete Wigner functions and quantum computational speedup
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• Qutrit Magic State Distillation
• Framed Hilbert space: hanging the quasi-probability pictures of quantum theory
• Catalysis and activation of magic states in fault tolerant architectures
• Non-negative Wigner functions in prime dimensions
• Nonnegative subtheories and quasiprobability representations of qubits
• Noise Thresholds for Higher Dimensional Systems using the Discrete Wigner Function

Cited by in corpus (243)

• Quantum Resource Theories
• Contextuality supplies the magic for quantum computation
• The Resource Theory of Stabilizer Computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Resource theory of quantum non-Gaussianity and Wigner negativity
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Kochen-Specker Contextuality
• Convex resource theory of non-Gaussianity
• Enhanced fault-tolerant quantum computing in $d$-level systems
• Multiqubit Clifford groups are unitary 3-designs
• Many-body quantum magic
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Contextuality as a resource for models of quantum computation on qubits
• Wigner function negativity and contextuality in quantum computation on rebits
• Operational Advantage of Quantum Resources in Subchannel Discrimination
• Multilevel distillation of magic states for quantum computing
• Operational Resource Theory of Quantum Channels
• Quantifying the magic of quantum channels
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Reliable quantum certification for photonic quantum technologies
• Resources of nonlinear cavity magnonics for quantum information
• Contextuality and Wigner function negativity in qubit quantum computation
• Quantum fluctuation theorems, contextuality and work quasi-probabilities
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Observing Dirac's classical phase space analog to the quantum state
• Circuit knitting with classical communication
• Efficiently computable bounds for magic state distillation
• Simulating boson sampling in lossy architectures
• Convex geometry of quantum resource quantification
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Robust preparation of Wigner-negative states with optimized SNAP-displacement sequences
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Operational relevance of resource theories of quantum measurements
• Nonstabilizerness via matrix product states in the Pauli basis
• Simulating realistic non-Gaussian state preparation
• Phase space simulation method for quantum computation with magic states on qubits
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Quantum interference as a resource for quantum speedup
• Uniqueness of noncontextual models for stabilizer subtheories
• Quantum Advantage from Sequential-Transformation Contextuality
• Wigner phase space distribution as a wave function
• Axiomatic and operational connections between the $l_1$-norm of coherence and negativity
• Negative Full Counting Statistics Arise From Interference Effects
• Probabilistic Simulation of Quantum Circuits with the Transformer
• Quasiprobability representation of quantum coherence
• Quasiprobability representations of quantum mechanics with minimal negativity
• Unbiased Simulation of Near-Clifford Quantum Circuits
• Non-stabilizerness versus entanglement in matrix product states
• Permutation Symmetry Determines the Discrete Wigner Function
• From estimation of quantum probabilities to simulation of quantum circuits
• A hidden variable model for universal quantum computation with magic states on qubits
• Efficiency vs. multi-photon contribution test for quantum dots
• Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers
• Symmetry-protected sign problem and magic in quantum phases of matter
• Critical behaviors of non-stabilizerness in quantum spin chains
• Quasi-probability distributions for observables in dynamic systems
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Entanglement-magic separation in hybrid quantum circuits
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Noncontextual wirings
• Pseudomagic Quantum States
• Tractable Simulation of Error Correction with Honest Approximations to Realistic Fault Models
• Phase-space inequalities beyond negativities
• Resource theory of contextuality for arbitrary prepare-and-measure experiments
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Qutrit Magic State Distillation Tight in Some Directions
• Characterization of an operational quantum resource in a critical many-body system
• Quasiprobability distributions in open quantum systems: spin-qubit systems
• Quasiprobability distributions for quantum-optical coherence and beyond
• Fast estimation of outcome probabilities for quantum circuits
• Fisher information universally identifies quantum resources
• Advances in Bosonic Quantum Error Correction with Gottesman-Kitaev-Preskill Codes: Theory, Engineering and Applications
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• The first law of general quantum resource theories
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Rotational covariance and GHZ contradictions for three or more particles of any dimension
• A single $T$-gate makes distribution learning hard
• Efficient backcasting search for optical quantum state synthesis
• Generalized concurrence in boson sampling
• Stabilizer information inequalities from phase space distributions
• Resource theory of quantum uncomplexity
• Virtual quantum resource distillation
• Probability representation of quantum dynamics using pseudostochastic maps
• Qutrit and Ququint Magic States
• Quantum Contextuality with Stabilizer States
• Wigner negativity in spin-$j$ systems
• Maximum nonlocality and minimum uncertainty using magic states
• Magic of quantum hypergraph states
• Universal limitations on implementing resourceful unitary evolutions
• Gaussification through decoherence
• Discrete Wigner Functions from Informationally Complete Quantum Measurements
• Quantum Advantage in Information Retrieval
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Classical simulation of non-Gaussian fermionic circuits
• Phase-space methods for representing, manipulating, and correcting Gottesman-Kitaev-Preskill qubits
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Handbook for Quantifying Robustness of Magic
• Characterization of phase-averaged coherent states
• Mermin inequalities for perfect correlations in many-qutrit systems
• Magic State Distillation with the Ternary Golay Code
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Graph-theoretic strengths of contextuality
• Negativity Bounds for Weyl-Heisenberg Quasiprobability Representations
• Contextuality and The Single-Qubit Stabilizer Formalism
• Generalized Gambler's Ruin Problem: explicit formulas via Siegumd duality
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• The role of cohomology in quantum computation with magic states
• State-injection schemes of quantum computation in Spekkens' toy theory
• Entanglement of random hypergraph states
• Virtual quantum resource distillation: General framework and applications
• Knots, links, and long-range magic
• Some Examples of Contextuality in Physics: Implications to Quantum Cognition
• Quasistates and quasiprobabilities
• Testing quantum mechanics: a statistical approach
• Simulation of quantum optics by coherent state decomposition
• Spekkens' toy model in all dimensions and its relationship with stabilizer quantum mechanics
• Magic of Random Matrix Product States
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Conditional nonclassical field generation in cavity QED
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Quantumness Beyond Entanglement: The Case of Symmetric States
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Experimental Reconstruction of Entanglement Quasiprobabilities
• General conditions for maximal violation of non-contextuality in discrete and continuous variables
• Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
• Quantum Theory is a Quasi-stochastic Process Theory
• Witnessing negativity of Wigner function by estimating fidelities of cat-like states from homodyne measurements
• The vacuum provides quantum advantage to otherwise simulatable architectures
• Stabilizer Rényi Entropy and Conformal Field Theory
• Quantum speed limits in arbitrary phase spaces
• States that "look the same" with respect to every basis in a mutually unbiased set
• Likelihood-free methods for quantum parameter estimation
• Epistemically restricted phase space representation, weak momentum value, and reconstruction of quantum wave function
• Classical simulation of non-Gaussian bosonic circuits
• Minimal informationally complete measurements for probability representation of quantum dynamics
• States that are far from being stabilizer states
• Quantum Bayesian Inference in Quasiprobability Representations
• Attoscience in Phase Space
• Exact and Efficient Simulation of Concordant Computation
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem
• Contextual bound states for qudit magic state distillation
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Noise thresholds for classical simulability of non-linear Boson sampling
• Quantum speed limit for Kirkwood-Dirac quasiprobabilities
• Multi-time correlations in the positive-P, Q, and doubled phase-space representations
• Universal resources for quantum computing
• Advantages of the Kirkwood-Dirac distribution among general quasi-probabilities for finite-state quantum systems
• 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
• Snapshotting Quantum Dynamics at Multiple Time Points
• Efficient witnessing and testing of magic in mixed quantum states
• Quantum Ruzsa Divergence to Quantify Magic
• Hybrid magic state distillation for universal fault-tolerant quantum computation
• Computing quantum magic of state vectors
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Clifford operations and homological codes for rotors and oscillators
• A classical formulation of quantum theory?
• Measurement Contextuality and Planck's Constant
• Maximal Magic for Two-qubit States
• Qubit from the classical collision entropy
• Kenfack Zyczkowski indicator of nonclassicality for two non-equivalent representations of Wigner function of qutrit
• Non-stabilizerness in quantum-enhanced metrological protocols
• Counting stabiliser codes for arbitrary dimension
• Wigner representation of the rotational dynamics of rigid tops
• On Quantum Steering and Wigner Negativity
• Orbital-Free Quasi-Density Functional Theory
• Quantum Bochner's theorem for phase spaces built on projective representations
• Non-stabilizerness of Neural Quantum States
• Quantum Path Computing: Computing Architecture with Propagation Paths in Multiple Plane Diffraction of Classical Sources of Fermion and Boson Particles
• Efficient computations of quantum canonical Gibbs state in phase space
• Classical codes in quantum state space
• Logical Entropy and Negative Probabilities in Quantum Mechanics
• Approximating outcome probabilities of linear optical circuits
• Evolution of quasi-characteristic functions in quantum stochastic systems with Weyl quantization of energy operators
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Quasiprobability distributions with weak measurements
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• The Non-Disjoint Ontic States of the Grassmann Ontological Model, Transformation Contextuality, and the Single Qubit Stabilizer Subtheory
• Witnessing Bell violations through probabilistic negativity
• A quantum prediction as a collection of epistemically restricted classical predictions
• Choi-Defined Resource Theories
• Rise and fall of nonstabilizerness via random measurements
• Gaussian boson sampling at finite temperature
• Wigner's Theorem for stabilizer states and quantum designs
• Heralded dissipative preparation of nonclassical states in a Kerr oscillator
• Generalized parity proofs of the Kochen-Specker theorem
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Polytopes of Absolutely Wigner Bounded Spin States
• Path superposition activating perfect quantum teleportation ability for separable states
• Noise-adaptive test of quantum correlations with quasiprobability functions
• On measures of classicality/quantumness in quasiprobability representations of finite-dimensional quantum systems
• Stellar representation of extremal Wigner-negative spin states
• Simulating quantum computation: how many "bits" for "it"?
• Low Overhead Qutrit Magic State Distillation
• Quantum Coherence and Distinguishability as Complementary Resources: A Resource-Theoretic Perspective from Wave-Particle Duality
• Contextuality Can be Verified with Noncontextual Experiments
• Generalized reduction formula for Discrete Wigner functions of multiqubit systems
• Grand Unification of All Discrete Wigner Functions on $d\times d$ Phase Space
• Spin flip of multiqubit states in discrete phase space
• Harvesting Contextuality from the Vacuum
• Topos logic in measurement-based quantum computation
• Quantum non-Gaussian high Fock states of light pulses and their superpositions
• Wigner formalism for a particle on an infinite lattice: dynamics and spin
• On the stabilizer complexity of Hawking radiation
• Probing Kirkwood-Dirac nonpositivity and its operational implications via moments
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• Quantum-to-Classical Transition via Single-Shot Generalized Measurements
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• Characterization of non-adaptive Clifford channels
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Quantifying magic via quantum $(\alpha ,\beta )$ Jensen-Shannon divergence
• Using Quantum Computers to Learn Physics
• How contextuality and antidistinguishability are related
• General entropic constraints on CSS codes within magic distillation protocols
• Nonclassicality in a dispersive atom-cavity field interaction in presence of an external driving field
• Almost no experiments have classical Kirkwood-Dirac representations
• Operational quasiprobabilities for continuous variables
• Deterministic Gaussian conversion protocols for non-Gaussian single-mode resources
• Contextuality from the vacuum
• Classical algorithms for measurement-adaptive Gaussian circuits
• Quasi-Bell inequalities from symmetrized products of noncommuting qubit observables
• A Study on Stabilizer Rényi Entropy Estimation using Machine Learning
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Spin coherence scale: operator-ordering sensitivity beyond the Heisenberg-Weyl group
• Joint quasiprobability distribution on the measurement outcomes of MUB-driven operators
• Non-Gaussianity from superselection rules
• Optical Quantum Computing
• Efficient measure of information backflow with a quasistochastic process
• Probing information theoretic measures of nonlinear ultracold quantum gases using phase-space distributions
• Efficient Classical Simulation of the DQC1 Circuit with Zero Discord
• Resourcefulness of non-classical continuous-variable quantum gates
• The Interplay between Quantum Contextuality and Wigner Negativity
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories