More Optimal Simulation of Universal Quantum Computers

Abstract

Validating whether a quantum device confers a computational advantage often requires classical simulation of its outcomes. The worst-case sampling cost of $L_1$-norm based simulation has plateaued at $\le (2+\sqrt{2}){\xi }_t{\delta }^{-1}$ in the limit that $t\to \infty$, where $\delta$ is the additive error and ${\xi }_t$ is the stabilizer extent of a $t$-qubit magic state. We reduce this prefactor 68-fold by a leading-order reduction in $t$ through correlated sampling. The result exceeds even the average-case of the prior state-of-the-art and current simulators accurate to multiplicative error. Numerical demonstrations support our proofs. The technique can be applied broadly to reduce the cost of $L_1$ minimization.