Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
arXiv:2307.16688 · doi:10.1103/PhysRevLett.133.220601
Abstract
The Wigner function formalism has played a pivotal role in examining the non-classical aspects of quantum states and their classical simulatability. Nevertheless, its application in qubit systems faces limitations due to negativity induced by Clifford gates. In this work, we propose a novel classical simulation method for qubit Clifford circuits based on the framed Wigner function, an extended form of the Wigner function with an additional phase degree of freedom. In our framework, Clifford gates do not induce negativity by switching to a suitable frame; thereby, a wide class of nonstabilizer states can be represented positively. By leveraging this technique, we show that some marginal outcomes of Clifford circuits with nonstabilizer state inputs can be efficiently sampled at polynomial time and memory costs. We develop a graph-theoretical approach to identify classically simulatable marginal outcomes and apply it to log-depth random Clifford circuits. We also present the outcome probability estimation scheme using the framed Wigner function and discuss its precision. Our approach opens new avenues for utilizing quasi-probabilities to explore classically simulatable quantum circuits.
5+16 pages, 6 figures
References in corpus (33)
- Efficient classical simulation of slightly entangled quantum computations
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Improved Simulation of Stabilizer Circuits
- Measurement-Induced Phase Transitions in the Dynamics of Entanglement
- Positive Wigner functions render classical simulation of quantum computation efficient
- 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
- Hudson's Theorem for finite-dimensional quantum systems
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Efficient classical simulation of random shallow 2D quantum circuits
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Contextuality and Wigner function negativity in qubit quantum computation
- Hadamard-free circuits expose the structure of the Clifford group
- Decoupling with random quantum circuits
- Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
- Phase space simulation method for quantum computation with magic states on qubits
- Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
- From estimation of quantum probabilities to simulation of quantum circuits
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- Improved upper bounds on the stabilizer rank of magic states
- A hidden variable model for universal quantum computation with magic states on qubits
- Quantum advantage of unitary Clifford circuits with magic state inputs
- Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
- Quantum circuits and low-degree polynomials over F_2
- Classical simulation of quantum circuits by half Gauss sums
- Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
- Faster Born probability estimation via gate merging and frame optimisation
- Simulating quantum computation: how many "bits" for "it"?