Rostock 2019 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

Q: Fachverband Quantenoptik und Photonik

Q 44: Quantum Information (Concepts and Methods) III

Q 44.7: Vortrag

Donnerstag, 14. März 2019, 12:00–12:15, S HS 001 Chemie

Sample complexity of device-independently certified ``quantum supremacy — •Dominik Hangleiter¹, Martin Kliesch², Jens Eisert¹, and Christian Gogolin³ — ¹Freie Universität Berlin, 14195 Berlin — ²Heinrich Heine Universität Düsseldorf, 40225 Düsseldorf — ³Universität Köln, 50937 Köln

Results on the hardness of approximate sampling are seen as important stepping stones towards a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, 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 non-interactive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. It is an ironic twist of our results that the same property that is a central ingredient for the approximate hardness results, prohibits sample-efficient certification: namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.