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.
AI Summary
The paper studies query algorithms composed of quantum blocks using at most $q$ oracle calls, with all quantum registers measured and discarded between blocks. It asks how this coherence restriction changes total query complexity when classical feedback remains adaptive.
It establishes tight complexities $\Theta(\epsilon^{-1}+(q\epsilon^2)^{-1})$ for phase estimation, $\Theta(\sqrt{p(1-p)}/\epsilon+p(1-p)/(q\epsilon^2))$ for amplitude estimation under a variance promise, and $\Theta(\sqrt N+N/q)$ for search. For an AND of $m$ ORs on $n$ bits each, it proves $\Theta(\sqrt{mn}+mn/q)$, supplying the previously missing matching lower bound. The search bound was already known. Distribution distinguishing with purified access has complexity $\widetilde\Theta(d_H^{-1}+(qd_H^2)^{-1})$, where $d_H$ is Hellinger distance.
The lower-bound framework tracks a $\chi^2$-type distinguishability measure between classical transcript distributions and bounds its increase per quantum block using final-state distances. AND-OR requires an additional noisy-oracle reduction and an adversary-style progress measure combining classical exclusions with quantum-state differences. Estimation upper bounds use repeated phase-estimation procedures with controlled moments; the blocks are nonadaptive and parallelizable. Lower bounds allow adaptive algorithms and biased estimators, while the constructions provide unbiased estimators except in an intermediate amplitude-estimation regime.
The distribution-distinguishing characterization retains logarithmic slack. The paper leaves open tight bounds for arbitrary-depth AND-OR trees, approximate counting, and element distinctness, as well as a more direct proof of its central AND-OR comparison lemma.
No sign of AI-generated textPossible error
Central claim may not hold: The abstract's unqualified unbiased-amplitude-estimation claim is not established by the construction, which explicitly permits bias in the intermediate-coherence regime.
The amplitude-estimation corollary's claimed tight complexity is false for its stated precision range: at q=1 and epsilon=p(1-p), one query suffices under its promise while the claimed bound grows as 1/p.
The intermediate-regime amplitude-estimation proof misidentifies the amplified probability as T_q(p) approximately equal to qp, rather than the standard expression with quadratic amplification near zero, invalidating its stated variance and inversion derivation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies query algorithms composed of quantum blocks using at most q oracle calls, with all quantum registers measured and discarded between blocks. It asks how this coherence restriction changes total query complexity when classical feedback remains adaptive.
It establishes tight complexities Θ(ϵ−1+(qϵ2)−1) for phase estimation, Θ(p(1−p)/ϵ+p(1−p)/(qϵ2)) for amplitude estimation under a variance promise, and Θ(N+N/q) for search. For an AND of m ORs on n bits each, it proves Θ(mn+mn/q), supplying the previously missing matching lower bound. The search bound was already known. Distribution distinguishing with purified access has complexity Θ(dH−1+(qdH2)−1), where dH is Hellinger distance.
The lower-bound framework tracks a χ2-type distinguishability measure between classical transcript distributions and bounds its increase per quantum block using final-state distances. AND-OR requires an additional noisy-oracle reduction and an adversary-style progress measure combining classical exclusions with quantum-state differences. Estimation upper bounds use repeated phase-estimation procedures with controlled moments; the blocks are nonadaptive and parallelizable. Lower bounds allow adaptive algorithms and biased estimators, while the constructions provide unbiased estimators except in an intermediate amplitude-estimation regime.
The distribution-distinguishing characterization retains logarithmic slack. The paper leaves open tight bounds for arbitrary-depth AND-OR trees, approximate counting, and element distinctness, as well as a more direct proof of its central AND-OR comparison lemma.
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.
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.
In this paper, we introduce the hybrid query complexity, denoted as Q(f;q), which is the minimal query number needed to compute f, when a classical decision tree is allowed to call q′-query quantum subroutines for any q′≤q. We present the following results: ∙ There exists a total Boolean function f such that Q(f;1)=O(R(f)4/5). ∙Q(f;q)=Ω(bs(f)/q+bs(f)) for any Boolean function f; the lower bound is tight when f is the OR function. ∙Q(g∘XORClogn;1)=Ω(n) for some sufficiently large constant C, where g:=BOOLSIMONn is a variant of Simon's problem. Note that Q(g∘XORClogn)=O(polylogn). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀k,Q(g∘XORClogk+1n;logkn)=Ω(n), which would imply the oracle separation HP(QSIZE(nα))O⊊BQPO for any α, where HP(QSIZE(nα)) is a complexity class that contains BQTIME(nα)BPP and BPPBQTIME(nα) in any relativized world.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UA and the right-hand side through a state-preparation oracle Ub. The optimal query complexities of these two oracles are known separately: O(κlog(1/ε)) queries to UA and O(κ/s) queries to Ub, where s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open.
We resolve this question affirmatively. Given a constant-factor estimate of s, we give a quantum linear-system algorithm that prepares the normalized solution to error ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UA and O(κ/s) queries to Ub. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy.
We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog(1/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
In this work, we study the phase estimation problem. We show an alternative, simpler and self-contained proof of query lower bounds. Technically, compared to the previous proofs [NW99, Bes05], our proof is considerably elementary. Specifically, our proof consists of basic linear algebra without using the knowledge of Boolean function analysis and adversary methods. Qualitatively, our bound is tight in the low success probability regime and offers a more fine-grained trade-off. In particular, we prove that for any ε>0,p≥0, every algorithm requires at least Ω(p/ε) queries to obtain an ε-approximation for the phase with probability at least p. However, the existing bounds hold only when p>1/2. Quantitatively, our bound is tight since it matches the well-known phase estimation algorithm of Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires O(1/ε) queries to obtain an ε-approximation with a constant probability. Following the derivation of the lower bound in our framework, we give a new and intuitive interpretation of the phase estimation algorithm of [CEMM98], which might be of independent interest.