BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1238
DTSTAMP:20230914T125956Z
SUMMARY:M.Sc. thesis waiver presentation
DESCRIPTION:Speaker: Sreejata Kishor Bhattacharya\n\nAbstract: \nOne of th
e most active research directions in quantum computing currently is establ
ishing quantum supremacy results: coming up with computational tasks which
a quantum algorithm can solve super-polynomially faster than a classical
algorithm. In this talk we look at the particular computational model of q
uery complexity: where the algorithm has to evaluate a known function on a
n unknown input\; it can access the input by asking queries to an oracle a
nd has to minimize the number of queries. Internal computations are assume
d to have no cost. We can define the quantum variant of query complexity w
here the quantum algorithm has access to an oracle representing the input
and can ask queries in superposition.\n\nOne of the long-standing question
s in this direction is the following: given a quantum query algorithm for
a Boolean function (defined on a subset of the Boolean hypercube with at l
east inverse polynomial density) making d queries\, does there exist a cla
ssical query algorithm which makes at most poly(d) queries and approximate
s the output probability of the quantum algorithm on most inputs? We shall
discuss the body of previous work done on this question: weak results tha
t are known\, a recent attempt to resolve the conjecture which turned out
to have a fatal flaw and our attempts to fix the argument.\n
URL:https://www.tcs.tifr.res.in/web/events/1238
DTSTART;TZID=Asia/Kolkata:20220908T103000
DTEND;TZID=Asia/Kolkata:20220908T120000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR