Sample Complexity of Device-Independently Certified "quantum Supremacy"

Hangleiter D, Kliesch M, Eisert J, Gogolin C (2019)

Publication Type: Journal article

Publication year: 2019

Journal

Physical Review Letters American Physical Society

Book Volume: 122

Article Number: 210502

Journal Issue: 21

DOI: 10.1103/PhysRevLett.122.210502

Abstract

Results on the hardness of approximate sampling are seen as important stepping stones toward a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, instantaneous quantum polynomial time (IQP) circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any noninteractive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results, namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.

Involved external institutions

Freie Universität Berlin DE Germany (DE) Heinrich-Heine-Universität Düsseldorf DE Germany (DE) Autonomous University of Barcelona (UAB) / Universitat Autònoma de Barcelona ES Spain (ES)

How to cite

APA:

Hangleiter, D., Kliesch, M., Eisert, J., & Gogolin, C. (2019). Sample Complexity of Device-Independently Certified "quantum Supremacy". Physical Review Letters, 122(21). https://doi.org/10.1103/PhysRevLett.122.210502

MLA:

Hangleiter, Dominik, et al. "Sample Complexity of Device-Independently Certified "quantum Supremacy"." Physical Review Letters 122.21 (2019).

BibTeX: Download