Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling

Abstract

Bounding the cost of classically simulating the outcomes of universal quantum circuits to additive error δ is often called weak simulation and is a direct way to determine when they confer a quantum advantage. Weak simulation of the T+Clifford gateset is BQP -complete and is expected to scale exponentially with the number t of T gates. We constructively tighten the upper bound on the worst-case L1 norm sampling cost to next order in t from O(ξ δ) if δ ≫ ξ to O((ξ−t)δ) if δ ≫ (ξ− t), where ξ = 2 is the stabilizer extent of the t-tensored T gate magic state. We accomplish this by replacing independent L1 sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated L1 sampling. As an aside, this result demonstrates that the T gate magic state’s approximate stabilizer state decomposition is not multiplicative with respect to t, for finite values, despite the multiplicativity of its stabilizer extent. This is the first weak simulation algorithm that has lowered this bound’s dependence on finite t in the worst-case to our knowledge and establishes how to obtain further such reductions in t.