The Complexity and Verification of Quantum Random Circuit Sampling

Published

October 29, 2018

Author(s)

Adam Bouland, William J. Fefferman, Chinmay Nirkhe, Umesh Vazirani

Abstract

A critical milestone on the path to useful quantum computers is the demonstration of a quantum computation that is prohibitively hard for classical computers -- a task referred to as quantum supremacy. A leading near-term candidate is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). RCS was defined with experimental realizations in mind, leaving its computational hardness unproven. Here we give strong complexity-theoretic evidence of 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, which is critical to establishing computational hardness in the presence of experimental noise. 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. Finally, 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.

Citation

Nature Physics

Volume

14

Pub Type

Journals

Download Paper

https://doi.org/10.1038/s41567-018-0318-2

Local Download

Keywords

Random Circuit Sampling, RCS, quantum circuits

Citation

Bouland, A. , Fefferman, W. , Nirkhe, C. and Vazirani, U. (2018), The Complexity and Verification of Quantum Random Circuit Sampling, Nature Physics, [online], https://doi.org/10.1038/s41567-018-0318-2, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=927073 (Accessed April 18, 2024)