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.
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.
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.
The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set S of M oracles and a blackbox oracle f. Our task is to figure out which oracle in S is equal to the blackbox f by making queries to f. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: (i) For any oracle set S such that ∣S∣≤2Nd (d<1), we design an algorithm whose query complexity is O(NlogM/logN), matching the lower bound proved in \cite{AIKMRY04}. (ii) Our algorithm also works for the range between 2Nd and 2N/logN (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. (iii) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.
Grover's algorithm searches an unstructured database with a number of oracle queries that grows only as the square root of its size. Noise erodes this advantage, and we ask, analytically, how quickly. When a depolarizing channel acts on the whole register after every gate layer, it commutes with the gates, and the noisy state is the noiseless one with a coherent weight that decays geometrically with depth. The Grover rotation is not slowed. Its weight decays, the best stopping point moves earlier, and the expected query cost keeps its square-root scaling only while the accumulated noise over the circuit stays small. For independent errors on the qubits we show that the ideal Grover operator freezes any amplitude pushed out of the two-dimensional search plane. This gives the exact effect of a single error: phase flips do most damage early in the search, bit flips late, and combined errors at any time. For large databases it also reduces the noisy search to Bloch-type equations for the part of the state that stays in the plane, in which the algorithm is a rotation and the noise appears as leakage and dephasing. We derive the rates for bit-flip, phase-flip, depolarizing, and amplitude-damping noise and solve the equations. Local noise acts, to leading order, like a global channel strengthened by the number of qubits, so the tolerable error per qubit falls faster than the inverse square root of the database size by one power of the register size. For coherent errors in the rotation angle we bound the success probability by a band that widens linearly with depth. Our results recover, in closed form, scalings found earlier for particular noise models, and they explain why some errors are more harmful than others.
We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among N possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget nb≫1. We analyze a continuous-time phase-shift oracle of strength B0, with cost given by the total oracle time, and a discrete oracle with fixed phase φ0, with cost given by the number of queries. We give algorithms that identify the target with query complexity O(N/nbB0) for continuous-time oracles or O(N/nb∣sin(φ0/2)∣) for discrete oracles with nb∣sin(φ0/2)∣=O(1). In contrast, for discrete oracles with nb∣sin(φ0/2)∣=Ω(1), we provide an algorithm using O(max{1,N/nb∣sin(φ0/2)∣}) queries. We also prove matching lower bounds on the query complexity, showing that these algorithms are asymptotically optimal. Furthermore, we show that, in the absence of loss, non-Gaussianity is necessary to achieve the optimal joint query scaling in N and nb, but entanglement is not. Under uniform boson loss at rate γ, we prove a query lower bound of Ω(γN/nbB02), attained for γ=Ω(B0nb/N) using coherent-state probes. Finally, we propose experimental implementations using multipass optical microscopy or superconducting circuits as potential routes to speeding up imaging or device calibration with a low boson-number budget.