Universität zu Köln

Hangleiter, Dominik ORCID: 0000-0002-4766-7967, Kliesch, Martin, Eisert, Jens ORCID: 0000-0003-3033-1292 and Gogolin, Christian (2019). Sample Complexity of Device-Independently Certified Quantum Supremacy. Phys. Rev. Lett., 122 (21). COLLEGE PK: AMER PHYSICAL SOC. ISSN 1079-7114

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Hangleiter, Dominik UNSPECIFIED orcid.org/0000-0002-4766-7967 UNSPECIFIED Kliesch, Martin UNSPECIFIED UNSPECIFIED UNSPECIFIED Eisert, Jens UNSPECIFIED orcid.org/0000-0003-3033-1292 UNSPECIFIED Gogolin, Christian UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-147764
DOI:	10.1103/PhysRevLett.122.210502
Journal or Publication Title:	Phys. Rev. Lett.
Volume:	122
Number:	21
Date:	2019
Publisher:	AMER PHYSICAL SOC
Place of Publication:	COLLEGE PK
ISSN:	1079-7114
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language CIRCUITS; COMPUTATION; ALGORITHMS Multiple languages Physics, Multidisciplinary Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/14776