Query Complexity

Query complexity isolates the cost of learning enough about an input through a declared black-box interface. Once the problem, promise, output, error guarantee, and oracle action are fixed, it asks how many licensed oracle calls are sufficient or necessary. That abstraction can expose genuine quantum–classical separations while deliberately leaving gate synthesis, data loading, memory, noise, and runtime outside the count.

The central task is therefore not merely to quote a bound. It is to define comparable deterministic, randomized, exact quantum, zero-error quantum, and bounded-error quantum measures; construct a valid query schedule; select a lower-bound certificate with the right hypotheses; and state exactly what the result does not establish. This page develops that workflow for finite functions and relations, then tests it on parity and promised search.

Required background. Quantum Oracles supplies the fixed problem family, promise, registers, complete oracle action, phase representative, and separately licensed forward, inverse, controlled, powered, or family capabilities whose calls are counted here.

Helpful background. Algorithmic Primitives supplies the access–processing–interference–readout composition pattern and its resource currencies. Classical Information Review supplies the matched representation, output, error, construction, and total-cost comparator needed before a query advantage can support a broader claim.

Query Problems after the Access Contract

Let the promised input domain and valid-output relation be

$$D\subseteq\{0,1\}^n, \qquad F\subseteq D\times Y, \qquad F(x)\ne\varnothing,$$

where $Y$ is finite and $F(x)=\{y:(x,y)\in F\}$. A function is the special case $F(x)=\{f(x)\}$. The size parameter $n$ identifies a family of finite problems; a query bound becomes asymptotic only when its dependence on that parameter is stated.

The primary access representative on this page is the complete bit-query unitary

$$O_x|i,b,z\rangle = |i,b\mathbin\oplus x_i,z\rangle,$$

where $i$ selects a coordinate, $b$ is a one-bit answer register, and $z$ denotes untouched workspace. The action is defined for every $x\in\{0,1\}^n$, even though correctness is required only for $x\in D$. This full-space definition prevents a query procedure from depending on an unspecified off-promise action.

Fixing $O_x$ does not silently grant a phase oracle, a controlled oracle, a powered query, a coherent family, a cheaper inverse, or a physical implementation. A phase query can be derived from this Boolean bit query by preparing the answer register in $|{-}\rangle$, but the call and the preparation must still belong to the declared model. Other conversions can require capabilities that an uncontrolled black box does not provide.

A query result is consequently conditional: it concerns the stated family, promise, output relation, error regime, and access unit. Changing any of those ingredients can change both the algorithm and the lower bound. The useful organizing question is:

After the access contract is fixed, how many declared oracle calls solve the promised problem at the stated error, and which resources remain outside that statement?

The Ten-Field Query-Complexity Record

Use the following record whenever a query bound or separation is audited. Every field receives a value or a justified N/A; an unknown or deliberately excluded cost is not the same as a quantity that does not apply.

1. Problem family and size. State whether the task is a function or relation, identify the size parameter, and name the asymptotic variable.
2. Domain, promise, and instance. Give the promised subset, valid-output relation, and finite instance being checked.
3. Oracle interface and licensed access. Specify the complete action, registers, off-promise convention, and any separately licensed phase, inverse, controlled, powered, or family capability.
4. Output, success, and error. Give the output alphabet, validity condition, error regime, tolerance, and per-input success requirement.
5. Model and adaptivity. Name the deterministic, randomized, exact quantum, zero-error quantum, or bounded-error quantum model, including adaptive choices, measurements, and query rounds.
6. Query measure and cost convention. Identify the exact $D$, $R_\varepsilon$, $Q_E$, $Q_0$, or $Q_\varepsilon$ quantity, distinguish a fixed cap from any separately named expected convention, and state what one query costs.
7. Upper-bound procedure and composition. Give an executable schedule, any reduction or block composition, postprocessing, amplification, and the stopping rule under their stated hypotheses.
8. Lower-bound method and certificate. Name the polynomial, adversary, hybrid, reduction, composition, or explicitly scoped information argument and its checkable witness.
9. Matched comparator and excluded resources. Match promise, access, output, error, and cost convention, then list construction, gates, time, memory, noise, and other resources outside the comparison.
10. Conclusion, evidence, and handoff. State the exact count, asymptotic bound, or separation; theorem scope and constants; unsupported extrapolations; and the specialist owners of omitted questions.

The record separates a mathematical query theorem from an implementation or advantage claim. In particular, a lower bound without a matching upper procedure is not an algorithm, and a query separation without a matched nonquery ledger is not an end-to-end speedup.

Classical Decision Trees and Randomized Queries

A deterministic decision tree chooses an index, receives the corresponding bit, and selects its next branch from the transcript. Its depth on an input is the number of queries along that root-to-leaf path. The measure

$$D(F)$$

is the minimum, over trees that always output a member of $F(x)$, of the maximum depth over $x\in D$.

The page’s randomized convention also uses a fixed worst-case cap. A randomized algorithm is a distribution over deterministic trees, each of depth at most $T$, and

$$R_\varepsilon(F)$$

is the least such $T$ for which the returned output belongs to $F(x)$ with probability at least $1-\varepsilon$ for every $x\in D$. Both the success quantifier and the cap are worst-case: averaging cost or error over an unstated input distribution defines a different measure.

Yao’s minimax principle connects worst-case randomized error at a fixed depth to distributional deterministic error. Let $\mathcal T_q$ be the finite set of deterministic trees of depth at most $q$, let $\ell(A,x)$ be one when $A$ returns an invalid output and zero otherwise, and let $\Delta(S)$ denote distributions over a finite set $S$. Then

$$\min_{\lambda\in\Delta(\mathcal T_q)} \max_{x\in D} \mathbb E_{A\sim\lambda}\ell(A,x) = \max_{\mu\in\Delta(D)} \min_{A\in\mathcal T_q} \mathbb E_{x\sim\mu}\ell(A,x).$$

To prove $R_\varepsilon(F)>q$, it is therefore enough to find a distribution $\mu$ on the promise for which every depth-$q$ deterministic tree has average error greater than $\varepsilon$. That hard distribution can depend on $q$ and on the target error. The equality above is a fixed-depth statement; transferring it unchanged to an expected-query stopping model would mix two different optimization problems.

Decision trees are adaptive because their next queried coordinate may depend on earlier answers. Nonadaptivity, parallel batches, and a fixed number of rounds are additional restrictions. A statement about total sequential queries alone need not control any of those finer resources.

Quantum Query Algorithms

After purification and deferred measurement, a $T$-query quantum algorithm can be written in the fixed-schedule form

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

where every $U_j$ is independent of the hidden input $x$. The workspace can coherently record branches that a measured description would call adaptive; a final measurement then returns an element of the declared output alphabet. Deferring measurement changes the representation of the procedure, not the number of oracle calls.

The input dependence enters only through $O_x$. This fact underlies both upper- and lower-bound reasoning. For an upper bound, the displayed product must be executable using the licensed oracle, including every uncomputation, verification call, repetition, and conditional restart. For a lower bound, it allows one to track how amplitudes, state overlaps, or another progress measure can change with each call.

Quantum query count is not the number of coherent branches. A single query on a superposition can change relative phases across many indices, but the algorithm still has one joint state and a constrained measurement. Conversely, an oracle call can hide a large reversible circuit, a long physical evolution, or a costly memory construction. The query model treats that operation as one unit only because the access contract says so.

The sequence above counts total calls, not query rounds. Several queries may be executable in parallel if the model supplies parallel copies of the interface, while a sequential procedure may require a long coherent horizon even when its abstract query count is modest. Round complexity, gate count, depth, width, memory, sample count, coherent time, construction cost, and wall-clock time remain separate currencies.

Exact, Zero-Error, and Bounded-Error Measures

This page uses a fixed worst-case query cap for all five primary measures:

• $D(F)$ is the minimum worst-case deterministic depth for an always-valid output.
• $R_\varepsilon(F)$ is the minimum cap for a distribution over depth-bounded trees that is valid with probability at least $1-\varepsilon$ on every promised input.
• $Q_E(F)$ is the minimum fixed number of quantum queries for a valid output with probability one.
• $Q_0(F)$ is the minimum fixed number of quantum queries for an output in $Y\cup\{?\}$ that is never an invalid member of $Y$ and satisfies $\Pr[?]\le 1/2$ on every promised input.
• $Q_\varepsilon(F)$ is the minimum fixed number of quantum queries for a valid output with probability at least $1-\varepsilon$ on every promised input.

Unless another value is displayed, bounded error means $\varepsilon=1/3$. For Boolean functions, independent repetition followed by majority vote changes any fixed error below $1/2$ to another fixed constant at a constant-factor query cost. A relation needs a declared way to combine or verify candidate outputs before the same amplification argument applies. Exact finite counts can also depend on the chosen constant even when asymptotic classes do not.

The inconclusive symbol in $Q_0$ is different from a wrong output. A fixed-$T$ procedure that is always valid when conclusive and is inconclusive with probability at most $1/2$ can be repeated until it concludes, giving worst-input expected cost at most $2T$. In the other direction, suppose an always-correct stopping procedure has worst-input expected cost $L$. Truncating it after $2L$ queries and reporting ? when it has not stopped gives, by Markov’s inequality,

$$\Pr[\text{more than }2L\text{ queries}] \le \frac{L}{2L} = \frac12.$$

Thus the fixed-cap and worst-input expected stopping conventions are related within a factor of two, but they are not literally the same finite measure. A classical conclusive/inconclusive fixed-cap analogue can be written $R_0^{\mathrm{cap}}$ only after the definition is given. Older symbols $R_2$ and $Q_2$ denote two-sided bounded error, not an error value of two, and zero-error notation is not uniform across the literature. Newer quantum Las Vegas query-mass definitions are not denoted by $Q_0$ here.

Upper Bounds, Reductions, and Composition

An upper bound is an executable schedule. It must say which oracle representative is called, how many calls each stage makes, how intermediate outcomes affect later calls, how candidates are checked, and when the procedure stops. If a subroutine is repeated $r$ times, its query cost is debited $r$ times. Describing an interference idea without this schedule does not establish an upper bound.

A restriction can transfer a lower bound from a subproblem: any algorithm for the larger problem would also solve the restricted family without extra queries. A more general query reduction must preserve the promise, valid outputs, error guarantee, and query unit, while charging every call used to simulate one interface from another. A reduction that changes a bit query into unit-cost coherent value access, or a decision output into a witness without verification, has not preserved the model.

Composition needs equally explicit hypotheses. Let

$$g:D_g\to\{0,1\}, \qquad D_g\subseteq\{0,1\}^k,$$

and

$$f:D_f\to\{0,1\}, \qquad D_f\subseteq\{0,1\}^m.$$

For disjoint blocks $x^{(1)},\ldots,x^{(m)}\in D_g$ whose output string lies in $D_f$, define the compatible Boolean block composition

$$(f\mathbin\bullet g) \bigl(x^{(1)},\ldots,x^{(m)}\bigr) = f\!\left(g(x^{(1)}),\ldots,g(x^{(m)})\right).$$

The negative-weight adversary bound obeys the exact product theorem

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

Together with adversary tightness, this implies that fixed-bounded-error Boolean query complexity composes up to constant factors. It does not establish the same equality for a general non-Boolean relation, overlapping blocks, an incompatible promise, or a different access model. Formal query reductions and this theorem belong here; procedural coherent composition remains with Algorithmic Primitives.

Amplification is another composition and pays for every constituent call. Batching can change query rounds, and converting a sequential routine into parallel access changes the model. None of these transformations makes oracle construction, readout, or nonquery processing free.

The Polynomial Method

The polynomial method follows the input dependence through the query sequence. Before any query, every computational-basis amplitude is independent of $x$ and hence has degree zero. A bit query routes an amplitude according to $x_i$ and $1-x_i$, increasing its degree by at most one. Each input-independent $U_j$ takes linear combinations without increasing degree. Induction therefore shows that every final amplitude of a $T$-query algorithm is a complex multilinear polynomial of degree at most $T$.

A final measurement-event probability is a sum of squared moduli of amplitudes. It is consequently a real polynomial of degree at most $2T$; replacing $x_i^r$ by $x_i$ for $r\ge1$ gives its unique multilinear representative on the Boolean cube. This degree bound concerns each declared event, not an informal count of paths through the computation.

For a partial Boolean function $f:D\to\{0,1\}$, define $\deg_D(f)$ as the minimum degree of a real multilinear polynomial equal to $f$ on $D$. Define the partial approximate degree used here by

$$\widetilde{\deg}_{\varepsilon,D}(f) = \min\left\{ \deg p: |p(x)-f(x)|\le\varepsilon \text{ for every }x\in D \right\}.$$

This definition imposes no additional off-promise bound on the approximating polynomial. The probability polynomial produced by an actual algorithm is more constrained: it still lies in $[0,1]$ on the full cube because the algorithm and oracle are defined there. Exact and bounded-error algorithms therefore imply

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

For a relation, there need not be one meaningful acceptance event. Use one output probability polynomial $p_y$ for each $y\in Y$. On promised inputs they satisfy

$$p_y(x)\ge0, \qquad \sum_{y\in Y}p_y(x)=1, \qquad \sum_{y\in F(x)}p_y(x)\ge1-\varepsilon \quad (x\in D).$$

Replacing this family by one unexplained “acceptance polynomial” can lose the input-dependent valid-output condition. A polynomial certificate is strongest when the event, domain, approximation convention, and conversion from degree to queries are all displayed.

Adversary, Hybrid, and Information-Theoretic Methods

For a Boolean function $f:D\to\{0,1\}$, let $\Gamma$ be a nonzero real symmetric matrix indexed by promised inputs and constrained by $\Gamma_{xy}=0$ whenever $f(x)=f(y)$. Define the coordinate-difference matrices

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

The positive adversary bound restricts $\Gamma$ to be entrywise nonnegative; “positive” does not mean positive semidefinite. Removing the sign restriction gives the negative-weight bound:

$$\operatorname{ADV}(f) = \max_{\substack{\Gamma\ne0\\ \Gamma_{xy}\ge0}} \frac{\|\Gamma\|} {\max_i\|\Gamma\circ\Delta_i\|}, \qquad \operatorname{ADV}^{\pm}(f) = \max_{\Gamma\ne0} \frac{\|\Gamma\|} {\max_i\|\Gamma\circ\Delta_i\|}.$$

Here $\circ$ is entrywise multiplication and $\|\cdot\|$ is the operator norm. Under the Høyer–Lee–Špalek convention for Boolean output,

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

At $\varepsilon=1/3$, the prefactor is

$$\frac{3-2\sqrt2}{6} \approx0.0285955.$$

That numerical constant must not be transferred unchanged to a general-output theorem, whose hypotheses and error terms differ. For Boolean partial functions and any fixed bounded error below $1/2$, Reichardt’s tightness theorem states

$$Q(f) = \Theta\!\left(\operatorname{ADV}^{\pm}(f)\right).$$

This is an asymptotic equivalence up to constants, not numerical equality and not a theorem about exact, zero-error, gate, runtime, or implementation complexity.

The hybrid method uses a different progress object. It compares states generated by different oracles and bounds how quickly one query can separate them. For unstructured promised search, the Bennett–Bernstein–Brassard–Vazirani argument yields the general $\Omega(\sqrt N)$ scale by accumulating these limited state changes. A valid progress proof has four parts: define a potential, derive the final progress required by the success condition, bound the change caused by one licensed query, and divide required progress by the per-query change.

Information language is safe only with the same bridge. A Holevo bound constrains accessible classical information in a final ensemble; by itself it does not bound the number of queries. A query lower bound additionally needs a lemma controlling information or distinguishability growth per call. In particular, the slogan “one query returns one bit” is false for coherent access. Quantum Entropy owns the Holevo-bound derivation; its role here is only to mark what an information-based query proof would still have to establish.

From Query Bounds to Resource and Complexity Claims

Query theorems are matched-access black-box statements. Under the complete bit-query interface and the no-mark-versus-one-mark promise, unstructured search has randomized query complexity $\Theta(N)$ and quantum query complexity $\Theta(\sqrt N)$ at constant bounded error. The statement compares queries under the same promise, output, and error convention. It does not compare oracle construction, gates, memory, or physical time.

Deutsch–Jozsa Algorithm gives a finite warning against suppressing the error regime: for its constant-versus-balanced promise, $Q_E=1$ and $D=2^{n-1}+1$, but the matched fixed-cap value is $R_{1/3}=2$. Its page owns that promise, circuit, exact constants, and historical interpretation; the general measure conventions and lower-bound methods remain here.

Bernstein–Vazirani Algorithm supplies an error-regime-stable $n$-versus-one example: for every fixed $\varepsilon<1/2$, the hidden linear word requires $n$ matched classical queries but one exact quantum query. Its page owns the linear-rank and Yao specializations; the general query measures and minimax method remain here.

Simon’s Algorithm supplies a different kind of separation. It assumes a promised many-bit function accessed through

$$O_f|x,y\rangle = |x,y\mathbin\oplus f(x)\rangle$$

and a unique hidden XOR period, including an injective branch. For every fixed $\varepsilon<1/2$, its exact, zero-error, and bounded-error quantum measures are each $\Theta(n)$, while $D$ and $R_\varepsilon$ are each $\Theta(2^{n/2})$ under that distinct query unit. Its page owns the coset-state derivation, rank recovery, verification, collision bounds, and exact-algorithm qualifications; the general measures and lower-bound methods remain here. The separation does not prove BQP $\ne$ BPP, a lower bound for factoring, an end-to-end runtime advantage, or a hardware speedup.

The implication boundary can be summarized as follows:

Established statement	Additional evidence needed for a broader claim
A $T$-query upper bound	Oracle construction, nonquery work, error composition, and an executable implementation
A $T$-query lower bound	Confirmation that the practical task obeys the same promise, output, access, and error model
A quantum–classical query separation	A matched total-cost comparator and evidence that hidden costs do not erase the separation
An oracle or relativized separation	Separate reasoning for an unrelativized complexity-class claim

Claims, Hype, and Evidence Standards owns the vocabulary for claim strength. Algorithmic Benchmarking owns end-to-end instances, retries, output-quality estimands, and cost-to-solution; Verification of Quantum Advantage owns the dated comparator and reproduction chain. Resource Estimation Tools owns the translation from abstract calls and logical operations to codes, factories, physical qubits, spacetime, and uncertainty. None belongs inside a bare query count.

Two Worked Query Audits

PARITY_n through the polynomial method

Define

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

For every fixed $\varepsilon<1/2$, parity has exact and approximate degree $n$ on the full cube. To see the nontrivial lower bound, write

$$s(x)=(-1)^{\sum_jx_j}=\prod_{j=1}^{n}(1-2x_j).$$

If $p$ approximates parity within $\varepsilon$ and $r=1-2p$, then $|r(x)-s(x)|\le2\varepsilon<1$. Hence $s(x)r(x)>0$ at every Boolean input, so its uniform average is positive. But any multilinear $r$ of degree less than $n$ has zero coefficient on the full Fourier character $s$, which would force that same average to vanish. This contradiction proves approximate degree $n$; exact degree is the $\varepsilon=0$ specialization. The polynomial lower bound and the pair-query construction below therefore give

$$Q_E(\operatorname{PARITY}_n) = Q_0(\operatorname{PARITY}_n) = Q_\varepsilon(\operatorname{PARITY}_n) = \left\lceil\frac n2\right\rceil.$$

For the zero-error lower bound, replace an inconclusive output by an independent fair bit. The resulting ordinary algorithm has error at most $1/4$, so

$$Q_{1/4}(\operatorname{PARITY}_n) \le Q_0(\operatorname{PARITY}_n),$$

and approximate degree supplies the required lower bound. For the upper bound, prepare the answer register in $|{-}\rangle$. On a chosen pair $(a,b)$, one query maps

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

Measuring in the pair basis $\{(|a\rangle\pm|b\rangle)/\sqrt2\}$ reveals $x_a\oplus x_b$ with certainty. Pair all coordinates and query a leftover bit when $n$ is odd.

For $n=4$, query $(1,2)$ and $(3,4)$ and XOR the two certain outcomes. The complete enumeration is:

$x_1x_2x_3x_4$	$x_1\oplus x_2$	$x_3\oplus x_4$	parity
0000	0	0	0
0001	0	1	1
0010	0	1	1
0011	0	0	0
0100	1	0	1
0101	1	1	0
0110	1	1	0
0111	1	0	1
1000	1	0	1
1001	1	1	0
1010	1	1	0
1011	1	0	1
1100	0	0	0
1101	0	1	1
1110	0	1	1
1111	0	0	0

The audit record is:

1. Problem family and size. The Boolean function is $\operatorname{PARITY}_n$ with asymptotic parameter $n$; the finite audit uses $n=4$.
2. Domain, promise, and instance. The domain is the full cube $D=\{0,1\}^n$ with no promise restriction, and the checked instance family contains all sixteen four-bit strings.
3. Oracle interface and licensed access. One query is the complete bit action $O_x|i,b,z\rangle=|i,b\oplus x_i,z\rangle$ on the full cube. Preparing $b$ in $|{-}\rangle$ derives the phase used by each pair query; no controlled, powered, or family access is assumed.
4. Output, success, and error. The output alphabet is $\{0,1\}$, the valid output is the XOR of all input bits, and the two-query procedure succeeds with probability one and zero inconclusive probability.
5. Model and adaptivity. The finite upper bound is an exact quantum fixed-schedule procedure with two sequential pair queries. The pair choices are nonadaptive, and the two parity outcomes may be stored coherently or measured before their final XOR.
6. Query measure and cost convention. The audit establishes $Q_E=Q_0=Q_\varepsilon=2$ for $n=4$ under the fixed-cap convention, where each complete bit-oracle call costs one. It also uses the same convention for the classical $R_\varepsilon$ comparison.
7. Upper-bound procedure and composition. Query the $(1,2)$ pair basis, query the $(3,4)$ pair basis, and XOR the two certain outcomes. For general $n$, compose $\lfloor n/2\rfloor$ pair queries with one leftover coordinate query when necessary.
8. Lower-bound method and certificate. The real multilinear representation of parity has degree four for the finite audit and degree $n$ generally. Exact or approximate degree gives the matching $\lceil n/2\rceil$ bound; replacing ? by a fair bit transfers the $1/4$-error lower bound to $Q_0$.
9. Matched comparator and excluded resources. Under the uniform hard distribution, any classical tree omitting one coordinate has conditional error $1/2$, so $R_\varepsilon(\operatorname{PARITY}_n)=n$ for $\varepsilon<1/2$. Gate synthesis, state preparation, measurement implementation, memory, noise, and runtime are outside this query comparison.
10. Conclusion, evidence, and handoff. The exact finite result is two quantum queries versus four fixed-cap randomized classical queries for $n=4$; generally it is $\lceil n/2\rceil$ versus $n$. This is a factor-two black-box improvement, not an asymptotic speedup or hardware claim; oracle construction and broader resource interpretation remain with their specialist owners.

OR_N through an adversary certificate

Consider the promised Boolean decision problem

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

Index the first row and column by $0^N$ and the remaining ones by the unit vectors. The matrix

$$\Gamma = \begin{pmatrix} 0 & \mathbf 1^{\mathsf T}\\ \mathbf 1 & 0_N \end{pmatrix}$$

is the adjacency matrix of a star. On the span of the center and the normalized uniform leaf vector it has eigenvalues $\pm\sqrt N$; it vanishes on the orthogonal leaf subspace. Hence $\|\Gamma\|=\sqrt N$. For coordinate $i$, entrywise filtering leaves just the edge between $0^N$ and $e_i$, whose norm is one:

$$\|\Gamma\circ\Delta_i\|=1.$$

The adversary ratio is therefore $\sqrt N$, equal to $2$ for $N=4$ and $4$ for $N=16$. These numbers are witness values, not exact finite quantum query counts.

The audit record is:

1. Problem family and size. This is the promised Boolean no-mark-versus-one-mark decision family with asymptotic parameter $N$; the finite checks use $N=4$ and $N=16$.
2. Domain, promise, and instance. The promise domain is $\{0^N,e_1,\ldots,e_N\}$, the valid output distinguishes no marked coordinate from exactly one, and the principal finite audit is $N=16$.
3. Oracle interface and licensed access. One query is the complete bit action $O_x|i,b,z\rangle=|i,b\oplus x_i,z\rangle$ defined on every $N$-bit string. Phase kickback from an answer qubit in $|{-}\rangle$ is licensed at one bit-query call; no further oracle capabilities are assumed.
4. Output, success, and error. The output is one decision bit, with 0 valid for $0^N$ and 1 valid for every $e_j$. The comparison uses worst-case bounded error $\varepsilon=1/3$.
5. Model and adaptivity. The lower bound applies to fixed-cap bounded-error quantum algorithms with arbitrary input-independent unitaries and deferred measurement. The matched classical comparator permits adaptive randomized decision trees.
6. Query measure and cost convention. The quantum quantity is $Q_{1/3}(f)$ and the classical quantity is $R_{1/3}(f)$, both under fixed worst-case caps. One coordinate bit-oracle call costs one query; gates, rounds, and physical duration are not folded into it.
7. Upper-bound procedure and composition. Grover search supplies a matching $O(\sqrt N)$ query procedure after the same promise and bit-to-phase conversion are fixed. Its rotation law, finite constants, stopping choices, and search-specific verification are not reconstructed in this lower-bound audit.
8. Lower-bound method and certificate. The displayed star matrix is entrywise nonnegative, respects the output partition, has norm $\sqrt N$, and every filtered matrix has norm one. It certifies adversary ratio $\sqrt N$, with finite witness values 2 and 4 at $N=4$ and $N=16$.
9. Matched comparator and excluded resources. A classical randomized algorithm under the same promise, output, error, and bit-query unit needs $\Theta(N)$ queries, while the quantum query complexity is $\Theta(\sqrt N)$. Oracle construction, logical gates, memory, coherent time, noise, readout, and end-to-end runtime remain excluded.
10. Conclusion, evidence, and handoff. The witness proves an $\Omega(\sqrt N)$ quantum lower-bound scale and, with the matching upper bound, a tight asymptotic query result. It does not give the exact finite query count. Grover Search owns the algorithm, rotation constants, stopping rules, and search-specific optimality theorem.

The star above must not be confused with a common witness for exact-one index-finding. There the output identifies which $e_j$ occurred, and $J-I$ on the unit-vector inputs is a clique; its coordinate-filtered matrices are stars. The output relation changes the admissible adversary matrix.

Canonical Owners, Limitations, and Reader Pathways

This page begins only after an oracle contract is fixed and ends before a query theorem is converted into a physical or unrelativized complexity claim. The ownership boundaries are:

• Quantum Oracles owns interface taxonomy, construction, full-space actions, phase representatives, conversions, and separately licensed inverse, controlled, powered, and family capabilities.
• Algorithmic Primitives owns reusable coherent composition and the general multi-resource ledger; this page owns formal query measures, reductions, composition theorems under hypotheses, and lower-bound certificates.
• Grover Search owns marked-subspace rotation, exact success probabilities, finite constants, stopping rules, and the search-specific optimality proof.
• Amplitude Amplification owns the general coherent reduction from $1/a$ measure-and-restart preparations to $O(1/\sqrt a)$ component uses, its known-, unknown-, exact-, and fixed-point schedules, and the transfer of worst-case optimal dependence from bounded-error unstructured search.
• Amplitude Estimation owns the matched $\Theta(1/\epsilon)$ coherent additive-estimation dependence and the approximate-counting lower-bound transfer under the same access, output, error, and success conventions.
• Hamiltonian Simulation Algorithms owns Hamiltonian-specific matched-access method applicability, normalized upper and lower query bounds, and query-to-resource qualifications; this page retains the general query measures, reductions, and lower-bound machinery used to interpret those results.
• Classical Information Review owns the general cross-model and end-to-end comparator; this page compares $D$, $R$, and $Q$ only after promise, access, output, error, and query unit match.
• Quantum Complexity Classes owns uniform families, class definitions, containments, completeness, relativized evidence, and unrelativized class claims. A query separation is not an unrelativized class separation.
• The chapter Quantum Algorithms and Complexity guide provides the wider problem-first claim record and routes a reader from access through algorithms, resources, comparators, and evidence.

Lower Bounds and Limitations owns cross-resource barriers such as loading and explicit-output bottlenecks, no-fast-forwarding implications, matched-access dequantization caveats, noise overhead, and query-to-gate or runtime gaps; this page retains fixed-oracle measures, polynomial, adversary, hybrid, and information-theoretic certificates, reductions, composition, and proved matched-query separations. Quantum Algorithms Frontier and Volume-19 Query Complexity Frontiers remain future owners of evolving research and dated separation records. The reference algorithm index remains a scaffold. These inventory names remain deliberately unlinked until promotion.

A practical reading path is access contract → query model and certificate → named algorithm → matched total-cost audit → evidence claim. Stopping at the query theorem is entirely legitimate, provided its exclusions travel with the conclusion.

Common Query-Complexity Failures

Counting before fixing access. A query number is undefined until the complete oracle action, promise, registers, and licensed capabilities are stated. Unit-cost bit, value, controlled, powered, and physical-evolution calls are different resources.

Mixing fixed caps with expected stopping costs. A constant-factor conversion does not make two finite measures identical. Name the convention before comparing algorithms or quoting an exact value.

Calling a query a gate or a second. One black-box call may hide substantial construction and execution work. Query count can be useful precisely because it abstracts that work, but the abstraction must remain visible.

Transferring a bound across an unmatched reduction. A restriction or simulation must preserve promise, output, error, and query unit. Otherwise the proposed lower bound applies to a different problem.

Using one acceptance polynomial for a relation. When several outputs can be valid and the valid set depends on $x$, retain the full family of output-event polynomials and their normalization.

Reading “positive adversary” as positive semidefinite. The restriction is entrywise nonnegativity. The matrix may have negative eigenvalues, as the promised-search star does.

Exporting a theorem constant beyond its hypotheses. The displayed adversary prefactor is for Boolean output under a specified convention. General-output bounds and other error models need their own statements.

Treating Holevo’s bound as a query lower bound. Accessible final information does not by itself limit information gained per query. A progress measure and per-call change lemma are still required.

Confusing a witness ratio with an exact query count. An adversary matrix certifies a lower bound under a theorem; the finite ratio 4 at $N=16$ is not the assertion that the optimal algorithm uses exactly four calls.

Turning a black-box separation into BQP versus BPP. Oracle evidence can illuminate mechanisms and barriers without resolving an unrelativized class separation or proving end-to-end advantage.

Exercises

1. 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 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 workspace debit is 70 ancillas, and 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.

2. 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.

3. 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.

4. 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.

5. 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.

In lexicographic input order from 0000 through 1111, the first pair parities are

$$0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,$$

the second pair parities are

$$0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,$$

and their XORs are

$$0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0.$$

This enumerates all sixteen inputs and agrees with four-bit parity. 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$.

6. 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.

7. 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 whose $g$-output string always 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 preserve the required contracts?

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) satisfies the compatible Boolean block hypotheses. 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 preserve the theorem’s contract: 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.

8. Full ten-field promised-search audit

Audit the $N=16$ no-mark-versus-one-mark decision problem using the complete record. Include the star certificate, a matched classical comparator, excluded resources, and the Grover handoff.

Solution

1. Problem family and size. The task is the Boolean decision version of unstructured search with family parameter and asymptotic variable $N$; this audit fixes $N=16$.
2. Domain, promise, and instance. The domain is $D=\{0^{16},e_1,\ldots,e_{16}\}$, promised to contain no marked coordinate or exactly one. The valid output is 0 in the first case and 1 in the second.
3. Oracle interface and licensed access. The complete action is $O_x|i,b,z\rangle=|i,b\oplus x_i,z\rangle$ for every $x\in\{0,1\}^{16}$. An answer register in $|{-}\rangle$ derives a phase at one call. A separately licensed inverse is N/A because $O_x^\dagger=O_x$, and any inverse use still debits one ordinary call; controlled, unit-cost powered, and family access are neither required nor licensed.
4. Output, success, and error. The output alphabet is $\{0,1\}$, validity follows the promise above, and the target is worst-case success at least $2/3$, or $\varepsilon=1/3$, on every promised input.
5. Model and adaptivity. The quantum model permits a fixed cap of sequential queries separated by input-independent unitaries and a deferred final measurement. The classical comparator permits adaptive randomized decision trees. Parallel-query copies and a separate round bound are N/A because neither is supplied.
6. Query measure and cost convention. The quantities are $Q_{1/3}(f)$ and $R_{1/3}(f)$ under fixed worst-case query caps. One complete coordinate bit-oracle call costs one; a derived phase action also debits that call.
7. Upper-bound procedure and composition. The matching upper procedure is Grover search under the same promise, using $O(\sqrt N)$ calls across the family with its declared bit-to-phase conversion and readout. At $N=16$ this is a constant-size finite procedure, but its exact constants and stopping choices are delegated to the named algorithm owner rather than inferred from the lower-bound witness.
8. Lower-bound method and certificate. The star matrix connecting $0^{16}$ to all sixteen $e_j$ has nonzero eigenvalues $\pm4$, norm 4, and coordinate-filtered norms 1. Its adversary ratio is 4, certifying the $\sqrt N$ lower-bound scale under the bounded-error adversary theorem.
9. Matched comparator and excluded resources. The randomized classical comparator has the same promise, decision output, $1/3$ error, coordinate access, and fixed cap, and satisfies $R_{1/3}(f_N)=\Theta(N)$ across the family. The $N=16$ audit is one finite member and does not infer an exact constant from $\Theta$ notation. Oracle construction, gates, rounds, width, memory, coherent time, noise, readout, and wall-clock cost are excluded.
10. Conclusion, evidence, and handoff. At $N=16$, the checkable star witness has ratio 4; over the family it supports the tight quantum $\Theta(\sqrt N)$ versus randomized classical $\Theta(N)$ query separation when combined with the upper bound. It is not an exact four-query claim, a gate or runtime advantage, or a class separation. Grover Search owns the algorithm, finite success law, constants, stopping rules, and search-specific optimality theorem.

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.
• D. R. Simon, “On the Power of Quantum Computation,” SIAM Journal on Computing 26, 1474–1483 (1997), doi:10.1137/S0097539796298637.
• 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.