What are the tight query bounds for hybrid quantum-classical algorithms?

The hybrid model caps queries per coherent block

The paper studies hybrid quantum-classical algorithms in the query model. A computation is classical, but it may invoke quantum subroutines, and each subroutine is allowed at most q oracle queries. At the end of every subroutine, all quantum registers are measured and discarded, and the measurement outcomes are passed to the classical algorithm, which then chooses the next subroutine.

Formally, the algorithm is a finite rooted tree: each internal vertex holds a quantum algorithm making at most q queries and ending in a measurement, outgoing edges are labelled by measurement outcomes, and leaves carry the classical output. The complexity is the maximum, over root-to-leaf paths that can occur on a valid input, of the total number of queries summed over the internal vertices on that path.

The parameter q is the lever the paper varies. Setting q = 1 recovers the classical complexity, while letting q reach Q(f), the unrestricted bounded-error quantum query complexity, recovers the standard quantum setting. Everything in between is the hybrid regime the paper characterizes.

Phase and amplitude estimation scale as one over q epsilon squared

The first pair of results concerns estimating a phase or an amplitude to precision ε with success probability at least 2/3. For phase estimation, given controlled query access to an unknown unitary U and an eigenstate U|ψ⟩ = e^{iφ}|ψ⟩, the hybrid query complexity of estimating φ to precision ε ∈ (0,1) is Θ(1/ε + 1/(qε²)).

For amplitude estimation, given controlled access to a unitary U with U|0̄⟩ = √s|1⟩|ψ₁⟩ + √(1−s)|0⟩|ψ₀⟩, and promised only that s(1−s) ≤ p(1−p) for a known p ∈ (0,1), the complexity of estimating s to precision ε ≤ p(1−p) is Θ(√(p(1−p))/ε + p(1−p)/(qε²)).

Both lower bounds follow from a single theorem on binary classification of unitaries: if subroutines use at most q controlled queries to U and U†, and there exist U₀, U₁ in the two classes with ‖U₀ − U₁‖ = ε, then any bounded-error hybrid algorithm needs Ω(1/ε + 1/(qε²)) queries in the worst case. The 1/ε term is the unrestricted quantum bound, and the 1/(qε²) term is the hybrid penalty.

The matching upper bounds come from unbiased estimators. For phase estimation, repeating a subroutine ℓ = Θ(1/(q²ε²)) times yields an unbiased estimator of e^{iφ} with variance O(1/(q²ℓ)). For amplitude estimation, the analysis splits into regimes: for q = O(1) one simply measures U|0̄⟩; for 1 ≪ q ≤ (p(1−p))^{−1/2} one uses amplitude amplification about q times and outputs the first qubit; for larger q one runs the boosting procedure with m = 4 and takes the real part of the phase estimate. In all cases the estimator is unbiased except in the intermediate amplitude-estimation regime, and the algorithm is non-adaptive, so all depth-q circuits may be run in parallel.

Search and AND-OR add a square-root term to the hybrid cost

For search, the setting is standard: x₁, …, x_N ∈ {0,1} with query access, and the task is to distinguish the case where no i has x_i = 1 from the case where exactly one such i exists. The paper proves that Θ(√N + N/q) queries are necessary and sufficient. The √N term is the familiar Grover bound, and N/q is the classical-like term that dominates when q is small.

The bound was first proved by Sun and Zheng; here it is rederived through the same framework used for binary classification, which is the paper's stated reason for including it.

The third problem is the two-level AND-OR tree F(x) = ⋀_{i=1}^{m} ⋁_{j=1}^{n} x_{ij} with x ∈ {0,1}^{m×n} and m, n ≥ 2, which models a nested search. The paper proves that Θ(√(mn) + mn/q) queries are necessary and sufficient to compute F. The upper bound is due to MMO24; the lower bound is shown in this paper for the first time.

All four bounds are stated as optimal up to a constant factor for every q from 1 up to Q(f), the unrestricted quantum query complexity of the respective problem. That is the sense in which they are tight: they interpolate exactly between the classical endpoint and the quantum endpoint.

A chi-squared progress measure drives the lower bounds

The paper's methodological contribution is a systematic way to prove hybrid lower bounds, which the authors describe as having been very ad hoc up to now. The framework tracks the transcript: the sequence of classical measurement outcomes produced by successive quantum blocks. For each input, a hybrid algorithm induces a probability distribution over transcripts, and if the algorithm distinguishes two inputs with bounded error, those transcript distributions must have constant statistical distance.

The difference is captured by a χ²-type progress measure M(p, q) = Σ_z (p(z) − q(z))² / (2(p(z) + q(z))). A Cauchy–Schwarz bound relates it to total variation distance: TV(p, q) ≤ √M. If the algorithm distinguishes the two cases with error at most 1/3, then the final total variation distance is at least 1/3, hence M_T ≥ 1/9.

The key one-block inequality (Lemma 1) bounds the increase in progress after one subroutine by (1 − M_t(h))·‖|ψ₀⟩ − |ψ₁⟩‖², where |ψ₀⟩ and |ψ₁⟩ are the subroutine's states immediately before its final measurement under the two oracles. Combined with the fact that an r-query subroutine changes the state by at most r·‖U₀ − U₁‖, this yields M_T ≤ qε²L, where L is the worst-case total query count, and therefore L = Ω(1/(qε²)). The standard hybrid argument applied to the whole computation separately gives L = Ω(1/ε), and the two combine into the stated bound.

For search, the proof uses the complement M′ = 1 − M and the sum Σ_i M′^{(i)}_t over the N possible positions of the unique 1 as the progress measure. For AND-OR, the argument is more delicate: it combines the transcript-based measure with ideas from the hybrid compressed-oracle framework, including a reduction to an alternative model of hybrid computation and separate progress measures tracking the classical and quantum information accumulated by the algorithm. Unlike that earlier work, the ingredients are folded into an adversary-style argument rather than used to track a compressed oracle.

Distribution distinguishing is tight up to a logarithmic factor

As a further application, the paper characterizes the hybrid query complexity of distinguishing two discrete distributions r, s ∈ Δ_k given by purified access: an unknown unitary U_p corresponding to a uniformly random p ∈ {r, s} with U_p|0̄⟩ = Σ_{i∈[k]} √(p_i)|i⟩|ψ_i⟩. With controlled access to U_p, distinguishing U_r from U_s with success probability at least 2/3 costs Θ̃(1/d_H + 1/(q d_H²)), where d_H is the Hellinger distance d_H(r, s) = √(Σ_{i∈[k]} (√r_i − √s_i)² / 2).

This bound is tight up to a logarithmic factor, not up to a constant. The lower bound is essentially equivalent to the amplitude-estimation corollary already in the k = 2 case. The upper bound reduces to that binary case: there is always a subset B ⊂ [k] such that the induced binary distributions satisfy 1 ≤ d_H(r, s)/d_H(r_B, s_B) ≤ O(min(k, log(1/d_H))), so applying the amplitude-estimation algorithm to r_B, s_B is asymptotically tight for constant k and has at most logarithmic slack in d_H in general.

The paper notes that this access model is fairly generic and includes situations where distributions are obtained via quantum Monte Carlo methods, and that the result interpolates smoothly between the incoherent sample complexity and the fully coherent query complexity.

Open problems mark where the framework stops

The paper is explicit that the study of hybrid lower bounds is just starting, and it lists four open problems. First, Lemma 4 — which upper bounds the distinguishability of transcript distributions via the probabilities of querying the variables that differ between the two inputs — currently lacks a more direct proof analogous to the earlier sections. Second, the methods extend to tight lower bounds for AND-OR trees of larger constant depth, but with big-O constants that increase with depth; whether arbitrary depth admits a tight bound is open.

Third, approximate counting, such as distinguishing whether the fraction of variables equal to 1 is 1/2 or 1/2 + ε, is a natural target, since its optimal quantum lower bound is proved by a positive-weight adversary method with a simple input distribution, suggesting the framework may extend. Fourth, element distinctness is unresolved: natural decompositions give O(max(N^{2/3}, N²/q²)) queries, which beats the classical algorithm only when q > √N, and it is not known whether this is optimal. The authors flag two difficulties — the positive-weight adversary method no longer gives an optimal quantum bound, and the hybrid and noisy query models may differ, so the noisy model may not yield an optimal lower bound.

These are stated as open problems, not as results. They define the boundary of what the paper's four tight bounds and its distribution-distinguishing bound actually establish.

Read the bounds as a tradeoff curve in q

The most useful way to read this paper is as a tradeoff curve rather than a single number. Each result has the form (unrestricted quantum term) + (classical-like term)/q, and the crossover between the two regimes is what determines whether a hybrid implementation retains an advantage. For search, the hybrid cost is √N + N/q, so the quantum advantage survives only while N/q is not much larger than √N, that is, roughly while q exceeds √N. For the two-level AND-OR tree, the analogous comparison is between √(mn) and mn/q.

For phase and amplitude estimation, the comparison is between 1/ε and 1/(qε²), and between √(p(1−p))/ε and p(1−p)/(qε²). The amplitude-estimation result carries an extra condition worth noting: the promise is s(1−s) ≤ p(1−p) for a known p, and the stated complexity holds for ε ≤ p(1−p). The paper also notes that the estimator is unbiased except in the 1 ≪ q ≪ (p(1−p))^{−1/2} regime, where the algorithm produces a potentially biased estimator of p via T_q(p)/q.

The distribution-distinguishing result is the one place where tightness is only up to a logarithmic factor, and the slack is bounded by O(min(k, log(1/d_H))) through the binary reduction. That is the paper-specific threshold to keep in mind: for constant k the bound is asymptotically tight, and the logarithmic slack grows with the number of outcomes k and with small Hellinger distance.

Sources used in this answer