dc.contributor.author
Hangleiter, Dominik
dc.contributor.author
Kliesch, Martin
dc.contributor.author
Eisert, Jens
dc.contributor.author
Gogolin, Christian
dc.date.accessioned
2019-11-06T09:32:53Z
dc.date.available
2019-11-06T09:32:53Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/25885
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-25646
dc.description.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.
en
dc.format.extent
18 Seiten
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
boson sampling
en
dc.subject
quantum benchmarking
en
dc.subject
quantum computation
en
dc.subject
information architectures
en
dc.subject
quantum protocols
en
dc.subject
quantum simulation
en
dc.subject
quantum information
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::530 Physik::539 Moderne Physik
dc.title
Sample complexity of device-independently certified “quantum supremacy”
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation.articlenumber
210502
dcterms.bibliographicCitation.doi
10.1103/PhysRevLett.122.210502
dcterms.bibliographicCitation.journaltitle
Physical review letters
dcterms.bibliographicCitation.number
21
dcterms.bibliographicCitation.volume
122
dcterms.bibliographicCitation.url
https://doi.org/10.1103/PhysRevLett.122.210502
refubium.affiliation
Physik
refubium.affiliation.other
Institut für Theoretische Physik
refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.issn
0031-9007
dcterms.isPartOf.eissn
1079-7114