skip to main content
Caltech

IQI Weekly Seminar

Tuesday, January 22, 2019
3:00pm to 4:00pm
Add to Cal
Annenberg 107
Verification vs. Approximate sampling: How hard is it to verify "quantum supremacy"?
Dominik Hangleiter, University of Berlin,

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.

 

 

 

 

 

 

For more information, please contact Bonnie Leung by phone at 626.395.4964 or by email at [email protected].