Quantifying quantum speedups: improved classical simulation from tighter magic monotones

Understand

Consumption of magic states promotes the stabilizer model of computation to universal quantum computation.

• Here, we propose three different classical algorithms for simulating such universal quantum circuits, and characterize them by establishing precise connections with a family of magic monotones.
• Our first simulator introduces a new class of quasiprobability distributions and connects its runtime to a generalized notion of negativity.
• We prove that this algorithm has significantly improved exponential scaling compared to all prior quasiprobability simulators for qubits.