Dominik Hangleiter: (How) can we verify quantum supremacy?
0Demonstrating a superpolynomial quantum speedup using feasible schemes has become a key near-term goal in the field of quantum simulation and computation. The most prominent schemes for "quantum supremacy" such as boson sampling or random circuit sampling are based on the task of sampling from the output distribution of a certain randomly chosen unitary. But to convince a skeptic of a successful demonstration of quantum supremacy, one must verify that the sampling device produces the correct outcomes. I will first identify a fundamental obstacle towards verifying such devices: ironically, sample-efficient certification based on the experimental output data alone is prohibited by the same property that allows proving the robustness of quantum supremacy to small experimental errors. In the second part of the talk, I will view this no-go result as an invitation to be circumvented. I will discuss alternative certification schemes that exploit known structure of the device, for instance, the possibility to perform quantum measurements in different bases.