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:2309.14944

Quantum Search with Noisy Oracle

Ansis Rosmanis

Published Sep 26, 2023• 17 citations
arXivHTMLPDF

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 $\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.

DOI
10.48550/arxiv.2309.14944

Related papers

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

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 ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. 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 $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ 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 $\operatorname{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.

quant-pharXiv:2610.00506•Oct 2, 2026•0 citations

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

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.

•Dec 19, 2025•0 citations

Robust Quantum Algorithms for Oracle Identification

Andris Ambainis, Kazuo Iwama, Akinori Kawachi +2 more

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| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (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.

arXiv:quant-ph/0411204•IPSJ SIG Notes•Nov 30, 2004•18 citations

Loss of the quadratic speedup in Grover search under local and coherent noise

Imama Tul Birrah Khan, Muhammad Faryad

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.

arXiv:2611.16398•Nov 12, 2026•0 citations

Addendum to "Quantum Search with Noisy Oracle"

Ansis Rosmanis

In this note, I generalize the techniques of my recent work (arXiv:2309.14944) and show that, even if just a single known qubit of query registers is affected by the depolarizing noise of rate p, quantum search among n elements cannot be done any faster than in O(np) queries. This holds both when the affected qubit is one of the log(n) index qubits and when it is the target qubit.

arXiv:2405.11973•May 20, 2024•4 citations

Bosonic unstructured search: quantum enhancement without entanglement

Yu-Xin Wang, Erfan Abbasgholinejad, Supratik Sarkar +4 more

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 $n_{\text{b}}\gg 1$. We analyze a continuous-time phase-shift oracle of strength $B_{0}$, 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(\sqrt{N}/{n_{\text{b}}}B_{0})$ for continuous-time oracles or $O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)$ for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)$. In contrast, for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)$, we provide an algorithm using $O(\max\{1,\sqrt{N/n_{\text{b}}|{\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 $n_{\text{b}}$, but entanglement is not. Under uniform boson loss at rate $γ$, we prove a query lower bound of $Ω( γN / n _{\text{b}} B_{0}^{2} )$, attained for $γ= Ω(B_{0} \sqrt{n _{\text{b}}/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.

quant-pharXiv:2610.17163•Oct 13, 2026•0 citations
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.
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⁡\operatorname{fbs}fbs). For a negligent oracle that applies the correct query with probability 1−p1-p1−p, we prove a lower bound in terms of fbs⁡(f,0n)\operatorname{fbs}(f,0^n)fbs(f,0n). We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function fff can be transformed into a partial function f′f'f′ whose negligent query complexity essentially preserves the quantum query complexity of fff. 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)\operatorname{fbs}(f)fbs(f) for partial functions in this model. For two other models, we obtain general lower bounds in terms of fbs⁡(f)\operatorname{fbs}(f)fbs(f) for all Boolean functions. For hybrid algorithms using QQQ coherent and CCC classical queries, we prove the tradeoff C+Q2=Ω(fbs⁡(f))C+Q^2=Ω(\operatorname{fbs}(f))C+Q2=Ω(fbs(f)). For an IID dephasing noisy model where each query dephases the query-index register at rate ppp independently, we prove Ω ⁣(p fbs⁡(f))Ω\!\left(p\,\operatorname{fbs}(f)\right)Ω(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)\operatorname{fbs}(f)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 SSS of MMM oracles and a blackbox oracle fff. Our task is to figure out which oracle in SSS is equal to the blackbox fff by making queries to fff. 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: (iii) For any oracle set SSS such that ∣S∣≤2Nd|S| \le 2^{N^d}∣S∣≤2Nd (d<1d < 1d<1), we design an algorithm whose query complexity is O(Nlog⁡M/log⁡N)O(\sqrt{N\log{M}/\log{N}})O(NlogM/logN​), matching the lower bound proved in \cite{AIKMRY04}. (iiiiii) Our algorithm also works for the range between 2Nd2^{N^d}2Nd and 2N/log⁡N2^{N/\log{N}}2N/logN (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. (iiiiiiiii) 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 NNN possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget nb≫1n_{\text{b}}\gg 1nb​≫1. We analyze a continuous-time phase-shift oracle of strength B0B_{0}B0​, with cost given by the total oracle time, and a discrete oracle with fixed phase φ0φ_{0}φ0​, with cost given by the number of queries. We give algorithms that identify the target with query complexity O(N/nbB0)O(\sqrt{N}/{n_{\text{b}}}B_{0})O(N​/nb​B0​) for continuous-time oracles or O(N/nb∣sin⁡(φ0/2)∣)O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)O(N​/nb​∣sin(φ0​/2)∣) for discrete oracles with nb∣sin⁡(φ0/2)∣=O(1)n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)nb​∣sin(φ0​/2)∣=O(1). In contrast, for discrete oracles with nb∣sin⁡(φ0/2)∣=Ω(1)n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)nb​∣sin(φ0​/2)∣=Ω(1), we provide an algorithm using O(max⁡{1,N/nb∣sin⁡(φ0/2)∣})O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})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 NNN and nbn_{\text{b}}nb​, but entanglement is not. Under uniform boson loss at rate γγγ, we prove a query lower bound of Ω(γN/nbB02)Ω( γN / n _{\text{b}} B_{0}^{2} )Ω(γN/nb​B02​), attained for γ=Ω(B0nb/N)γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})γ=Ω(B0​nb​/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.