BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum Worst-case to Average-case reductions for all linear probl
 ems - Sathyawageeswar Subramanian\, University of Warwick
DTSTART:20221103T141500Z
DTEND:20221103T153000Z
UID:TALK186353@talks.cam.ac.uk
CONTACT:Sergii Strelchuk
DESCRIPTION:Given an algorithm that has a small non-zero probability of an
 swering correctly on an average input\, can we use it to design another al
 gorithm that has non-zero probability of answering correctly even on worst
 -case inputs? In this talk\, I will focus on quantum algorithms for linear
  problems\, and describe an explicit and efficient transformation that tur
 ns algorithms which are only correct on a small (even sub-constant) fracti
 on of their inputs into ones that are correct on all inputs. This stands i
 n contrast to the classical setting\, where such results are only known fo
 r a small number of specific problems or restricted computational models. 
 Along the way I will also present a tight Omega(n^2) lower bound on the av
 erage-case quantum query complexity of the Matrix-vector Multiplication pr
 oblem.\n\nThe techniques used in this work build on the recently introduce
 d additive combinatorics framework for classical worst-case to average-cas
 e reductions (STOC 2022). The key quantum ingredients are subroutines base
 d on quantum singular value transformations for approximate verification o
 f the output of noisy quantum algorithms\, and a learner for the heavy Fou
 rier characters of indicator functions with imperfect quantum implementati
 ons. I will discuss how these tools can be combined to prove a quantum loc
 al correction lemma based on a probabilistic generalisation of Bogolyubov'
 s lemma in additive combinatorics\, leading to our worst-case to average-c
 ase transformation for linear problems.\n\nThis talk is based on joint wor
 k with Vahid Asadi\, Alexander Golovnev\, Tom Gur\, and Igor Shinkar.
LOCATION:MR15
END:VEVENT
END:VCALENDAR