Seminars

View all Seminars  |  Download ICal for this event

Making Quantum Query Algorithms Robust to a Faulty Oracle

Series: Bangalore Theory Seminars

Speaker: Manaswi Paraashar,University of Copenhagen

Date/Time: Oct 23 16:00:00

Location: Online Talk (See Teams link below)

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, Grovers algorithm for the search problem ([Gro96]) and Shors 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.
<br>
This talk is based on a joint work with David Rasmussen Lolck and Laura Mančinska.

<br>
Microsoft teams link:
<br>

<a href="Link
">Link </a>
<br>
<br>
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series

<br>
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar