Query Complexity as a Mathematical Cost Measure

The highlighted passage introduces the central unit of cost in the query model. The input is present, but it is not freely readable. If the hidden input is a bit string

\[ x=(x_1,x_2,\ldots,x_n)\in\{0,1\}^n, \]

then asking for one coordinate, such as “What is \(x_i\)?”, is one query. The query complexity of a task is then the smallest number of such questions needed to solve the task, once we have fixed what kind of algorithm is allowed and what it means for the algorithm to succeed.

This definition looks simple, but it contains several mathematical choices that must be made explicit. Query complexity is not a property of a function alone in complete isolation. It is a property of a function together with an access model, an algorithmic model, and a success criterion.

The input is known in form, hidden in value

In the basic bit-query model, the algorithm knows the length \(n\), knows that the input belongs to \(\{0,1\}^n\), and knows the task it is supposed to solve. What it does not know is the actual sequence of bits.

A query is therefore a controlled request for one piece of information. If the algorithm queries index \(i\), the oracle returns \(x_i\). Formally, in the simplest classical model, the oracle is the map

\[ (i,x)\mapsto x_i, \]

but the algorithm does not get \(x\) directly. It only gets the answer to the index it chose.

This distinction is important. If the input string were written openly on the page, computing many functions would be trivial from the viewpoint of input access: the algorithm could simply read whatever it wanted. Query complexity instead asks: if each inspected bit costs one unit, how many inspected bits are necessary?

For example, suppose the task is to compute

\[ \mathrm{OR}_n(x)= \begin{cases} 1 & \text{if at least one } x_i=1,\\ 0 & \text{if } x_1=x_2=\cdots=x_n=0. \end{cases} \]

A deterministic algorithm can query the bits one at a time and stop as soon as it sees a \(1\). But in the worst case, the input may be \(00\cdots 0\). Then the algorithm must inspect every bit before it can safely output \(0\). Thus the deterministic query complexity of \(\mathrm{OR}_n\) is \(n\).

The reasoning here is not about time in the usual sense. The algorithm might do a large amount of computation between queries, and in the query model that computation is often treated as free. The question is only how many times the algorithm must access the hidden input.

“Minimum number” means optimization over algorithms

The phrase “minimum number of queries needed” means that we look over all algorithms of the specified kind and choose the best possible one.

For a deterministic classical algorithm \(A\), let \(Q_A(x)\) be the number of queries made by \(A\) on input \(x\). If the algorithm must be correct on every input in a domain \(D\), then its worst-case query cost is

\[ Q_A=\max_{x\in D} Q_A(x). \]

The deterministic query complexity of a function \(f:D\to E\) is then

\[ D(f)=\min_{A} \max_{x\in D} Q_A(x), \]

where the minimum ranges over deterministic algorithms that correctly output \(f(x)\) for every \(x\in D\).

This formula is a compact version of the highlighted sentence. The “minimum” is over algorithms. The “number of queries” is usually the worst-case number over valid inputs. The “computational task” may be a function, a promise problem, or a relation. The “specified model” determines which algorithms count. The “specified success requirement” determines what correctness means.

Without these qualifications, the definition would be ambiguous.

The model of computation matters

The same task can have different query complexities in different models. The parent document later distinguishes deterministic, randomized, and quantum query algorithms. The highlighted passage already anticipates that distinction by saying “under a specified model of computation.”

In the deterministic classical model, an algorithm’s future behavior is completely determined by previous query answers. Such an algorithm can be represented as a decision tree: each internal node queries some coordinate \(i\), each outgoing edge corresponds to the answer \(0\) or \(1\), and each leaf gives an output. The depth of the tree is the maximum number of queries made on any input. This is the standard decision-tree view of query complexity [Buhrman and de Wolf 2002].

In the randomized model, the algorithm may use random coins. It may query different locations on different runs, even on the same input. Then the query complexity depends on the required probability of success. A common bounded-error requirement is

\[ \Pr[A(x)=f(x)]\geq \frac{2}{3} \quad\text{for every valid }x. \]

The constant \(2/3\) is conventional rather than sacred. Any fixed constant strictly greater than \(1/2\) often gives an equivalent complexity up to constant factors, because independent repetition can reduce error.

In the quantum model, the allowed query operation is different. A quantum algorithm may query a superposition of indices rather than a single classical index. A common bit oracle acts as a unitary transformation such as

\[ O_x\ket{i,b}=\ket{i,b\oplus x_i}, \]

where \(i\) is an index register, \(b\) is a target bit, and \(\oplus\) denotes addition modulo \(2\). The number of uses of \(O_x\) is the quantum query cost. This model can produce fewer queries for some tasks, most famously Grover search, where the quantum bounded-error query complexity of unstructured search is \(\Theta(\sqrt n)\), while the classical randomized bounded-error complexity is \(\Theta(n)\) [Grover 1996; Bennett et al. 1997].

Thus, the sentence’s phrase “under a specified model of computation” is essential. There is not one universal number called “the query complexity of OR” unless the model and error condition have been fixed.

The success requirement matters too

The highlighted passage also says that query complexity is defined under a “specified success requirement.” This prevents another ambiguity: must the algorithm always be right, or may it sometimes fail?

For deterministic exact computation, success usually means

\[ A(x)=f(x) \quad\text{for all }x\in D. \]

For randomized or quantum bounded-error computation, success usually means that each valid input is answered correctly with probability at least some constant, often \(2/3\). For zero-error randomized computation, the algorithm may output “don’t know” or have random running time, but it must never output an incorrect answer. For relation problems, success means outputting any acceptable witness, not necessarily a unique value.

These choices can change the complexity. Consider a search relation where the input is promised to contain at least one \(1\), and the algorithm must output an index \(i\) such that \(x_i=1\). If there may be many marked indices, several outputs can be correct. This is not exactly a function \(f(x)\), because there need not be a unique answer. The success condition must say what outputs are acceptable.

Similarly, for a promise problem, the algorithm may only be required to work on inputs satisfying the promise. If

\[ D\subsetneq \{0,1\}^n, \]

then correctness is imposed only for \(x\in D\). The behavior outside \(D\) is irrelevant unless the model states otherwise. This is why promise problems can have dramatically different query complexity from total functions.

Query complexity isolates information access

The mathematical point of query complexity is to isolate the cost of learning information about the input. A lower bound says that no algorithm of the given kind can obtain enough relevant information using fewer queries.

For deterministic \(\mathrm{OR}_n\), the lower-bound argument is especially transparent. Suppose an algorithm makes fewer than \(n\) queries on the all-zero input. Then at least one coordinate \(j\) remains unseen. The transcript of answers is consistent with both

\[ x=00\cdots 0 \]

and the input \(y\) that is identical to \(x\) except that \(y_j=1\). These two inputs require different OR values:

\[ \mathrm{OR}_n(x)=0,\qquad \mathrm{OR}_n(y)=1. \]

Because the algorithm has seen the same answers in both cases, it cannot distinguish them. Therefore it cannot be correct on both. This proves that every deterministic exact algorithm needs \(n\) queries in the worst case.

This style of reasoning illustrates the general structure behind query lower bounds. One shows that after too few queries, there remain possible inputs that are indistinguishable to the algorithm but require different outputs. In randomized and quantum models, “indistinguishable” becomes more subtle. It may involve probability distributions, total variation distance, polynomial approximation, inner products between quantum states, or adversary matrices [Beals et al. 2001; Ambainis 2002].

What the highlighted definition does and does not claim

The passage gives a foundational definition, not a theorem about any particular task. It does not by itself prove that a given problem needs many queries. Rather, it establishes what kind of quantity later theorems will estimate.

To verify a query-complexity claim, one must always ask:

What is the input domain \(D\)? What is the oracle allowed to reveal in one query? Is the algorithm deterministic, randomized, or quantum? Is the complexity worst-case, average-case, expected, or bounded-error? What output counts as success?

Once those choices are fixed, the definition becomes mathematically precise. For example, saying

\[ D(\mathrm{OR}_n)=n \]

means exact deterministic worst-case bit-query complexity. Saying

\[ R_2(\mathrm{OR}_n)=\Theta(n) \]

usually means bounded-error randomized worst-case query complexity. Saying

\[ Q_2(\mathrm{OR}_n)=\Theta(\sqrt n) \]

usually means bounded-error quantum query complexity. The notation varies somewhat by author, but the dependence on model and success requirement is universal in the theory.

The highlighted passage is therefore doing careful conceptual work. It prevents the reader from treating “query complexity” as a single informal phrase. Instead, it defines query complexity as an optimized cost measure inside a precisely chosen access model.

References

Ambainis, A. (2002). Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4), 750–767. https://doi.org/10.1006/jcss.2002.1826

Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001). Quantum lower bounds by polynomials. Journal of the ACM, 48(4), 778–797. https://doi.org/10.1145/502090.502097

Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523. https://doi.org/10.1137/S0097539796300933

Buhrman, H., & de Wolf, R. (2002). Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1), 21–43. https://doi.org/10.1016/S0304-3975(01)00144-X

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (pp. 212–219). https://doi.org/10.1145/237814.237866