Query Complexity

Query complexity counts how many times an algorithm must consult an unknown input. It separates the cost of obtaining information from the work between consultations. This makes it possible to prove clean quantum–classical comparisons, provided both algorithms solve the same promised problem with the same access and error requirements.

Two examples guide this page. Parity needs all $n$ bits classically but only $\lceil n/2\rceil$ quantum queries. Deciding whether an $N$-bit input contains no one or exactly one one requires $\Theta(N)$ randomized queries and $\Theta(\sqrt N)$ quantum queries at constant bounded error. These counts do not include building the oracle or implementing the intervening gates.

Helpful background. Quantum oracles defines the access operations being counted. Algorithmic primitives explains how coherent queries combine with interference and readout.

Querying bits of a promised input

Let $D\subseteq\{0,1\}^n$ be the valid input set. A function specifies one answer $f(x)$; a relation specifies a nonempty set $F(x)\subseteq Y$ of valid answers. A promise restricts correctness to $x\in D$.

Our oracle is the complete bit-query unitary

$$O_x|i,b,z\rangle=|i,b\oplus x_i,z\rangle, \qquad i=1,\ldots,n.$$

The answer register is one bit and $z$ is workspace. The action is defined for every Boolean string, including strings outside the promise. A classical query returns $x_i$; a quantum query may act on a superposition of indices. Preparing the answer in $|-\rangle$ gives the phase $(-1)^{x_i}$ with one call. Preparing it in $|+\rangle$ gives no change. Also $O_x^{-1}=O_x$, so an inverse call has the same query cost here. These properties are specific to this oracle, not universal properties of unknown unitaries.

A $T$-query quantum algorithm has the form

$$U_TO_xU_{T-1}\cdots U_1O_xU_0,$$

with input-independent unitaries $U_j$ and a final measurement. Intermediate measurements can be deferred by recording their outcomes coherently. A branch that stops early can be padded to a fixed cap: route its answer register through a spare $|+\rangle$ during an inactive query, then restore the routing. Thus no extra unknown controlled oracle is assumed in this bit-query representation.

The abstract model allows arbitrary input-independent processing between queries. A small query count therefore need not imply an efficiently synthesizable circuit, small memory or short runtime. Parallel queries, query rounds and sequential calls are also different measures.

Deterministic, randomized and quantum measures

Every measure in this table uses a worst-case fixed query cap. The success requirement applies to every promised input.

Measure	Allowed procedure	Required output
$D(F)$	Deterministic decision tree	Always valid
$R_\epsilon(F)$	Random choice of capped decision trees	Valid with probability at least $1-\epsilon$
$Q_E(F)$	Quantum procedure	Valid with probability one
$Q_0(F)$	Quantum procedure with an extra ? outcome	Never wrong when conclusive; ? probability at most $1/2$
$Q_\epsilon(F)$	Quantum procedure	Valid with probability at least $1-\epsilon$

Usually $\epsilon=1/3$. Exact finite counts can depend on this choice. For a Boolean answer, independent repetition and majority voting reduce any fixed error below $1/2$ at constant-factor cost. A relation can have several different valid outputs, so majority voting needs a separate justification or a verifier.

Zero error allows uncertainty, not false answers. Repeating a capped $Q_0$ procedure until it concludes has worst-input expected cost at most twice its cap. Conversely, an always-correct stopping procedure with worst-input mean cost $L>0$ can be cut off at $\lceil2L\rceil$ queries and made to return ? thereafter. Markov’s inequality bounds that inconclusive probability by $1/2$. The zero-cost case is already trivial. Expected stopping cost and fixed-cap cost are related, but their finite values are not identical. Literature notation for zero error varies, so check its definition before comparing results.

Classical lower bounds from hard distributions

A deterministic decision tree branches on previously observed bits. To lower-bound a randomized algorithm, Yao’s minimax principle lets us choose an input distribution that is difficult for every capped deterministic tree.

For finite input and output sets, let $\mathcal T_q$ be the deterministic trees of depth at most $q$ and $\ell(A,x)$ their zero-or-one error. Then

$$\begin{aligned} &\min_{\lambda}\max_{x\in D}\mathbb E_{A\sim\lambda}\ell(A,x)\\ &\qquad=\max_{\mu}\min_{A\in\mathcal T_q}\mathbb E_{x\sim\mu}\ell(A,x), \end{aligned}$$

where $\lambda$ ranges over distributions of trees and $\mu$ over promised inputs. The left side is optimal worst-case randomized error; the right side is optimal deterministic error against the hardest distribution. This equality holds at fixed depth. It is not an unchanged formula for arbitrary expected-cost stopping rules.

For parity, use the uniform distribution on all bit strings. If even one coordinate remains unread, its conditional value is fair and flips the parity. Any tree with fewer than $n$ queries therefore errs with probability $1/2$. Consequently $R_\epsilon(\operatorname{PARITY}_n)=D(\operatorname{PARITY}_n)=n$ for $0\leq\epsilon<1/2$.

Polynomial lower bounds

Initially, each quantum amplitude is independent of $x$. One bit query expresses a new amplitude as old amplitudes multiplied by $x_i$ or $1-x_i$, increasing degree by at most one. Input-independent unitaries only take linear combinations. After $T$ queries, amplitudes are polynomials of degree at most $T$.

A measurement-event probability is a sum of products of amplitudes and their conjugates, so it has degree at most $2T$. Replacing $x_i^k$ by $x_i$ gives a multilinear polynomial with the same values on Boolean inputs. This is the Beals–Buhrman–Cleve–Mosca–de Wolf polynomial method.

For a partial Boolean function, let $\deg_D(f)$ be the minimum degree matching $f$ exactly on $D$, and let $\widetilde{\deg}_{\epsilon,D}(f)$ be the minimum degree approximating it within $\epsilon$ there. We impose no off-promise condition on these arbitrary approximants. An actual probability polynomial is more constrained: it lies in $[0,1]$ on the full cube because the algorithm is defined there. Nevertheless the weaker degrees give valid bounds:

$$Q_E(f)\geq\left\lceil\frac{\deg_D(f)}2\right\rceil, \qquad Q_\epsilon(f)\geq\left\lceil\frac{\widetilde{\deg}_{\epsilon,D}(f)}2\right\rceil.$$

For a relation, retain one probability polynomial $p_y(x)$ for each output. Correctness is $\sum_{y\in F(x)}p_y(x)\geq1-\epsilon$, alongside nonnegativity and normalization. There need not be a single input-independent acceptance event.

Parity: a matching algorithm and lower bound

The parity polynomial is

$$\operatorname{PARITY}_n(x)=\frac{1-\prod_{j=1}^n(1-2x_j)}2.$$

Its degree is $n$. Approximation within any $\epsilon<1/2$ still requires degree $n$. To see this, write $s(x)=(-1)^{\sum_jx_j}$ and suppose $p$ approximates parity. Then $r=1-2p$ obeys $|r-s|<1$, so $s(x)r(x)>0$ at every input. But every degree-less-than-$n$ multilinear polynomial is orthogonal to the full parity character under the uniform distribution. Its average product with $s$ must be zero, a contradiction.

One quantum query can recover the parity of a pair. Prepare the index state $(|a\rangle+|b\rangle)/\sqrt2$ and answer $|-\rangle$. After the query, measure the index in the plus/minus pair basis:

$$\frac{(-1)^{x_a}|a\rangle+(-1)^{x_b}|b\rangle}{\sqrt2}.$$

Equal bits give the plus outcome; different bits give the minus outcome. Pair the coordinates and query a leftover bit when $n$ is odd. This constructs an exact algorithm using $\lceil n/2\rceil$ calls, matching the degree lower bound.

A zero-error procedure can be converted to a $1/4$-error Boolean procedure by replacing ? with a fair bit. Thus the same lower bound applies to $Q_0$, and

$$Q_E(\operatorname{PARITY}_n)=Q_0(\operatorname{PARITY}_n) =Q_\epsilon(\operatorname{PARITY}_n)=\left\lceil\frac n2\right\rceil \quad(0\leq\epsilon<1/2).$$

For $n=4$, two pair queries give the final parity. For example, input 1011 gives pair parities 1 and 0, hence total parity 1. This is a constant-factor query improvement over the classical value four, not a change in asymptotic order.

Adversary bounds from distinguishability

An adversary matrix places weights between inputs requiring different answers. For a nonconstant Boolean function $f:D\to\{0,1\}$, choose a nonzero Hermitian matrix $\Gamma$ indexed by $D$ with $\Gamma_{xy}=0$ whenever $f(x)=f(y)$. Let

$$(\Delta_i)_{xy}=\mathbf1[x_i\ne y_i].$$

The negative-weight adversary bound is

$$\operatorname{ADV}^{\pm}(f)= \max_{\Gamma}\frac{\|\Gamma\|_{\mathrm{op}}} {\max_i\|\Gamma\circ\Delta_i\|_{\mathrm{op}}}.$$

The symbol $\circ$ denotes entrywise multiplication. The original positive adversary bound restricts $\Gamma$ to real, entrywise nonnegative matrices. “Positive” here does not mean positive semidefinite. Constant functions have adversary bound zero by convention.

For Boolean output and $0\leq\epsilon<1/2$, the Høyer–Lee–Špalek bound gives

$$Q_\epsilon(f)\geq \frac{1-2\sqrt{\epsilon(1-\epsilon)}}2 \operatorname{ADV}^{\pm}(f).$$

At $\epsilon=1/3$ this prefactor is $(3-2\sqrt2)/6\approx0.0285955$. It is a valid, generally loose constant; it does not turn a matrix ratio into an exact finite query count. The more powerful tightness result is $Q_{1/3}(f)=\Theta(\operatorname{ADV}^{\pm}(f))$, including partial Boolean functions. Neither statement concerns exact-query complexity or gate implementation cost.

The intuition is that different inputs initially produce the same algorithm state. A successful algorithm must eventually distinguish inputs with different answers. The denominator bounds the progress obtainable from one coordinate query, while the numerator measures the total distinction to be achieved. Hybrid arguments follow related state-distance changes directly, as in the Bennett–Bernstein–Brassard–Vazirani search lower bound. A final-information bound such as Holevo’s theorem is not by itself a per-query bound; one still needs to relate progress to individual calls.

A star matrix for promised search

Take the no-mark-versus-one-mark decision promise

$$D=\{0^N,e_1,\ldots,e_N\},\qquad f(0^N)=0,\quad f(e_j)=1.$$

The star matrix connecting $0^N$ to every $e_j$ is

$$\Gamma=\begin{pmatrix}0&\mathbf1^{\mathsf T}\\\mathbf1&0_N\end{pmatrix}.$$

On the span of the center and uniform leaf vector, it acts as $\sqrt N X$; it vanishes on the remaining leaf combinations. Its norm is therefore $\sqrt N$. Filtering with $\Delta_i$ retains only the center–$e_i$ edge, whose norm is one. The ratio $\sqrt N$ proves an $\Omega(\sqrt N)$ lower bound. Grover search followed by candidate verification gives the matching upper order.

At $N=16$, the star ratio is four. Independently, three Grover iterations followed by one ordinary bit query to verify the measured candidate give a four-query upper bound: success is $0.9613189697265625$ on a one-mark input and one on the all-zero input. The numerical agreement with the star ratio does not prove that four is the optimum; the adversary theorem includes a prefactor.

Classically, $R_{1/3}=8$ for this finite promise. Query eight uniformly chosen distinct positions, return 1 after a hit, and otherwise return 1 with probability $1/3$. Its error is $1/3$ on both input types.

For the lower bound at a proposed cap $q<8$, give $0^{16}$ weight $w=(16-q)/(32-q)$ and spread the remaining probability uniformly over the marks. A deterministic tree can learn only a hit or an all-negative transcript. Querying $q$ distinct positions is at least as informative as stopping earlier or repeating positions. On the negative transcript, guessing 1 errs on the all-zero input with total probability $w$, while guessing 0 misses the unqueried marks with total probability

$$(1-w)\frac{16-q}{16}=w>\frac13.$$

Thus every such tree has average error greater than $1/3$. Yao’s principle rules out randomized depth $q<8$ too. The hard distribution may depend on the candidate depth.

Reductions, composition and existence of algorithms

Restricting the input promise transfers a lower bound to a larger problem under the same oracle and output definition. A more general reduction must count each call used to simulate the other interface and preserve correctness and error.

For partial Boolean $f:D_f\subseteq\{0,1\}^m\to\{0,1\}$ and $g:D_g\subseteq\{0,1\}^k\to\{0,1\}$, use disjoint $k$-bit blocks and the full composed domain of block inputs in $D_g$ whose $g$-outputs lie in $D_f$. Then

$$\operatorname{ADV}^{\pm}(f\circ g) =\operatorname{ADV}^{\pm}(f)\operatorname{ADV}^{\pm}(g).$$

Kimmel’s Appendix A treats the partial-function issue explicitly. Tightness implies bounded-error Boolean query composition up to constants. Arbitrarily restricting the composed domain can make the task easier, and overlapping blocks, relations or many-bit queries require separate results.

An upper bound can follow from an explicit algorithm or from a nonconstructive existence proof. Adversary tightness and composition can establish that a query algorithm exists without furnishing its useful circuit; Kimmel gives examples of this distinction. If an explicit implementation is claimed, its schedule, repetitions, verification and nonquery work must still be supplied. A bare oracle theorem neither resolves BQP versus BPP nor gives a physical speedup.

For concrete separations, continue with Deutsch–Jozsa, Bernstein–Vazirani and Simon, whose promises and query units differ. Lower bounds and limitations discusses input/output and runtime barriers beyond query counts.

Exercises

Classify the model and currency

A bounded-error procedure uses 40 oracle calls arranged in ten sequential rounds. Each oracle call is synthesized with 800 logical gates and coherent depth 120; nonquery processing adds 12,000 gates, depth 900, 70 nonquery ancillas, and 500 classical operations. State which numbers are query count, rounds, gates, depth, memory, and classical work. Which runtime or hardware conclusions follow without an additional conversion model?

Solution

The query count is 40 and the query-round count is 10. Oracle synthesis contributes

$$40(800)=32{,}000$$

logical gates, so the total logical-gate count is $44{,}000$. If each round contains four oracle calls that genuinely run in parallel, oracle depth contributes $10(120)=1{,}200$ rather than $40(120)$; including nonquery depth gives $2{,}100$. That depth conclusion depends on the stated parallel-access license and scheduling assumption. The nonquery workspace uses 70 ancillas; any additional oracle workspace and the data register must be included before claiming a total memory requirement. The reported classical work is 500 operations.

No wall-clock time, physical-qubit count, error-correction overhead, energy cost, or hardware advantage follows. Those claims require gate durations, connectivity and routing, code parameters, factory and control costs, memory construction, readout, and a matched classical implementation. Even the depth total would change if the four calls in a round contend for one oracle implementation.

Exact, zero-error, or bounded-error?

Classify three fixed-cap contracts: (a) the algorithm always outputs the unique correct bit within 25 queries; (b) within 25 queries it outputs the correct bit or ?, never a wrong bit, and $\Pr[?]\le1/2$; (c) within 25 queries it always outputs a bit and is correct with probability at least $2/3$. Explain why ? is not an error of the same kind as an incorrect bit.

Solution

Contract (a) is exact and establishes $Q_E(f)\le25$. Contract (b) is zero-error under this page’s conclusive/inconclusive fixed-cap convention and establishes $Q_0(f)\le25$. Contract (c) is bounded-error with $\varepsilon=1/3$ and establishes $Q_{1/3}(f)\le25$.

An incorrect bit asserts a false answer and contributes directly to the error probability. The symbol ? certifies no answer at all. Because a zero-error procedure never lies when it concludes, it can be repeated or combined with a stopping rule; the cost of the inconclusive branches must then be counted. Replacing ? by a random bit can convert a Boolean zero-error routine to an ordinary bounded-error one, but it changes the output contract.

Amplification pays for every call

A Boolean decision procedure uses $T$ queries and has independent-run error probability $p<1/2$ on every promised input. Repeat it an odd number $r$ of times and return the majority bit. Derive a constant-error guarantee, count the queries, and name the independence assumptions. Why is the same rule not automatic for a relation?

Solution

Let $X_j$ indicate an error on run $j$. With fresh workspace, fresh measurements, and independent random seeds or independent preparations, the $X_j$ are independent Bernoulli variables with means at most $p$. Majority fails only if $\sum_jX_j\ge r/2$. Hoeffding’s inequality gives

$$\Pr[\text{majority error}] \le \exp\!\left[-2r\left(\frac12-p\right)^2\right].$$

Choosing any odd

$$r\ge \frac{\ln(1/\delta)}{2(1/2-p)^2}$$

up to rounding makes the error at most $\delta$. The amplified procedure uses exactly $rT$ oracle calls; repetitions do not make the base queries free.

For a general relation, several different outputs may all be valid for the same input, so a bitwise or plurality majority need not return any valid output. Amplification requires an output-combining rule whose validity is proved, or a verifier whose own queries and error are included.

Degree of an acceptance polynomial

Prove that a $T$-query bit-oracle algorithm has final event probabilities of degree at most $2T$. Include the distinction between a partial-domain approximation and the full-cube probability polynomial, and explain the modification for relation outputs.

Solution

Initially each basis amplitude is constant in $x$. In a complete bit query, an output amplitude is assembled from an old amplitude multiplied by either $x_i$ or $1-x_i$, so one call raises degree by at most one. An input-independent unitary forms fixed linear combinations and does not raise degree. Induction gives complex amplitudes of degree at most $T$.

A measurement-event probability is a sum of terms $a(x)\overline{a(x)}$, hence has real degree at most $2T$. On Boolean inputs, replacing every $x_i^k$ with $x_i$ makes it multilinear without changing its values. For a partial function, an approximate-degree witness need only approximate on $D$ under the convention used here; no off-promise bound is imposed on an arbitrary approximant. An actual event probability nevertheless remains in $[0,1]$ on the full cube because it comes from a fully defined algorithm.

For a relation, use one polynomial $p_y$ for each output. They obey nonnegativity and $\sum_yp_y=1$, while correctness is the joint constraint $\sum_{y\in F(x)}p_y(x)\ge1-\varepsilon$ on $D$. There may be no single input-independent “accept” event.

Exact four-bit parity

Reconstruct the two pair-parity queries, enumerate all sixteen inputs, and use degree four for the matching lower bound. State the exact, zero-error, and fixed-bounded-error values.

Solution

For a pair $(a,b)$, prepare $(|a\rangle+|b\rangle)|{-}\rangle/\sqrt2$. One bit query produces the plus pair-basis state when $x_a\oplus x_b=0$ and the minus state when it is 1. Query $(1,2)$ and $(3,4)$ and XOR those two certain outcomes.

For each of the sixteen inputs, the XOR of the two pair outputs equals the XOR of all four bits. Its real multilinear polynomial has degree four; its approximate degree is also four for every fixed error below $1/2$. The degree-$2T$ bound gives $T\ge2$, matching the construction. Replacing a zero-error routine’s ? by a fair bit gives error at most $1/4$, so the same lower bound applies. Therefore

$$Q_E(\operatorname{PARITY}_4) =Q_0(\operatorname{PARITY}_4) =Q_\varepsilon(\operatorname{PARITY}_4) =2$$

for every fixed $\varepsilon<1/2$.

Star adversary matrices

For the no-mark-versus-one-mark promise, compute the eigenvalues of the star witness and the norm of every coordinate-filtered matrix for $N=4$ and $N=16$. State precisely what the resulting ratios prove.

Solution

Let $|c\rangle$ be the center and $|u\rangle=N^{-1/2}\sum_j|e_j\rangle$ the uniform leaf vector. The star matrix satisfies

$$\Gamma|c\rangle=\sqrt N|u\rangle, \qquad \Gamma|u\rangle=\sqrt N|c\rangle,$$

and annihilates the $N-1$ leaf vectors orthogonal to $|u\rangle$. Its spectrum is therefore $\{\sqrt N,-\sqrt N,0^{(N-1)}\}$ and its norm is $\sqrt N$.

For each $i$, $\Gamma\circ\Delta_i$ keeps only the center–$e_i$ edge. Its nonzero block is

$$\begin{pmatrix}0&1\\1&0\end{pmatrix},$$

with eigenvalues $\pm1$, so every filtered norm equals one. At $N=4$, the witness norm and ratio are 2; at $N=16$, they are 4.

The adversary theorem turns these ratios into a bounded-error quantum lower bound with its theorem-dependent constant, and the family gives the $\Omega(\sqrt N)$ scale. The ratios do not assert exact optimal query counts 2 and 4, do not supply the upper-bound search procedure, and say nothing by themselves about gates or runtime.

Restriction, reduction, and Boolean block composition

Assess three proposed transfers: (a) restrict total OR to inputs of Hamming weight at most one; (b) compose partial Boolean $f$ and $g$ on disjoint blocks, using every block input in $D_g$ whose $g$-output string lies in $D_f$; (c) replace a relation on overlapping blocks accessed by a many-bit value oracle with the Boolean block product theorem. Which retain the hypotheses needed by the result?

Solution

Proposal (a) is a valid restriction for a lower bound. Any algorithm solving total OR under the same bit-query, output, and error convention also solves the promised subset, so a lower bound for that subset transfers to total OR.

Proposal (b) uses the full compatible composed domain and satisfies the Boolean block hypotheses. An additional promise restricting those block inputs would require a new argument. With $x^{(j)}\in D_g$, disjoint blocks, and $(g(x^{(1)}),\ldots,g(x^{(m)}))\in D_f$, one may use

$$\operatorname{ADV}^{\pm}(f\mathbin\bullet g) = \operatorname{ADV}^{\pm}(f) \operatorname{ADV}^{\pm}(g).$$

Adversary tightness then gives fixed-bounded-error query composition up to constants.

Proposal (c) does not satisfy the theorem’s hypotheses: the output is a relation, blocks overlap, and the query unit is a many-bit value call rather than the specified coordinate bit call. It needs a separately proved composition or reduction that charges the interface simulation and preserves valid outputs and error. The Boolean product equality cannot simply be imported.

Separate a search upper bound from its witness

For the $N=16$ no-mark-versus-one-mark decision problem, explain why three Grover queries plus one verification query give bounded error below $1/3$. Compare this upper bound with the star ratio four and the exact classical fixed-cap value eight. Does the star witness prove optimality of the four-query algorithm?

Solution

On a one-mark input, three Grover iterations produce the marked index with probability $0.9613189697265625$. Verification outputs 1 exactly when that candidate is marked. On the all-zero input it always outputs 0, regardless of the measured candidate. Thus the worst error is about $0.0386810$ with a cap of four calls.

The star ratio is also four, but the displayed adversary lower bound is that ratio times a prefactor, not four itself. It proves an asymptotic square-root lower bound across the family, not this finite optimum. The classical result eight follows from the separate matching randomized construction and hard-distribution argument above.

References

• A. Ambainis, “Quantum Lower Bounds by Quantum Arguments,” Journal of Computer and System Sciences 64, 750–767 (2002), doi:10.1006/jcss.2002.1826.
• R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, “Quantum Lower Bounds by Polynomials,” Journal of the ACM 48, 778–797 (2001), doi:10.1145/502090.502097.
• C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing 26, 1510–1523 (1997), doi:10.1137/S0097539796300933.
• H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka, “Bounds for Small-Error and Zero-Error Quantum Algorithms,” in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 358–368 (1999), doi:10.1109/SFFCS.1999.814607.
• E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “A Limit on the Speed of Quantum Computation in Determining Parity,” Physical Review Letters 81, 5442–5444 (1998), doi:10.1103/PhysRevLett.81.5442.
• P. Høyer, T. Lee, and R. Špalek, “Negative Weights Make Adversaries Stronger,” in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 526–535 (2007), doi:10.1145/1250790.1250867.
• S. Kimmel, “Quantum Adversary (Upper) Bound,” Chicago Journal of Theoretical Computer Science 2013, Article 4 (2013), doi:10.4086/cjtcs.2013.004.
• B. W. Reichardt, “Reflections for Quantum Query Algorithms,” in Proceedings of the Twenty-Second Annual ACM–SIAM Symposium on Discrete Algorithms, 560–569 (2011), doi:10.1137/1.9781611973082.44.
• A. C.-C. Yao, “Probabilistic Computations: Toward a Unified Measure of Complexity,” in Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 222–227 (1977), doi:10.1109/SFCS.1977.24.