"Quantum Supremacy" and the Complexity of Random Circuit Sampling

Authors Adam Bouland , Bill Fefferman , Chinmay Nirkhe , Umesh Vazirani



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.15.pdf
  • Filesize: 214 kB
  • 2 pages

Document Identifiers

Author Details

Adam Bouland
  • Electrical Engineering and Computer Sciences, University of California, Berkeley, 387 Soda Hall Berkeley, CA 94720, U.S.A.
Bill Fefferman
  • Electrical Engineering and Computer Sciences, University of California, Berkeley, 387 Soda Hall Berkeley, CA 94720, U.S.A. , Joint Center for Quantum Information and Computer Science (QuICS), University of Maryland/NIST, Bldg 224 Stadium Dr Room 3100, College Park, MD 20742, U.S.A.
Chinmay Nirkhe
  • Electrical Engineering and Computer Sciences, University of California, Berkeley, 387 Soda Hall Berkeley, CA 94720, U.S.A.
Umesh Vazirani
  • Electrical Engineering and Computer Sciences, University of California, Berkeley, 387 Soda Hall Berkeley, CA 94720, U.S.A.

Cite AsGet BibTex

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. "Quantum Supremacy" and the Complexity of Random Circuit Sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 15:1-15:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.15

Abstract

A critical goal for the field of quantum computation is quantum supremacy - a demonstration of any quantum computation that is prohibitively hard for classical computers. It is both a necessary milestone on the path to useful quantum computers as well as a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS). While RCS was defined with experimental realization in mind, we give strong complexity-theoretic evidence for the classical hardness of RCS, placing it on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS also satisfies an anti-concentration property, namely that errors in estimating output probabilities are small with respect to the probabilities themselves. This makes RCS the first proposal for quantum supremacy with both of these properties. We also give a natural condition under which an existing statistical measure, cross-entropy, verifies RCS, as well as describe a new verification measure which in some formal sense maximizes the information gained from experimental samples.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • quantum supremacy
  • average-case hardness
  • verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 2018. URL: http://dx.doi.org/10.1038/s41567-018-0318-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail