Efficient classical simulation of Clifford circuits with nonstabilizer input states

Abstract

We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states. First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the $l_1$ norm, of a large fraction of Clifford circuits. The running time of our algorithm decreases as the inputs become more mixed. Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured. This restriction depends on a magic monotone that we call the Pauli rank. We apply our results to give an efficient output probability approximation algorithm for some restricted quantum computation models, such as Clifford circuits with solely magic state inputs (CM), Pauli-based computation (PBC) and instantaneous quantum polynomial time (IQP) circuits.

arXiv comment4+12 pages, 3 figures

References in corpus (25)

• Quantum Computing in the NISQ era and beyond
• Quantum Teleportation is a Universal Computational Primitive
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• A Theory of Fault-Tolerant Quantum Computation
• On the Power of One Bit of Quantum Information
• Quantum Computational Supremacy
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• The Resource Theory of Stabilizer Computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Active stabilisation, quantum computation and quantum state synthesis
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• 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
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Diagonal gates in the Clifford hierarchy
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Anticoncentration theorems for schemes showing a quantum speedup
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Semi-Clifford operations, structure of ${\mathcal{C}}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation
• Efficient classical simulation of noisy quantum computation
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy

Cited by in corpus (31)

• Stim: a fast stabilizer circuit simulator
• Stabilizer entropies and nonstabilizerness monotones
• Phase transition in magic with random quantum circuits
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• On the statistical complexity of quantum circuits
• Resource theory of quantum scrambling
• Entanglement-magic separation in hybrid quantum circuits
• Quantum Entropy and Central Limit Theorem
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Quantum Non-Local Nonstabilizerness
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Effects of quantum resources on the statistical complexity of quantum circuits
• Magic of Random Matrix Product States
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Rademacher complexity of noisy quantum circuits
• Quantum Ruzsa Divergence to Quantify Magic
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Wasserstein Complexity of Quantum Circuits
• Rise and fall of nonstabilizerness via random measurements
• Improved Strong Simulation of Universal Quantum Circuits
• Efficient simulation of logical magic state preparation protocols
• On the Hardness of Measuring Magic
• Error-mitigated initialization of surface codes with non-Pauli stabilizers
• High-fidelity initialization a logical qubit with multiple injections
• Decoded Quantum Interferometry Under Noise
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources