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.
AI Summary
The paper studies which quantum query speedups survive imperfect oracle access, using fractional block sensitivity ($\operatorname{fbs}$) to extend search lower bounds to general Boolean functions.
For negligent queries—each oracle call is replaced by the identity with probability $p$—it proves $\Omega_\epsilon(\frac{p}{1-p}\operatorname{fbs}(f,0^n))$ queries are necessary. Complementary-pair encoding, $0\mapsto01$ and $1\mapsto10$, makes successful calls detectable without disturbing the logical computation. This transforms a function into a partial function preserving randomized query complexity and simulating ideal quantum queries with expected overhead $1/(1-p)$. Consequently, partial functions can retain exponential quantum speedups, and a universal global-$\operatorname{fbs}$ lower bound fails in this model.
For hybrid algorithms, the bound is $C+Q^2=\Omega_\epsilon(\operatorname{fbs}(f))$, with $C$ classical and $Q$ coherent queries. Independent query-index dephasing at rate $p$ requires $\Omega_\epsilon(\sqrt{\operatorname{fbs}(f)}+p\operatorname{fbs}(f))$ queries. The proofs use fractional sensitive-block packings and progress potentials; dephasing additionally requires tracking hidden index records.
A variational resource extends the analysis to time-dependent, temporally correlated dephasing schedules sampled independently of the computation. For search with $p_t=\min\{1,\lambda t^\gamma\}$, $0<\gamma<1$, matching bounds give successive regimes $\sqrt N$, $(\lambda N)^{1/(1-\gamma)}$, and $N$, with transitions at $\lambda\asymp N^{-(1+\gamma)/2}$ and $N^{-\gamma}$.
Open questions include a global-$\operatorname{fbs}$ negligent bound for total functions, tighter measures for functions such as $\mathrm{AND}\circ\mathrm{OR}$, general dephasing simulations, and applications to physically motivated correlated noise.
Little sign of AI-generated textAI use disclosedPossible errorUnclear writing
The model suggested a partial-function counterexample.
Error found: The partial-function lifting theorem states an Omega lower bound instead of the upper bound needed to express preservation of quantum query complexity.
The lifting proof starts with too much ideal error to reach its claimed final error by truncation and misstates the Markov cutoff, although the preservation construction admits a straightforward repair.
The extension of the hybrid lower bound from the zero input to global fractional block sensitivity is unsupported for pseudo-classical queries because those queries lack the XOR covariance invoked in the proof.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies which quantum query speedups survive imperfect oracle access, using fractional block sensitivity (fbs) to extend search lower bounds to general Boolean functions.
For negligent queries—each oracle call is replaced by the identity with probability p—it proves Ωϵ(1−ppfbs(f,0n)) queries are necessary. Complementary-pair encoding, 0↦01 and 1↦10, makes successful calls detectable without disturbing the logical computation. This transforms a function into a partial function preserving randomized query complexity and simulating ideal quantum queries with expected overhead 1/(1−p). Consequently, partial functions can retain exponential quantum speedups, and a universal global-fbs lower bound fails in this model.
For hybrid algorithms, the bound is C+Q2=Ωϵ(fbs(f)), with C classical and Q coherent queries. Independent query-index dephasing at rate p requires Ωϵ(fbs(f)+pfbs(f)) queries. The proofs use fractional sensitive-block packings and progress potentials; dephasing additionally requires tracking hidden index records.
A variational resource extends the analysis to time-dependent, temporally correlated dephasing schedules sampled independently of the computation. For search with pt=min{1,λtγ}, 0<γ<1, matching bounds give successive regimes N, (λN)1/(1−γ), and N, with transitions at λ≍N−(1+γ)/2 and N−γ.
Open questions include a global-fbs negligent bound for total functions, tighter measures for functions such as AND∘OR, general dephasing simulations, and applications to physically motivated correlated noise.
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 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 Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) 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.
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.
Given oracle access to an unknown unitary U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitH, 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(δ1logε1) queries for approximation error ε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any N-query circuit to the approximation of eitθ by a trigonometric polynomial with degree bounded by O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ(δ1logε1). Consequently, the optimal query complexity for fractional query problem is Θτ(δ1logε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) bound uniform to δ.
In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.
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(loglogn)/(S1/3logn)) 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 [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 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.