BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cryptography\, Distribution Verification\, and Quantum Advantage -
  Matthew Gray (Oxford)
DTSTART:20260113T130000Z
DTEND:20260113T140000Z
UID:TALK242356@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:The study of quantum computation is motivated by our belief in
  the existence of quantum advantage: that there are computational tasks th
 at are easy for quantum computers but hard for classical ones. Sampling-ba
 sed quantum advantage (the existence of quantum samplable but classically 
 un-samplable distributions) is one of the most well-studied frameworks for
  quantum advantage\, with specific instantiations such as Boson sampling a
 nd random-circuits having received significant study. One often-claimed di
 sadvantage of sampling-based quantum advantage compared with more sophisti
 cated frameworks\, such as proofs of quantumness\, is the lack of efficien
 t (or even inefficient) verification. This disadvantage of sampling-based 
 quantum advantage has been justified by appealing to the intuition that ve
 rifying distributions is impossible (even inefficiently). However this imp
 ossibility only holds when the adversarial distribution is some arbitrary 
 (potentially un-samplable) distribution and it is reasonable to assume tha
 t adversarial distributions must also be samplable. We provide formal defi
 nitions for this version of verification of distributions and the verifica
 tion of quantum advantage distributions. Using these definitions we prove 
 the following results:\n     Classically samplable distributions are PPT v
 erifiable if and only if (io)-OWFs do not exist.\n     Quantum samplable d
 istributions are verifiable by QPT^PP.\n     If (io)-OWPuzz do not exist t
 hen quantum advantage distributions are QPT verifiable.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR