Phase space simulation method for quantum computation with magic states on qubits

Abstract

We propose a method for classical simulation of finite-dimensional quantum systems, based on sampling from a quasiprobability distribution, i.e., a generalized Wigner function. Our construction applies to all finite dimensions, with the most interesting case being that of qubits. For multiple qubits, we find that quantum computation by Clifford gates and Pauli measurements on magic states can be efficiently classically simulated if the quasiprobability distribution of the magic states is non-negative. This provides the so far missing qubit counterpart of the corresponding result [V. Veitch et al., New J. Phys. 14, 113011 (2012)] applying only to odd dimension. Our approach is more general than previous ones based on mixtures of stabilizer states. Namely, all mixtures of stabilizer states can be efficiently simulated, but for any number of qubits there also exist efficiently simulable states outside the stabilizer polytope. Further, our simulation method extends to negative quasiprobability distributions, where it provides amplitude estimation. The simulation cost is then proportional to a robustness measure squared. For all quantum states, this robustness is smaller than or equal to robustness of magic.

24 pages, 4 tables, 7 figures

References in corpus (34)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Hidden Variables and the Two Theorems of John Bell
• Contextuality for preparations, transformations, and unsharp measurements
• Contextuality supplies the magic for quantum computation
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Positive Wigner functions render classical simulation of quantum computation efficient
• The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Discrete phase space based on finite fields
• Negative Quasi-Probability as a Resource for Quantum Computation
• The general structure of quantum resource theories
• Hudson's Theorem for finite-dimensional quantum systems
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Contextuality as a resource for models of quantum computation on qubits
• Wigner function negativity and contextuality in quantum computation on rebits
• Discrete Wigner functions and quantum computational speedup
• Contextuality and Wigner function negativity in qubit quantum computation
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• A General Theory of Phase-Space Quasiprobability Distributions
• Equivalence between contextuality and negativity of the Wigner function for qudits
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Quantum Advantage from Sequential-Transformation Contextuality
• From estimation of quantum probabilities to simulation of quantum circuits
• Permutation Symmetry Determines the Discrete Wigner Function
• Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers
• Nonnegative subtheories and quasiprobability representations of qubits
• Optimal classical simulation of state-independent quantum contextuality
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Quantum Contextuality with Stabilizer States
• Contextuality bounds the efficiency of classical simulation of quantum processes
• $\psi$-epistemic interpretations of quantum theory have a measurement problem
• A Contextual $\psi$-Epistemic Model of the $n$-Qubit Stabilizer Formalism

Cited by in corpus (52)

• Measurement reduction in variational quantum algorithms
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• General probabilistic theories: An introduction
• A hidden variable model for universal quantum computation with magic states on qubits
• Critical behaviors of non-stabilizerness in quantum spin chains
• 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
• A single $T$-gate makes distribution learning hard
• Contextuality of general probabilistic theories
• Contextual Subspace Variational Quantum Eigensolver
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Classical simulation of non-Gaussian fermionic circuits
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Noncontextuality Inequalities from Antidistinguishability
• The role of cohomology in quantum computation with magic states
• A stabilizer framework for Contextual Subspace VQE and the noncontextual projection ansatz
• Simulation of quantum optics by coherent state decomposition
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Contextual Subspace Variational Quantum Eigensolver Calculation of the Dissociation Curve of Molecular Nitrogen on a Superconducting Quantum Computer
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Sharp complexity phase transitions generated by entanglement
• Unitary Partitioning and the Contextual Subspace Variational Quantum Eigensolver
• Attoscience in Phase Space
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Non-Classical Kernels in Continuous Variable Systems
• A classical formulation of quantum theory?
• Extending Quantum Computing through Subspace, Embedding and Classical Molecular Dynamics Techniques
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Connecting XOR and XOR* games
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Wigner's Theorem for stabilizer states and quantum designs
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• A quantum prediction as a collection of epistemically restricted classical predictions
• Gleipnir: Toward Practical Error Analysis for Quantum Programs (Extended Version)
• Simulating quantum computation: how many "bits" for "it"?
• Contextuality Can be Verified with Noncontextual Experiments
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• General entropic constraints on CSS codes within magic distillation protocols
• Symmetries and Wigner representations of operational theories
• Quantum formalism on the plane: POVM-Toeplitz quantization, Naimark theorem and linear polarisation of the light
• Characterization of non-adaptive Clifford channels
• How contextuality and antidistinguishability are related
• Almost no experiments have classical Kirkwood-Dirac representations
• Twisted Fourier analysis and pseudo-probability distributions
• Noncontextual Pauli Hamiltonians
• Convexity of noncontextual wirings and how they order the set of correlations
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states
• Efficient classical simulation of cluster state quantum circuits with alternative inputs