Improved Strong Simulation of Universal Quantum Circuits

Abstract

We find a scaling reduction in the stabilizer rank of the twelve-qubit tensored $T$ gate magic state. This lowers its asymptotic bound to $2^{\sim 0.463t}$ for multi-Pauli measurements on $t$ magic states, improving over the best previously found bound of $2^{\sim 0.468t}$. We numerically demonstrate this reduction. This constructively produces the most efficient strong simulation algorithm of the Clifford+$T$ gateset to relative or multiplicative error. We then examine the cost of Pauli measurement in terms of its Gauss sum rank, which is a slight generalization of the stabilizer rank and is a lower bound on its asymptotic scaling. We demonstrate that this lower bound appears to be tight at low $t$-counts, which suggests that the stabilizer rank found at the twelve-qubit state can be lowered further to $2^{\sim 0.449t}$ and we prove and numerically show that this is the case for single-Pauli measurements. Our construction directly shows how the reduction at $12$ qubits is iteratively based on the reduction obtained at $6$, $3$, $2$, and $1$ qubits. This explains why novel reductions are found at tensor factors for these number of qubit primitives, an explanation lacking previously in the literature. Furthermore, in the process we observe an interesting relationship between the T gate magic state's stabilizer rank and decompositions that are Clifford-isomorphic to a computational sub-basis tensored with single-qubit states that produce minimal unique stabilizer state inner products -- the same relationship that allowed for finding minimal numbers of unique Gauss sums in the odd-dimensional qudit Wigner formulation of Pauli measurements.

References in corpus (22)

• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Computational Supremacy
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Quantum interference as a resource for quantum speedup
• Unbiased Simulation of Near-Clifford Quantum Circuits
• From estimation of quantum probabilities to simulation of quantum circuits
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Explicit lower bounds on strong quantum simulation
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Feynman-path type simulation using stabilizer projector decomposition of unitaries

Cited by in corpus (2)

• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• Improved upper bounds on the stabilizer rank of magic states