A Caltech Library Service

Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones

Seddon, James R. and Regula, Bartosz and Pashayan, Hakop and Ouyang, Yingkai and Campbell, Earl T. (2021) Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones. PRX Quantum, 2 (1). Art. No. 010345. ISSN 2691-3399. doi:10.1103/prxquantum.2.010345.

PDF - Published Version
Creative Commons Attribution.

PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Seddon, James R.0000-0002-6059-4125
Regula, Bartosz0000-0001-7225-071X
Pashayan, Hakop0000-0003-3782-7602
Ouyang, Yingkai0000-0003-1115-0074
Campbell, Earl T.0000-0002-3903-2734
Additional Information:© 2021 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. Received 13 March 2020; revised 11 September 2020; accepted 22 February 2021; published 18 March 2021. We would like to thank the anonymous reviewers for their insightful comments. This work is supported by the Engineering and Physical Sciences Research Council [Grants No. EP/P510270/1 (J.R.S.) and No. EP/M024261/1 (E.T.C. and Y.O.)]. B.R. is supported by the Presidential Postdoctoral Fellowship from Nanyang Technological University, Singapore. Research at Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Colleges and Universities. H.P. also acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) discovery Grants [RGPIN-2019-04198] and [RGPIN-2018-05188] and the ARC via the Centre of Excellence in Engineered Quantum Systems (EQUS) Project No. CE170100009. This work was completed while E.T.C. was at the University of Sheffield.
Group:AWS Center for Quantum Computing
Funding AgencyGrant Number
Engineering and Physical Sciences Research Council (EPSRC)EP/P510270/1
Engineering and Physical Sciences Research Council (EPSRC)EP/M024261/1
Nanyang Technological UniversityUNSPECIFIED
Department of Innovation, Science and Economic Development (Canada)UNSPECIFIED
Ontario Ministry of Colleges and UniversitiesUNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)RGPIN-2019-04198
Natural Sciences and Engineering Research Council of Canada (NSERC)RGPIN-2018-05188
Australian Research CouncilCE170100009
Issue or Number:1
Record Number:CaltechAUTHORS:20210421-155541079
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108792
Deposited By: Tony Diaz
Deposited On:22 Apr 2021 19:04
Last Modified:22 Apr 2021 19:04

Repository Staff Only: item control page