Multi-Pauli measurements on magic states is one way to formulate universal quantum computing. We lower the asymptotic bound to 2^{∼0.463t} for multi-Pauli measurements on t magic states, improving over the best previously found bound of 2^{∼0.468t}. This not only improves our understanding of the difficulty of classically simulating quantum circuits, but also results in the most efficient algorithm to-date for doing strong simulation of universal quantum circuits using Clifford + T gates.

Our reduction breaks through a long-standing lull in progress in the community in lowering the exponential cost of classically simulating a quantum circuit’s output probability distribution, allowing larger quantum computers to be classically verified and validated.

For details see

“Improved Strong Simulation of Universal Quantum Circuits”, L. Kocia, arXiv:2012.11739.