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

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

quant-phcs.CCSubmitted Sep 30, 2026• Announced Oct 2, 2026• 0 citations
v1 · Sep 30, 2026v2 · Oct 2, 2026
arXivHTMLPDF

Abstract

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,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 \(\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+Q^2=Ω(\fbs(f))\). For an IID dephasing noisy model where each query dephases the query-index register at rate \(p\) independently, we prove \(Ω\!\left(p\,\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 \(\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.

Related papers

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

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•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•1 citation

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

Paul Beame, Blake Holman, Niels Kornerup

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

cs.CCCross-listedarXiv:2609.40334•Oct 1, 2026•0 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

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

THEORETICAL FOUNDATIONS OF CLASSICAL AND QUANTUM QUERY MODELS: COMPLEXITY, LOWER BOUNDS, AND POLYNOMIAL-SPECTRAL INTERPLAY

Medak Srinivas

Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.

Iterative International Publishers eBooks•May 1, 2026•0 citations
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,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 (\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+Q^2=Ω(\fbs(f))). For an IID dephasing noisy model where each query dephases the query-index register at rate (p) independently, we prove (Ω!\left(p,\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 (\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.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
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.
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))Ω(n4/3(loglogn)/(S1/3logn)) lower bound on the number of queries that a fully general quantum algorithm with at most SSS qubits of memory requires to sort nnn numbers from [n2][n^2][n2]. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family HHH from nnn bits to mmm bits, almost all hash functions in HHH require any algorithm with at most SSS qubits of memory to make Ω(nm/S)Ω(nm/S)Ω(nm/S) quantum queries to input xxx in order to compute h(x)h(x)h(x), even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing h(x)h(x)h(x) with both hhh and xxx as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.
Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.