Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2111.14333 · Quantum Information Processing

Quantum search degeneration under amplitude noise in queries to the oracle

Alexey E. Rastegin, Anzhelika M. Shemet

Published Apr 27, 2022• 8 citations
arXivHTMLPDF
DOI
10.1007/s11128-022-03501-0

Related papers

Degeneration of the Grover search algorithm with depolarization in the oracle-box wires

Alexey E. Rastegin, Anzhelika M. Shemet

Grover’s search algorithm and similar techniques are widely used in quantum information science. Communication lines with the so-called oracle are one of inevitable vulnerabilities of quantum search. The impact of localized dephasing and amplitude damping on Grover’s algorithm had already been discussed in recent literature. In this paper, we study the influence of depolarization in the oracle-box wires on the search process. It is shown that even low level of noise is sufficient to degenerate Grover’s algorithm. Complementarity relations between the relative entropy of coherence and the success probability in the presence of depolarization are studied as well.

Modern Physics Letters A•Feb 20, 2023•3 citations

Query Complexity of Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

Springer eBooks•Jun 15, 2006•1 citation

Studies on Quantum Query Complexity for Oracle Identification Problems

Junichi Teruyama

•Mar 25, 2013•0 citations

Quantum Search with Noisy Oracle

Ansis Rosmanis

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 $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944•Sep 26, 2023•17 citations

Quantum Advantage with Faulty Oracle

David Rasmussen Lolck, Laura Mančinska, Manaswi Paraashar

This paper investigates the impact of noise in the quantum query model, a fundamental framework for quantum algorithms. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the \textit{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.

arXiv:2411.04931•Nov 7, 2024•4 citations

Oracle Distillation

Ruohan Shen, Soonwon Choi

Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy oracle into a single high-fidelity oracle. Here the oracle, an unknown unitary from a known family, models the interface through which a quantum device learns about an unknown system. We construct an explicit protocol that distills any Boolean oracle, both under adversarial noise that corrupts a constant fraction of the input qubits and under i.i.d. depolarizing noise at a constant rate on every qubit. At the heart of the protocol is the weak query, in which the device deliberately queries the oracle only weakly, trading response strength for the ability to correct errors. Our protocol is near-optimal among all protocols that distill the oracle while keeping its errors correctable, revealing a fundamental tension between these two requirements. An important implication of the protocol is a threshold theorem: every Boolean oracle problem whose quantum advantage is polynomial in the domain size, including Grover search, $k$-forrelation, and Simon's problem, retains a quantum advantage whenever the per-qubit depolarizing rate is below a constant threshold. In particular, the quadratic quantum advantage of Grover search, long believed fragile under noise, survives nearly intact at low error rates even when almost every query involves errors on one or more qubits. We further extend the protocol to fractional and continuous-time Boolean oracles. Quantum error correction can thus protect not only prescribed operations but also unknown dynamics. Our results make a large family of quantum advantages in learning robust against noise and open a path toward robust computational sensing.

quant-pharXiv:2609.31596•Sep 28, 2026•1 citation
Grover’s search algorithm and similar techniques are widely used in quantum information science. Communication lines with the so-called oracle are one of inevitable vulnerabilities of quantum search. The impact of localized dephasing and amplitude damping on Grover’s algorithm had already been discussed in recent literature. In this paper, we study the influence of depolarization in the oracle-box wires on the search process. It is shown that even low level of noise is sufficient to degenerate Grover’s algorithm. Complementarity relations between the relative entropy of coherence and the success probability in the presence of depolarization are studied as well.
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0p>0p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(n)\mathrm{O}(\sqrt{n})O(n​)-query algorithms in this setting, even for constant ppp. We show that, for all p≤0.99p\le 0.99p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max⁡{np,n})\tildeΘ(\max\{np,\sqrt{n}\})Θ~(max{np,n​}). The lower bound Ω(max⁡{np,n})Ω(\max\{np,\sqrt n\})Ω(max{np,n​}) holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
This paper investigates the impact of noise in the quantum query model, a fundamental framework for quantum algorithms. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the \textit{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.
Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy oracle into a single high-fidelity oracle. Here the oracle, an unknown unitary from a known family, models the interface through which a quantum device learns about an unknown system. We construct an explicit protocol that distills any Boolean oracle, both under adversarial noise that corrupts a constant fraction of the input qubits and under i.i.d. depolarizing noise at a constant rate on every qubit. At the heart of the protocol is the weak query, in which the device deliberately queries the oracle only weakly, trading response strength for the ability to correct errors. Our protocol is near-optimal among all protocols that distill the oracle while keeping its errors correctable, revealing a fundamental tension between these two requirements. An important implication of the protocol is a threshold theorem: every Boolean oracle problem whose quantum advantage is polynomial in the domain size, including Grover search, kkk-forrelation, and Simon's problem, retains a quantum advantage whenever the per-qubit depolarizing rate is below a constant threshold. In particular, the quadratic quantum advantage of Grover search, long believed fragile under noise, survives nearly intact at low error rates even when almost every query involves errors on one or more qubits. We further extend the protocol to fractional and continuous-time Boolean oracles. Quantum error correction can thus protect not only prescribed operations but also unknown dynamics. Our results make a large family of quantum advantages in learning robust against noise and open a path toward robust computational sensing.