Abstract
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. Our second simulator is a new variant of the stabilizer-rank simulation algorithm, extended to work with mixed states and with significantly improved runtime bounds. Our third simulator trades precision for speed by discarding negative quasiprobabilities. We connect each algorithm’s performance to a corresponding magic monotone and, by comprehensively characterizing the monotones, we obtain a precise understanding of the simulation runtime and error bounds. Our analysis reveals a deep connection between all three seemingly unrelated simulation techniques and their associated monotones. For tensor products of single-qubit states, we prove that our monotones are all equal to each other, multiplicative and efficiently computable, allowing us to make clear-cut comparisons of the simulators’ performance scaling. Furthermore, our monotones establish several asymptotic and nonasymptotic bounds on state interconversion and distillation rates. Beyond the theory of magic states, our classical simulators can be adapted to other resource theories under certain axioms, which we demonstrate through an explicit application to the theory of quantum coherence.
5 More- Received 13 March 2020
- Revised 11 September 2020
- Accepted 22 February 2021
DOI:https://doi.org/10.1103/PRXQuantum.2.010345
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
Some computational tasks (such as factorization) can be solved exponentially faster on a quantum computer compared to the best-known classical algorithm. Consequently, we expect that classically simulating a general quantum computation will need exponentially more computational resources (such as the runtime of the simulation or amount of memory) than would be needed to run the computation on a quantum device.
However, not all quantum computational tasks exhibit this exponential classical cost of simulation. A key example is a phenomenologically rich subset of quantum computations known as the stabilizer circuits. These quantum computations can be simulated on a classical computer using only polynomially, rather than exponentially, scaling classical resources. This computationally limited subset can be promoted to the full power of unrestricted quantum computers by adding the so-called “magic states” to stabilizer circuits. In this way, magic states can be viewed as a computational resource that promotes classical to quantum computational power. Here we undertake a rigorous study of different ways to quantify such computational resources.
Our work shows that two key approaches to classical simulation of quantum computers are closely connected and allows us to compare their runtimes. Additionally, we develop state-of-the-art algorithms, which employ magic states for the classical simulation of quantum computation. This provides a reliable, presently available, and inexpensive means to simulate small quantum systems with important applications.