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 \rightarrow \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.
Categories: quant-ph