Freiburg 2019 – scientific programme

Sessions | Days | Selection | Search | Updates | Downloads | Help

FM: Fall Meeting

FM 36: Quantum Computation: Benchmarking and Certification

FM 36.4: Talk

Tuesday, September 24, 2019, 15:00–15:15, 2006

Sample complexity of device-independently certified "quantum supremacy" — •Dominik Hangleiter¹, Martin Kliesch², Jens Eisert¹, and Christian Gogolin³ — ¹FU Berlin, Berlin — ²Heinrich-Heine-Universität, Düsseldorf — ³Universität Köln, 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.