Quantum Search with Noisy Oracle
- 講者Ansis Rosmanis 博士 (日本名古屋大學)
邀請人：鐘楷閔 - 時間2023-07-13 (Thu.) 10:00 ~ 12:00
- 地點資訊所新館101演講廳
摘要
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.