Rostock 2019 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

Q: Fachverband Quantenoptik und Photonik

Q 44: Quantum Information (Concepts and Methods) III

Q 44.7: Talk

Thursday, March 14, 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.