Improved upper bounds on the stabilizer rank of magic states

Abstract

In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|T⟩={\sqrt{2}}^{-1}(|0⟩+e^{i\pi /4}|1⟩)$ in the limit of large $m$. In particular, we show that $|T{⟩}^{\otimes m}$ can be exactly expressed as a superposition of at most $O(2^{\alpha m})$ stabilizer states, where $\alpha \le 0.3963$, improving on the best previously known bound $\alpha \le 0.463$. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an $n$-qubit Clifford + T circuit $U$ with $m$ uses of the T gate to within a given inverse polynomial relative error using a runtime $\mathrm{poly}(n,m)2^{\alpha m}$. We also provide improved upper bounds on the stabilizer rank of symmetric product states $|\psi {⟩}^{\otimes m}$ more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $\text{poly}(n,m)2^{m/2}$. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.

arXiv commentA preliminary version of our results was reported in the first author's Ph.D thesis

References in corpus (9)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• 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
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Lower bounds on the non-Clifford resources for quantum computations
• Lower Bounds on Stabilizer Rank
• Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count
• Improved Strong Simulation of Universal Quantum Circuits

Cited by in corpus (29)

• Computational advantage of quantum random sampling
• Measuring magic on a quantum processor
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
• Thrifty shadow estimation: re-using quantum circuits and bounding tails
• A single $T$-gate makes distribution learning hard
• How to simulate quantum measurement without computing marginals
• Stabilizer Tensor Networks with Magic State Injection
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Lower Bounds on Stabilizer Rank
• Faster Born probability estimation via gate merging and frame optimisation
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• New techniques for bounding stabilizer rank
• Lower T-count with faster algorithms
• Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation
• Finding maximal quantum resources
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models
• Non-stabilizerness and entanglement from cat-state injection
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Fast Classical Simulation of Quantum Circuits via Parametric Rewriting in the ZX-Calculus
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits