BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Quantum Worst-case to Average-case reductions for
all linear problems - Sathyawageeswar Subramanian\
, University of Warwick
DTSTART;TZID=Europe/London:20221103T141500
DTEND;TZID=Europe/London:20221103T153000
UID:TALK186353AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/186353
DESCRIPTION:Given an algorithm that has a small non-zero proba
bility of answering correctly on an average input\
, can we use it to design another algorithm that h
as non-zero probability of answering correctly eve
n on worst-case inputs? In this talk\, I will focu
s on quantum algorithms for linear problems\, and
describe an explicit and efficient transformation
that turns algorithms which are only correct on a
small (even sub-constant) fraction of their inputs
into ones that are correct on all inputs. This st
ands in contrast to the classical setting\, where
such results are only known for a small number of
specific problems or restricted computational mode
ls. Along the way I will also present a tight Omeg
a(n^2) lower bound on the average-case quantum que
ry complexity of the Matrix-vector Multiplication
problem.\n\nThe techniques used in this work build
on the recently introduced additive combinatorics
framework for classical worst-case to average-cas
e reductions (STOC 2022). The key quantum ingredie
nts are subroutines based on quantum singular valu
e transformations for approximate verification of
the output of noisy quantum algorithms\, and a lea
rner for the heavy Fourier characters of indicator
functions with imperfect quantum implementations.
I will discuss how these tools can be combined to
prove a quantum local correction lemma based on a
probabilistic generalisation of Bogolyubov's lemm
a in additive combinatorics\, leading to our worst
-case to average-case transformation for linear pr
oblems.\n\nThis talk is based on joint work with V
ahid Asadi\, Alexander Golovnev\, Tom Gur\, and Ig
or Shinkar.
LOCATION:MR15
CONTACT:Sergii Strelchuk
END:VEVENT
END:VCALENDAR