Tata Institute of Fundamental Research
Making Quantum Query Algorithms Robust to a Faulty Oracle
STCS Seminar
Speaker:
Manaswi Paraashar (IIT Hyderabad)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 28 Jul 2026, 16:00 to 17:00
Venue:
via Zoom in A201
(Scan to add to calendar)
Abstract:
Understanding 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 this model, for example, Grover's algorithm for the search problem ([Gro96]) and Shor's algorithm for the period-finding problem ([Sho99]). Also, due to its simplicity, this model is also naturally connected to many other areas of quantum computing.
In this talk, we investigate the impact of noise in the quantum query model. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the faulty oracle model, where the oracle fails with a constant probability and acts as identity. Regev and Schiff (ICALP’08) showed that quantum advantage is lost for the search problem under this noise model. Our main result shows that every quantum query algorithm can be made robust 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.
This talk is based on a joint work with David Rasmussen Lolck and Laura Mančinska.
Bio. Manaswi Paraashar is a faculty member in the Department of Computer Science and Engineering at IIT Hyderabad. He completed postdoctoral research at QMath, University of Copenhagen, and in the Department of Computer Science at Aarhus University, both in Denmark. He obtained his Ph.D. from ISI Kolkata, India. His research lies broadly at the intersection of quantum computing and complexity theory.
| Speaker: | Manaswi Paraashar (IIT Hyderabad) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 28 Jul 2026, 16:00 to 17:00 |
| Venue: | via Zoom in A201 |
(Scan to add to calendar)
Abstract:
Understanding 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 this model, for example, Grover's algorithm for the search problem ([Gro96]) and Shor's algorithm for the period-finding problem ([Sho99]). Also, due to its simplicity, this model is also naturally connected to many other areas of quantum computing.
In this talk, we investigate the impact of noise in the quantum query model. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the faulty oracle model, where the oracle fails with a constant probability and acts as identity. Regev and Schiff (ICALP’08) showed that quantum advantage is lost for the search problem under this noise model. Our main result shows that every quantum query algorithm can be made robust 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.
This talk is based on a joint work with David Rasmussen Lolck and Laura Mančinska.
Bio. Manaswi Paraashar is a faculty member in the Department of Computer Science and Engineering at IIT Hyderabad. He completed postdoctoral research at QMath, University of Copenhagen, and in the Department of Computer Science at Aarhus University, both in Denmark. He obtained his Ph.D. from ISI Kolkata, India. His research lies broadly at the intersection of quantum computing and complexity theory.