• Open Access

Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones

James R. Seddon, Bartosz Regula, Hakop Pashayan, Yingkai Ouyang, and Earl T. Campbell
PRX Quantum 2, 010345 – Published 18 March 2021

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
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)

Quantum Information, Science & Technology

Authors & Affiliations

James R. Seddon1,*, Bartosz Regula2,†, Hakop Pashayan3,4,5, Yingkai Ouyang6, and Earl T. Campbell6,7,†

  • 1Department of Physics and Astronomy, University College London, London, United Kingdom
  • 2School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore
  • 3Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Ontario N2L 3G1, Canada
  • 4Perimeter Institute for Theoretical Physics, Waterloo, Ontario N2L 2Y5 Canada
  • 5Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, New South Wales 2006, Australia
  • 6Department of Physics & Astronomy, University of Sheffield, Sheffield S3 7RH, United Kingdom
  • 7AWS Center for Quantum Computing, Pasadena, California 91125, USA

  • *jseddonquantum@gmail.com
  • bartosz.regula@gmail.com
  • earltcampbell@gmail.com

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.

Key Image

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 2, Iss. 1 — March - May 2021

Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from PRX Quantum

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×