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.