Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations

Abstract

We show that the cost of strong simulation of quantum circuits using $t$ $T$ gate magic states exhibits non-trivial reductions on its upper bound for $t=1$, $t=2$, $t=3$, and $t=6$ with odd-prime-qudits. This agrees with previous numerical bounds found for qubits. We define simulation cost by the number of terms that require Gaussian elimination of a $t\times t$ matrix and so capture the cost of simulation methods that proceed by computing stabilizer inner products or evaluating quadratic Gauss sums. Prior numerical searchs for qubits were unable to converge beyond $t=7$. We effectively increase the space searched for these non-trivial reductions by $>10^{10^4}$ and extend the bounds to $t=14$ for qutrits. This is accomplished by using the Wigner-Weyl-Moyal formalism to algebraically find bounds instead of relying on numerics. We find a new reduction in the upper bound from the $12$-qutrit magic state of $3^{\sim 0.469t}$, which improves on the bound obtained from the $6$-qutrit magic state of $3^{\sim 0.482t}$.

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Quantum Computational Supremacy
• 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
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Qudit versions of the qubit "pi-over-eight" gate
• The Weyl representation on the torus
• Standard Form of Qudit Stabilizer Groups
• Non-negative Wigner functions in prime dimensions
• Classical algorithms for quantum mean values
• Quantization of multidimensional cat maps
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits

Cited by in corpus (5)

• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• Faster Born probability estimation via gate merging and frame optimisation
• Improved Strong Simulation of Universal Quantum Circuits
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums