Positive Wigner functions render classical simulation of quantum computation efficient

Abstract

We show that quantum circuits where the initial state and all the following quantum operations can be represented by positive Wigner functions can be classically efficiently simulated. This is true both for continuous-variable as well as discrete variable systems in odd prime dimensions, two cases which will be treated on entirely the same footing. Noting the fact that Clifford and Gaussian operations preserve the positivity of the Wigner function, our result generalizes the Gottesman-Knill theorem. Our algorithm provides a way of sampling from the output distribution of a computation or a simulation, including the efficient sampling from an approximate output distribution in case of sampling imperfections for initial states, gates, or measurements. In this sense, this work highlights the role of the positive Wigner function as separating classically efficiently simulatable systems from those that are potentially universal for quantum computing and simulation, and it emphasizes the role of negativity of the Wigner function as a computational resource.

7 pages, minor changes

References in corpus (11)

• Multi-party entanglement in graph states
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Novel schemes for measurement-based quantum computation
• Universal resources for measurement-based quantum computation
• Fast simulation of stabilizer circuits using a graph state representation
• Classicality in discrete Wigner functions
• Randomized Benchmarking of Multi-Qubit Gates
• Discrete Wigner functions and quantum computational speedup
• Classical simulation versus universality in measurement based quantum computation
• Directly estimating non-classicality
• Probing the negative Wigner function of a pulsed single photon point by point

Cited by in corpus (295)

• 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
• Modes and states in Quantum Optics
• Non-Gaussian Quantum States and Where to Find Them
• 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
• Schrödinger cat states of a 16-microgram mechanical oscillator
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Non-Gaussian quantum states of a multimode light field
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Wigner function negativity and contextuality in quantum computation on rebits
• Quantifying the magic of quantum channels
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Reliable quantum certification for photonic quantum technologies
• Quantifying magic for multi-qubit operations
• Contextuality and Wigner function negativity in qubit quantum computation
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Stellar representation of non-Gaussian quantum states
• Detecting quantum non-Gaussianity via the Wigner function
• 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
• Simulating boson sampling in lossy architectures
• Efficiently computable bounds for magic state distillation
• Entanglement and Wigner function negativity of multimode non-Gaussian states
• Resolution of 100 photons and quantum generation of unbiased random numbers
• Statistics of photon-subtracted and photon-added states
• 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
• Creation, storage, and on-demand release of optical quantum states with a negative Wigner function
• Precision measurements with photon-subtracted or photon-added Gaussian states
• Synchronization of optical photons for quantum information processing
• Simulating realistic non-Gaussian state preparation
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Phase space simulation method for quantum computation with magic states on qubits
• Pure single photons from a trapped atom source
• Quantum non-Gaussianity witnesses in the phase space
• Resources for bosonic quantum computational advantage
• Production of photonic universal quantum gates enhanced by machine learning
• Experimental demonstration of remotely creating Wigner negativity via quantum steering
• Compact Gaussian quantum computation by multi-pixel homodyne detection
• Certification of non-Gaussian states with operational measurements
• Quantum interference as a resource for quantum speedup
• Tailoring Non-Gaussian Continuous-Variable Graph States
• Uniqueness of noncontextual models for stabilizer subtheories
• Tomography of a Mode-Tunable Coherent Single-Photon Subtractor
• Universal control of a bosonic mode via drive-activated native cubic interactions
• Axiomatic and operational connections between the $l_1$-norm of coherence and negativity
• Probabilistic Simulation of Quantum Circuits with the Transformer
• From estimation of quantum probabilities to simulation of quantum circuits
• Properties and Applications of the Kirkwood-Dirac Distribution
• Negativity of quasiprobability distributions as a measure of nonclassicality
• Quantification and manipulation of magic states
• Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
• Negative Conditional Entropy of Post-Selected States
• Polynomial approximation of non-Gaussian unitaries by counting one photon at a time
• Efficiency vs. multi-photon contribution test for quantum dots
• Bright multiplexed source of indistinguishable single photons with tunable GHz-bandwidth at room temperature
• Critical behaviors of non-stabilizerness in quantum spin chains
• Testing nonclassicality and non-Gaussianity in phase space
• Tensor network states in time-bin quantum optics
• Pseudomagic Quantum States
• Statistical signatures of multimode single-photon added and subtracted states of light
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Remote generation of Wigner-negativity through Einstein-Podolsky-Rosen steering
• Squeezing and multimode entanglement of surface acoustic wave phonons
• Operational quantification of continuous-variable quantum resources
• Quantum Entropy and Central Limit Theorem
• What gravity mediated entanglement can really tell us about quantum gravity
• Witnessing Wigner Negativity
• Nonlinearity as a resource for nonclassicality in anharmonic systems
• Fast simulation of bosonic qubits via Gaussian functions in phase space
• Conditional non-Gaussian quantum state preparation
• Benchmarking of Gaussian boson sampling using two-point correlators
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
• Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
• Characterization of an operational quantum resource in a critical many-body system
• Quantum Wigner entropy
• Quantum non-Gaussianity of light and atoms
• Framework for resource quantification in infinite-dimensional general probabilistic theories
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Measurement-based generation and preservation of cat and grid states within a continuous-variable cluster state
• Fast estimation of outcome probabilities for quantum circuits
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Neural networks for detecting multimode Wigner-negativity
• The first law of general quantum resource theories
• Optimization of networks for measurement-based quantum computation
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Advances in Bosonic Quantum Error Correction with Gottesman-Kitaev-Preskill Codes: Theory, Engineering and Applications
• Interpretable Quantum Advantage in Neural Sequence Learning
• Gaussian conversion protocols for cubic phase state generation
• Generation of Schrödinger cat states with Wigner negativity using continuous-wave low-loss waveguide optical parametric amplifier
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Non-Gaussian Nature and Entanglement of Spontaneous Parametric Nondegenerate Triple-Photon Generation
• A single $T$-gate makes distribution learning hard
• Continuous-variable entanglement distillation and non-commutative central limit theorems
• Contextuality of general probabilistic theories
• Efficient backcasting search for optical quantum state synthesis
• Quantumness of spin-1 states
• Dynamics-Based Entanglement Witnesses for Non-Gaussian States of Harmonic Oscillators
• Generalized concurrence in boson sampling
• Stabilizer information inequalities from phase space distributions
• Resource theory of quantum uncomplexity
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Further extensions of Clifford circuits and their classical simulation complexities
• Noiseless conditional teleportation of a single photon
• Qutrit and Ququint Magic States
• Theory of genuine tripartite nonlocality of Gaussian states
• Wigner negativity in spin-$j$ systems
• Wigner negativity in the steady-state output of a Kerr parametric oscillator
• Gaussification through decoherence
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Quantifying non-stabilizerness via information scrambling
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Quantum Advantage in Information Retrieval
• Numerical study of Wigner negativity in one-dimensional steady-state resonance fluorescence
• Enhanced continuous generation of non-Gaussianity through optomechanical modulation
• Quantum arbitrary waveform generator
• Characterizing Multipartite Non-Gaussian Entanglement for Three-Mode Spontaneous Parametric Down-Conversion Process
• Randomized benchmarking for qudit Clifford gates
• Classical simulation of non-Gaussian fermionic circuits
• Quantum backflow effect and nonclassicality
• Quantum data hiding with continuous variable systems
• Quantification of Wigner Negativity Remotely Generated via Einstein-Podolsky-Rosen Steering
• Characterization of phase-averaged coherent states
• Negative Wigner function at telecommunication wavelength from homodyne detection
• Cubic nonlinear squeezing and its decoherence
• Dirac open quantum system dynamics: formulations and simulations
• Magic State Distillation with the Ternary Golay Code
• Generation of quantum states with nonlinear squeezing by Kerr nonlinearity
• Photon-phonon-photon transfer in optomechanics
• The role of cohomology in quantum computation with magic states
• Revealing quantum correlation by negativity of the Wigner function
• Steady-state generation of Wigner negative states in 1D resonance fluorescence
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• Quantifying non-Gaussianity of a quantum state by the negative entropy of quadrature distributions
• Adaptive loop-based subtraction of a single photon from a traveling beam of light
• Steady-state generation of negative-Wigner-function light using feedback
• Simulation of quantum optics by coherent state decomposition
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Interaction signatures and non-Gaussian photon states from a strongly driven atomic ensemble coupled to a nanophotonic waveguide
• A direct approach to Gaussian measurement based quantum computation
• Signatures of Many-Particle Interference
• Detecting Bell correlations in multipartite non-Gaussian spin states
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Generating optical cat states via quantum interference of multi-path free-electron-photons interactions
• Quantum state engineering by non-deterministic noiseless linear amplification
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Subtraction and Addition of Propagating Photons by Two-Level Emitters
• Tensor eigenvalues and entanglement of symmetric states
• Conditional nonclassical field generation in cavity QED
• Nonclassical steering and the Gaussian steering triangoloids
• Sharp complexity phase transitions generated by entanglement
• Loss of non-Gaussianity for damped photon-subtracted thermal states
• Detecting Einstein-Podolsky-Rosen steering in non-Gaussian spin states from conditional spin-squeezing parameters
• Witnessing negativity of Wigner function by estimating fidelities of cat-like states from homodyne measurements
• The vacuum provides quantum advantage to otherwise simulatable architectures
• Creation of non-classical states of light in a chiral waveguide
• Deterministic nonclassicality for quantum mechanical oscillators in thermal states
• Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
• Likelihood-free methods for quantum parameter estimation
• Homodyne detection of non-Gaussian quantum steering
• Are all Gaussian states also cluster states? Essential diagnostic tools for continuous-variable one-way quantum computing
• Optomechanical Self-Oscillations in an Anharmonic Potential: Engineering a Nonclassical Steady State
• Epistemically restricted phase space representation, weak momentum value, and reconstruction of quantum wave function
• Classical simulation of non-Gaussian bosonic circuits
• Dual form of the phase-space classical simulation problem in quantum optics
• Contextual bound states for qudit magic state distillation
• Absence of localization in two-dimensional Clifford circuits
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Unconditional generation of bright coherent non-Gaussian light from exciton-polariton condensates
• Exact and Efficient Simulation of Concordant Computation
• Sufficient condition for universal quantum computation using bosonic circuits
• Stoquasticity in circuit QED
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Simulating macroscopic quantum correlations in linear networks
• Noise thresholds for classical simulability of non-linear Boson sampling
• Fast Generation of High-Fidelity Mechanical Non-Gaussian States via Additional Amplifier and Photon Subtraction
• Semiclassical Formulation of Gottesman-Knill and Universal Quantum Computation
• Generation of multi-photon Fock states at telecommunication wavelength using picosecond pulsed light
• Deterministic multi-mode nonlinear coupling for quantum circuits
• Taming numerical errors in simulations of continuous variable non-Gaussian state preparation
• Phase-space negativity as a computational resource for quantum kernel methods
• From the Bloch sphere to phase space representations with the Gottesman-Kitaev-Preskill encoding
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Algorithmic quantum simulation of memory effects
• Certification of non-Gaussian Einstein-Podolsky-Rosen Steering
• Faster Born probability estimation via gate merging and frame optimisation
• Non-classicality of positive relativistic Wigner function
• Conditional preparation of non-Gaussian quantum optical states by mesoscopic measurement
• Snapshotting Quantum Dynamics at Multiple Time Points
• Efficient detection of nonclassicality using moments of the Wigner function
• Maximal Magic for Two-qubit States
• Measurement Contextuality and Planck's Constant
• Wigner distribution of Sine Gordon and Kink solitons
• Classical simulation and quantum resource theory of non-Gaussian optics
• Genuine Multipartite Entanglement induced by a Thermal Acoustic Reservoir
• Assisted metrology and preparation of macroscopic superpositions with split spin-squeezed states
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Convex roofs witnessing Kirkwood-Dirac nonpositivity
• Clifford operations and homological codes for rotors and oscillators
• Mode-selective single-photon addition to a multimode quantum field
• Statistical Mechanics of Stochastic Quantum Control: $d$-adic Rényi Circuits
• Quantum Bochner's theorem for phase spaces built on projective representations
• Classical simulability of constant-depth linear-optical circuits with noise
• Toolbox for non-classical state calculations
• Classical codes in quantum state space
• Efficient computations of quantum canonical Gibbs state in phase space
• On Quantum Steering and Wigner Negativity
• Optimal sensing of photon addition and subtraction on nonclassical light
• Approximating outcome probabilities of linear optical circuits
• The Quantum Density Matrix and its many uses: From quantum structure to quantum chaos and noisy simulators
• Persistent non-Gaussian correlations in out-of-equilibrium Rydberg atom arrays
• Two-mode light states before and after delocalized single-photon addition
• Quasiprobability distributions with weak measurements
• Superselection rules and bosonic quantum computational resources
• Catability as a metric for evaluating superposed coherent states
• The Non-Disjoint Ontic States of the Grassmann Ontological Model, Transformation Contextuality, and the Single Qubit Stabilizer Subtheory
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• Bosonic data hiding: power of linear vs non-linear optics
• Normalizer Circuits and Quantum Computation
• Fundamental limitations to key distillation from Gaussian states with Gaussian operations
• Coupled three-mode squeezed vacuum: Gaussian steering and remote generation of Wigner negativity
• Gleipnir: Toward Practical Error Analysis for Quantum Programs (Extended Version)
• Characterizing the Multipartite Entanglement Structure of Non-Gaussian Continuous-Variable States with a Single Evolution Operator
• Engineering propagating cat states with driving-assisted cavity QED
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Polytopes of Absolutely Wigner Bounded Spin States
• Steady-state tripartite non-Gaussian entanglement and steering in output field from intracavity triple-photon parametric downconversion
• Wigner-negative states in the steady-state emission of a two-level system driven by squeezed light
• Quantifying athermality and quantum induced deviations from classical fluctuation relations
• Wigner's Theorem for stabilizer states and quantum designs
• Adapting coherent-state superpositions in noisy channels
• Gaussian boson sampling at finite temperature
• Exploring the possibility of a complex-valued non-Gaussianity measure for quantum states of light
• Quadrature Coherence Scale of Linear Combinations of Gaussian Functions in Phase Space
• Tsirelson inequalities: Detecting cheating and quantumness in a single framework
• Stellar representation of extremal Wigner-negative spin states
• Low Overhead Qutrit Magic State Distillation
• A Bayesian quasi-probability approach to inferring the past of quantum observables
• Entanglement, loss, and quantumness: When balanced beam splitters are best
• Quantum non-Gaussian high Fock states of light pulses and their superpositions
• Quantum advantage in temporally flat measurement-based quantum computation
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Unveiling Vacuum Fluctuations and Nonclassical States with Cavity-Enhanced Tripartite Interactions
• Detecting single photons is not always necessary to evidence interference of photon probability amplitudes
• Path superposition activating perfect quantum teleportation ability for separable states
• Wigner formalism for a particle on an infinite lattice: dynamics and spin
• Grand Unification of All Discrete Wigner Functions on $d\times d$ Phase Space
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Quantum computational advantage implies contextuality
• General entropic constraints on CSS codes within magic distillation protocols
• On the stabilizer complexity of Hawking radiation
• Witnessing non-classicality through large deviations in quantum optics
• Subcycle tomography of quantum light
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• All non-Gaussian states are advantageous for channel discrimination: Robustness of non-convex continuous variable quantum resources
• Sufficient Wigner Negativity Implies Genuine Multipartite Entanglement
• Probing Kirkwood-Dirac nonpositivity and its operational implications via moments
• Wigner entropy conjecture and the interference formula in quantum phase space
• Non-Gaussian state teleportation with a nonlinear feedforward
• Nonclassicality in a dispersive atom-cavity field interaction in presence of an external driving field
• Sampling and the complexity of nature
• No real advantage of photon subtraction and displacement in continuous variable measurement device independent quantum key distribution
• Deterministic Gaussian conversion protocols for non-Gaussian single-mode resources
• Nonlocality in Continuous-Variable Quantum Networks
• Classical algorithms for measurement-adaptive Gaussian circuits
• Teleportation-based squeezer for bosonic cluster states
• Characterization of Generalized Coherent States through Intensity-Field Correlations
• Robust Negativity in the Quantum-to-Classical Transition of Kerr Dynamics
• Non-Gaussianity from superselection rules
• Continuous Generation and Stabilization of Mesoscopic Field Superposition States in a Quantum Circuit
• Probing information theoretic measures of nonlinear ultracold quantum gases using phase-space distributions
• Understanding Squeezed States of Light Through Wigner's Phase-Space
• Monte Carlo Quantum Computing
• Measuring High-Order Phonon Correlations in an Optomechanical Resonator
• The Interplay between Quantum Contextuality and Wigner Negativity
• Majorization theoretical approach to entanglement enhancement via local filtration
• On overall measure of non-classicality of $N$-level quantum system and its universality in the large $N$ limit
• Twisted Fourier analysis and pseudo-probability distributions
• Pinching operators for approximating multiphoton entangled states
• From Quantum Optics to Quantum Technologies
• Circuit connectivity boosts by quantum-classical-quantum interfaces
• Coherent LQG Control, Free-Carrier Oscillations, Optical Ising Machines and Pulsed OPO Dynamics
• Resourcefulness of non-classical continuous-variable quantum gates
• Filter functions for the Glauber-Sudarshan $P$-function regularization
• Optical Quantum Computing
• Dynamical complexity of non-Gaussian many-body systems with dissipation