Positive Wigner functions render classical simulation of quantum computation efficient
arXiv:1208.3660 · doi:10.1103/PhysRevLett.109.230503
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.
arXiv comment7 pages, minor changes
References in corpus (23)
- Gaussian Quantum Information
- Multi-party entanglement in graph states
- Classical simulation of infinite-size quantum lattice systems in one spatial dimension
- Stabilizer Codes and Quantum Error Correction
- On the impossibility of distilling Gaussian states with Gaussian operations
- The characterization of Gaussian operations and Distillation of Gaussian States
- Simulating quantum computation by contracting tensor networks
- Efficient Classical Simulation of Continuous Variable Quantum Information Processes
- Gaussian transformations and distillation of entangled Gaussian states
- Quantum Nonlocality in Phase Space
- Hudson's Theorem for finite-dimensional quantum systems
- Most quantum states are too entangled to be useful as computational resources
- 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
- Bound States for Magic State Distillation in Fault-Tolerant Quantum Computation
- Extending Hudson's theorem to mixed quantum states
Cited by in corpus (296)
- 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 -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
- Quantifying magic for multi-qubit operations
- Reliable quantum certification for photonic quantum technologies
- Contextuality and Wigner function negativity in qubit quantum computation
- 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
- Stellar representation of non-Gaussian quantum states
- Detecting quantum non-Gaussianity via the Wigner function
- Observing Dirac's classical phase space analog to the quantum state
- Efficiently computable bounds for magic state distillation
- Simulating boson sampling in lossy architectures
- 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
- Universal control of a bosonic mode via drive-activated native cubic interactions
- Tomography of a Mode-Tunable Coherent Single-Photon Subtractor
- Wigner phase space distribution as a wave function
- Probabilistic Simulation of Quantum Circuits with the Transformer
- Axiomatic and operational connections between the -norm of coherence and negativity
- Quantification and manipulation of magic states
- Negativity of quasiprobability distributions as a measure of nonclassicality
- Properties and Applications of the Kirkwood-Dirac Distribution
- From estimation of quantum probabilities to simulation of quantum circuits
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Polynomial approximation of non-Gaussian unitaries by counting one photon at a time
- Negative Conditional Entropy of Post-Selected States
- Bright multiplexed source of indistinguishable single photons with tunable GHz-bandwidth at room temperature
- Efficiency vs. multi-photon contribution test for quantum dots
- 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
- What gravity mediated entanglement can really tell us about quantum gravity
- Remote generation of Wigner-negativity through Einstein-Podolsky-Rosen steering
- 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
- Squeezing and multimode entanglement of surface acoustic wave phonons
- Operational quantification of continuous-variable quantum resources
- Quantum Entropy and Central Limit Theorem
- Witnessing Wigner Negativity
- Nonlinearity as a resource for nonclassicality in anharmonic systems
- Fast simulation of bosonic qubits via Gaussian functions in phase space
- Benchmarking of Gaussian boson sampling using two-point correlators
- Conditional non-Gaussian quantum state preparation
- Error mitigation and quantum-assisted simulation in the error corrected regime
- Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
- Characterization of an operational quantum resource in a critical many-body system
- Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
- Quantum Wigner entropy
- 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
- Quantum non-Gaussianity of light and atoms
- Classical simulation of Gaussian quantum circuits with non-Gaussian input states
- Fast estimation of outcome probabilities for quantum circuits
- Optimization of networks for measurement-based quantum computation
- Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
- Neural networks for detecting multimode Wigner-negativity
- Advances in Bosonic Quantum Error Correction with Gottesman-Kitaev-Preskill Codes: Theory, Engineering and Applications
- The first law of general quantum resource theories
- 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
- Non-Gaussian Nature and Entanglement of Spontaneous Parametric Nondegenerate Triple-Photon Generation
- Efficient simulatability of continuous-variable circuits with large Wigner negativity
- A single -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
- Dynamics-Based Entanglement Witnesses for Non-Gaussian States of Harmonic Oscillators
- Quantumness of spin-1 states
- Generalized concurrence in boson sampling
- Stabilizer information inequalities from phase space distributions
- Resource theory of quantum uncomplexity
- Further extensions of Clifford circuits and their classical simulation complexities
- Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
- Theory of genuine tripartite nonlocality of Gaussian states
- Noiseless conditional teleportation of a single photon
- Qutrit and Ququint Magic States
- Wigner negativity in spin- systems
- Wigner negativity in the steady-state output of a Kerr parametric oscillator
- Gaussification through decoherence
- Constraints on magic state protocols from the statistical mechanics of Wigner negativity
- Quantum Advantage in Information Retrieval
- Quantifying non-stabilizerness via information scrambling
- Quantifying dynamical magic with completely stabilizer preserving operations as free
- Numerical study of Wigner negativity in one-dimensional steady-state resonance fluorescence
- Enhanced continuous generation of non-Gaussianity through optomechanical modulation
- 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 arbitrary waveform generator
- Cubic nonlinear squeezing and its decoherence
- Quantum data hiding with continuous variable systems
- Characterization of phase-averaged coherent states
- Quantification of Wigner Negativity Remotely Generated via Einstein-Podolsky-Rosen Steering
- Negative Wigner function at telecommunication wavelength from homodyne detection
- Quantum backflow effect and nonclassicality
- Magic State Distillation with the Ternary Golay Code
- Dirac open quantum system dynamics: formulations and simulations
- Generation of quantum states with nonlinear squeezing by Kerr nonlinearity
- Steady-state generation of Wigner negative states in 1D resonance fluorescence
- Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
- Revealing quantum correlation by negativity of the Wigner function
- Photon-phonon-photon transfer in optomechanics
- Quantifying non-Gaussianity of a quantum state by the negative entropy of quadrature distributions
- The role of cohomology in quantum computation with magic states
- Steady-state generation of negative-Wigner-function light using feedback
- Adaptive loop-based subtraction of a single photon from a traveling beam of light
- Interaction signatures and non-Gaussian photon states from a strongly driven atomic ensemble coupled to a nanophotonic waveguide
- Simulation of quantum optics by coherent state decomposition
- A direct approach to Gaussian measurement based quantum computation
- Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
- 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
- Nonclassical steering and the Gaussian steering triangoloids
- Conditional nonclassical field generation in cavity QED
- Tensor eigenvalues and entanglement of symmetric states
- The axiomatic and the operational approaches to resource theories of magic do not coincide
- Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
- Subtraction and Addition of Propagating Photons by Two-Level Emitters
- The vacuum provides quantum advantage to otherwise simulatable architectures
- Loss of non-Gaussianity for damped photon-subtracted thermal states
- Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
- Detecting Einstein-Podolsky-Rosen steering in non-Gaussian spin states from conditional spin-squeezing parameters
- Creation of non-classical states of light in a chiral waveguide
- Witnessing negativity of Wigner function by estimating fidelities of cat-like states from homodyne measurements
- Sharp complexity phase transitions generated by entanglement
- Deterministic nonclassicality for quantum mechanical oscillators in thermal states
- Likelihood-free methods for quantum parameter estimation
- Are all Gaussian states also cluster states? Essential diagnostic tools for continuous-variable one-way quantum computing
- Classical simulation of non-Gaussian bosonic circuits
- Dual form of the phase-space classical simulation problem in quantum optics
- 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
- Homodyne detection of non-Gaussian quantum steering
- Exact and Efficient Simulation of Concordant Computation
- Absence of localization in two-dimensional Clifford circuits
- Unconditional generation of bright coherent non-Gaussian light from exciton-polariton condensates
- Stoquasticity in circuit QED
- 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
- Contextual bound states for qudit magic state distillation
- Semiclassical Formulation of Gottesman-Knill and Universal Quantum Computation
- Noise thresholds for classical simulability of non-linear Boson sampling
- Taming numerical errors in simulations of continuous variable non-Gaussian state preparation
- Deterministic multi-mode nonlinear coupling for quantum circuits
- Limitations of Classically-Simulable Measurements for Quantum State Discrimination
- Phase-space negativity as a computational resource for quantum kernel methods
- Fast Generation of High-Fidelity Mechanical Non-Gaussian States via Additional Amplifier and Photon Subtraction
- Generation of multi-photon Fock states at telecommunication wavelength using picosecond pulsed light
- Simulating macroscopic quantum correlations in linear networks
- Faster Born probability estimation via gate merging and frame optimisation
- Certification of non-Gaussian Einstein-Podolsky-Rosen Steering
- Algorithmic quantum simulation of memory effects
- Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
- From the Bloch sphere to phase space representations with the Gottesman-Kitaev-Preskill encoding
- Snapshotting Quantum Dynamics at Multiple Time Points
- Efficient detection of nonclassicality using moments of the Wigner function
- Conditional preparation of non-Gaussian quantum optical states by mesoscopic measurement
- Non-classicality of positive relativistic Wigner function
- Maximal Magic for Two-qubit States
- Wigner distribution of Sine Gordon and Kink solitons
- Assisted metrology and preparation of macroscopic superpositions with split spin-squeezed states
- Clifford operations and homological codes for rotors and oscillators
- Classical simulation and quantum resource theory of non-Gaussian optics
- Genuine Multipartite Entanglement induced by a Thermal Acoustic Reservoir
- Convex roofs witnessing Kirkwood-Dirac nonpositivity
- Measurement Contextuality and Planck's Constant
- Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
- Optimal sensing of photon addition and subtraction on nonclassical light
- Toolbox for non-classical state calculations
- Classical codes in quantum state space
- Classical simulability of constant-depth linear-optical circuits with noise
- Quantum Bochner's theorem for phase spaces built on projective representations
- On Quantum Steering and Wigner Negativity
- Statistical Mechanics of Stochastic Quantum Control: -adic Rényi Circuits
- Efficient computations of quantum canonical Gibbs state in phase space
- Mode-selective single-photon addition to a multimode quantum field
- Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
- Two-mode light states before and after delocalized single-photon addition
- The Quantum Density Matrix and its many uses: From quantum structure to quantum chaos and noisy simulators
- Approximating outcome probabilities of linear optical circuits
- 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 Quantum Computation
- Persistent non-Gaussian correlations in out-of-equilibrium Rydberg atom arrays
- Bosonic data hiding: power of linear vs non-linear optics
- Quasiprobability distributions with weak measurements
- Quantifying athermality and quantum induced deviations from classical fluctuation relations
- Wigner's Theorem for stabilizer states and quantum designs
- 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
- Adapting coherent-state superpositions in noisy channels
- Fundamental limitations to key distillation from Gaussian states with Gaussian operations
- Steady-state tripartite non-Gaussian entanglement and steering in output field from intracavity triple-photon parametric downconversion
- Quadrature Coherence Scale of Linear Combinations of Gaussian Functions in Phase Space
- Tsirelson inequalities: Detecting cheating and quantumness in a single framework
- Gaussian boson sampling at finite temperature
- Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
- Gleipnir: Toward Practical Error Analysis for Quantum Programs (Extended Version)
- Polytopes of Absolutely Wigner Bounded Spin States
- Exploring the possibility of a complex-valued non-Gaussianity measure for quantum states of light
- Coupled three-mode squeezed vacuum: Gaussian steering and remote generation of Wigner negativity
- Wigner-negative states in the steady-state emission of a two-level system driven by squeezed light
- 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
- Grand Unification of All Discrete Wigner Functions on Phase Space
- Quantum advantage in temporally flat measurement-based quantum computation
- Detecting single photons is not always necessary to evidence interference of photon probability amplitudes
- Unveiling Vacuum Fluctuations and Nonclassical States with Cavity-Enhanced Tripartite Interactions
- Continuous Variable Quantum Advantages and Applications in Quantum Optics
- Stellar representation of extremal Wigner-negative spin states
- Wigner formalism for a particle on an infinite lattice: dynamics and spin
- Path superposition activating perfect quantum teleportation ability for separable states
- Witnessing non-classicality through large deviations in quantum optics
- General entropic constraints on CSS codes within magic distillation protocols
- Sampling and the complexity of nature
- Wigner entropy conjecture and the interference formula in quantum phase space
- All non-Gaussian states are advantageous for channel discrimination: Robustness of non-convex continuous variable quantum resources
- Quantum computational advantage implies contextuality
- No real advantage of photon subtraction and displacement in continuous variable measurement device independent quantum key distribution
- Non-Gaussian state teleportation with a nonlinear feedforward
- Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
- Subcycle tomography of quantum light
- Enhancement of non-Stabilizerness within Indefinite Causal Order
- Probing Kirkwood-Dirac nonpositivity and its operational implications via moments
- Sufficient Wigner Negativity Implies Genuine Multipartite Entanglement
- On the stabilizer complexity of Hawking radiation
- Nonclassicality in a dispersive atom-cavity field interaction in presence of an external driving field
- Robust Negativity in the Quantum-to-Classical Transition of Kerr Dynamics
- Probing information theoretic measures of nonlinear ultracold quantum gases using phase-space distributions
- Understanding Squeezed States of Light Through Wigner's Phase-Space
- Majorization theoretical approach to entanglement enhancement via local filtration
- On overall measure of non-classicality of -level quantum system and its universality in the large limit
- Measuring High-Order Phonon Correlations in an Optomechanical Resonator
- The Interplay between Quantum Contextuality and Wigner Negativity
- Dynamical complexity of non-Gaussian many-body systems with dissipation
- Pinching operators for approximating multiphoton entangled states
- Optical Quantum Computing
- Circuit connectivity boosts by quantum-classical-quantum interfaces
- Deterministic Gaussian conversion protocols for non-Gaussian single-mode resources
- Twisted Fourier analysis and pseudo-probability distributions
- Filter functions for the Glauber-Sudarshan -function regularization
- From Quantum Optics to Quantum Technologies
- Coherent LQG Control, Free-Carrier Oscillations, Optical Ising Machines and Pulsed OPO Dynamics
- Continuous Generation and Stabilization of Mesoscopic Field Superposition States in a Quantum Circuit
- Resourcefulness of non-classical continuous-variable quantum gates
- 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
- Monte Carlo Quantum Computing
- Non-Gaussianity from superselection rules