Classical simulation of quantum circuits using fewer Gaussian eliminations

A compelling way to quantify the separation between classical and quantum computing is to determine how many $T$-gate magic states, $t$, a classical computer must simulate to calculate the probability of a universal quantum circuit's output. Unfortunately, efforts to determine the minimum number of stabilizer state inner products necessary to decompose $T$-gate magic states (${\chi }_t$) have proven intractable past $t=7$. By using a phase space formalism based on Wootters' discrete Weyl operator basis over a finite field, we develop an algebraic approach to determining ${\chi }_t$ for single-Pauli measurements. This allows us to extend the bounds on ${\chi }_t$ to $t=14$ for qutrits, effectively increasing the space searched by $>{10}^{{10}^4}$. Our results show that by using such phase space methods it is possible to validate noisy intermediate-scale quantum circuits of larger size than previously thought possible.

Figure 1

Monte Carlo search for the stabilizer rank of the 3-qutrit $T$-gate magic state.

Figure 2

Logarithm (base 10) of the worst-case number of terms required to evaluate $P_k$ for qutrits in Eq. (2) for a Monte Carlo method based on Wigner negativity [23] (dashed curve) compared to the qutrit trivial tensor bound from ${\left({\xi }_1\right)}^t, {\left({\xi }_2\right)}^{t/2}, {\left({\xi }_6\right)}^{t/6}$, and ${\left({\xi }_{12}\right)}^{t/12}$ (solid curves).