IQI Weekly Seminar

Abstract: Devising schemes showing a quantum speedup that are feasible in the near
future has become a central milestone in the field of quantum simulation
and computation. The most prominent of the suggested schemes are based
on the task of sampling from the output distribution of certain randomly
chosen unitaries applied to a reference state. In this talk, I will
discuss how two properties required of such schemes of "quantum
supremacy" are related: the hardness results need to be robust against
errors and a (quantum) device sampling from the relevant distributions
should be efficiently verifiable. I will show that, ironically, an
anti-concentration property that is crucial to proving an *approximate*
hardness result, also prohibits sample-efficient certification based on
the experimental output data alone. This is the case, in particular, for
Boson Sampling, universal random circuit sampling and IQP circuit
sampling. In the last part of the talk I will view these results as an
invitation to be circumvented and discuss alternative certification
schemes that use structure specific to the sampling device or quantum
powers of the verifier.