Quantum Search with Noisy Oracle
- LecturerDr. Ansis Rosmanis (Nagoya University, Japan)
Host: Kai-Min Chung - Time2023-07-13 (Thu.) 10:00 ~ 12:00
- LocationAuditorium 101 at IIS new Building
Abstract
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(sqrt(n))-query algorithms in this setting, even for constant p. We show that for all p in [1/sqrt(n), 1-Ω(1)], the quantum noisy-query complexity of the unstructured search is Ω(np), which is tight up to logarithmic factors. The same bound holds for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the noise has occurred.