BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1744
DTSTAMP:20260727T042251Z
SUMMARY:Making Quantum Query Algorithms Robust to a Faulty Oracle
DESCRIPTION:Speaker: Manaswi Paraashar (IIT Hyderabad)\n\nAbstract: \n\nUnd
 erstanding and mitigating noise is one of the most important challenges in
  quantum computing today\, and the quantum query model is one of the most 
 natural models of computation for studying the effects of noise. Almost 
 all provable advantages of quantum algorithms over classical ones are in t
 his model\, for example\, Grover's algorithm for the search problem ([Gro9
 6]) and Shor's algorithm for the period-finding problem ([Sho99]). Also\, 
 due to its simplicity\, this model is also naturally connected to many oth
 er areas of quantum computing.\n \nIn this talk\, we investigate the imp
 act of noise in the quantum query model. We focus on the scenario where th
 e oracle is subject to non-unitary (or irreversible) noise\, specifically 
 under the faulty oracle model\, where the oracle fails with a constant pro
 bability and acts as identity. Regev and Schiff (ICALP’08) showed that q
 uantum advantage is lost for the search problem under this noise model. O
 ur main result shows that every quantum query algorithm can be made robus
 t in this noise model with a roughly quadratic blow-up in query complexity
 \, thereby preserving quantum speedup for all problems where the quantum 
 advantage is super-cubic. This is the first non-trivial robustification of
  quantum query algorithms against an oracle that is noisy.\n \nThis talk
  is based on a joint work with David Rasmussen Lolck and Laura Mančinsk
 a.\n \nBio. Manaswi Paraashar is a faculty member in the Department of C
 omputer Science and Engineering at IIT Hyderabad. He completed postdoctora
 l research at QMath\, University of Copenhagen\, and in the Department of 
 Computer Science at Aarhus University\, both in Denmark. He obtained his P
 h.D. from ISI Kolkata\, India. His research lies broadly at the intersecti
 on of quantum computing and complexity theory.\n
URL:https://www.tcs.tifr.res.in/web/events/1744
DTSTART;TZID=Asia/Kolkata:20260728T160000
DTEND;TZID=Asia/Kolkata:20260728T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR