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.
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.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
We show that it is impossible to obtain a quantum speedup for a faulty Hamiltonian oracle. The effect of dephasing noise to this continuous-time oracle model has first been investigated by Shenvi, Brown, and Whaley [Phys. Rev. A 68, 052313 (2003).]. The authors consider a faulty oracle described by a continuous-time master equation that acts as dephasing noise in the basis determined by the marked item. The analysis focuses on the implementation with a particular driving Hamiltonian. A universal lower bound for this oracle model, which rules out a better performance with a different driving Hamiltonian, has so far been lacking. Here, we derive an adversary-type lower bound which shows that the evolution time T has to be at least in the order of N, i.e., the size of the search space, when the error rate of the oracle is constant. This means that quadratic quantum speedup vanishes and the runtime assumes again the classical scaling. For the standard quantum oracle model this result was first proven by Regev and Schiff [in Automata, Languages and Programming, Lecture Notes in Computer Science Vol. 5125 (Springer, Berlin, 2008), pp. 773--781]. Here, we extend this result to the continuous-time setting.
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.
We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett., 2008]. Due to a result of Regev and Schiff [ICALP, 2008], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order o(2^{-n/2}) (where N=2^n is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of "active" gates, since all components have to be actively error corrected.
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(n)-query algorithms in this setting, even for constant p. We show that, for all p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max{np,n}). The lower bound Ω(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.
We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity (fbs).
For a negligent oracle that applies the correct query with probability 1−p, we prove a lower bound in terms of fbs(f,0n). We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function f can be transformed into a partial function f′ whose negligent query complexity essentially preserves the quantum query complexity of f. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of fbs(f) for partial functions in this model.
For two other models, we obtain general lower bounds in terms of fbs(f) for all Boolean functions. For hybrid algorithms using Q coherent and C classical queries, we prove the tradeoff C+Q2=Ω(fbs(f)). For an IID dephasing noisy model where each query dephases the query-index register at rate p independently, we prove Ω(pfbs(f)) queries are necessary.
Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by fbs(f). Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.