Stabilizer extent is not multiplicative

Abstract

The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of logarithmically many stabilizer states. The runtime of the classical simulation is governed by the stabilizer extent, which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating largescale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.

15 pages, 1 figure

References in corpus (18)

• Lectures on 0/1-polytopes
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Hudson's Theorem for finite-dimensional quantum systems
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Contextuality as a resource for models of quantum computation on qubits
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Convex geometry of quantum resource quantification
• Phase space simulation method for quantum computation with magic states on qubits
• Contextuality as a resource for measurement-based quantum computation beyond qubits
• Qubit stabilizer states are complex projective 3-designs

Cited by in corpus (23)

• Many-body quantum magic
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Nonstabilizerness via matrix product states in the Pauli basis
• Non-stabilizerness versus entanglement in matrix product states
• Nonstabilizerness of Permutationally Invariant Systems
• Lie-algebraic classical simulations for quantum computing
• Classical simulation of non-Gaussian fermionic circuits
• Stabilizer disentangling of conformal field theories
• Chaos and magic in the dissipative quantum kicked top
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Nonstabilizerness of a Boundary Time Crystal
• Extracting randomness from magic quantum states
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Fermionic Magic Resources of Quantum Many-Body Systems
• Classical simulation and quantum resource theory of non-Gaussian optics
• Non-stabilizerness in quantum-enhanced metrological protocols
• Certifying nonstabilizerness in quantum processors
• Faster computation of nonstabilizerness
• Quantifying magic via quantum $(\alpha ,\beta )$ Jensen-Shannon divergence
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits