Introduction
A query problem begins with a simple restriction: the input exists, but the algorithm may see it only by asking questions of a specified kind. If the input is a bit string
\[ x=(x_1,x_2,\ldots,x_n)\in\{0,1\}^n, \]
then the most basic question is: “What is the value of \(x_i\)?” One such question is called a query. The query complexity of a computational task is the minimum number of queries needed to solve the task, under a specified model of computation and a specified success requirement.
This book studies what can and cannot be learned under such access rules. The subject is narrow enough to be mathematically clean, but broad enough to touch many central themes in theoretical computer science and quantum algorithms: lower bounds, randomness, approximation by polynomials, semidefinite programming, adversary methods, span programs, quantum walks, communication complexity, learning theory, and oracle separations.
The guiding question is:
If information is available only through queries, how many queries are necessary and sufficient to solve a problem?
This question is intentionally different from the usual question “How much time does the algorithm take?” Query complexity isolates information access from the rest of computation. In many applications, this is exactly the resource of interest. A database lookup may be expensive, while local arithmetic is cheap. A laboratory experiment may be costly, while processing the resulting data is routine. A call to a remote server, a memory hierarchy, or a cryptographic oracle may dominate the running time. Query complexity models such situations by charging for input access and often treating all other computation as free.
This abstraction is old and fruitful in classical complexity theory through the study of decision trees and Boolean function measures, and it became especially powerful in quantum computing after the discovery of quantum query algorithms such as Deutsch–Jozsa, Simon’s algorithm, and Grover search, which showed that quantum access to a black-box input can yield dramatic query advantages over classical access (Deutsch and Jozsa, 1992; Simon, 1997; Grover, 1996).
The first model: asking for bits
Let us begin from the simplest possible setting. There is an unknown input string \(x\in\{0,1\}^n\). An algorithm may choose an index \(i\in\{1,\ldots,n\}\), ask for \(x_i\), and receive the answer. The algorithm may choose later questions depending on earlier answers. At the end, it must output something: perhaps a bit, perhaps an index, perhaps a more complicated object.
For example, define the Boolean function
\[ \mathrm{OR}_n(x)= \begin{cases} 1 & \text{if at least one } x_i=1,\\ 0 & \text{if all } x_i=0. \end{cases} \]
A deterministic classical algorithm for \(\mathrm{OR}_n\) must, in the worst case, inspect all \(n\) bits. If it has seen \(n-1\) zeros, the last unseen bit could still be either \(0\) or \(1\). Thus the answer is not determined until the last bit is queried. In this model, the deterministic query complexity of \(\mathrm{OR}_n\) is exactly \(n\).
This example already contains several key ideas.
First, the input is hidden but structured. The algorithm knows that the input is an \(n\)-bit string and knows the function it wants to compute. It does not know the particular values of the bits.
Second, query complexity is a worst-case measure unless stated otherwise. Saying that deterministic \(\mathrm{OR}_n\) needs \(n\) queries means that every correct deterministic algorithm has some input on which it asks \(n\) questions.
Third, lower bounds are knowledge arguments. To prove that fewer than \(n\) queries do not suffice, we argue that after fewer than \(n\) queries, there remain two possible inputs consistent with everything the algorithm has seen but requiring different outputs.
This last point is one of the great themes of the book. Lower bounds often prove that an algorithm has not yet obtained enough information to distinguish relevant cases. Classical and quantum theories differ in how information can be extracted, but both are governed by rigorous distinguishability arguments.
Oracles and black-box access
The formal object that answers queries is called an oracle. An oracle is not magical; it is simply an interface that specifies how the algorithm may access the input. In the bit-query model, the oracle receives an index \(i\) and returns \(x_i\). We often call the input black-box because the algorithm cannot inspect it directly. It can only interact with it through the oracle.
For example, a graph on \(n\) vertices can be represented by an adjacency matrix \(A\), where \(A_{ij}=1\) means that vertices \(i\) and \(j\) are connected by an edge. In an adjacency-matrix query model, the algorithm may ask, “Is there an edge between \(i\) and \(j\)?” Each such question is one query. The algorithm might be trying to decide whether the graph is connected, whether it contains a triangle, or whether it is bipartite. The graph is not literally mysterious; its representation and the allowed questions are specified. What is hidden is the particular instance.
This distinction matters. Query complexity is not merely about ignorance. It is about controlled access. The oracle determines what information can be acquired in one step.
Functions, promises, and relations
Many query problems ask an algorithm to compute a function
\[ f:D\to E, \]
where \(D\) is the set of valid inputs and \(E\) is the set of possible outputs. When \(E=\{0,1\}\), the function is a Boolean function.
A function is called total if every possible input of the chosen type is valid. For example, \(\mathrm{OR}_n:\{0,1\}^n\to\{0,1\}\) is total.
A function is called partial if it is defined only on some subset \(D\subsetneq\{0,1\}^n\). The condition \(x\in D\) is called a promise. The algorithm is required to be correct only when the promise holds.
Here is a simple promise problem. Suppose \(x\in\{0,1\}^n\) is promised to have either no \(1\)’s or exactly one \(1\). The task is to decide which case holds. This is a partial version of search. Inputs with two or more \(1\)’s are outside the promise, so the algorithm’s behavior on them is irrelevant.
Promise problems are not artificial. They express situations where prior knowledge restricts possible inputs. They are also central in quantum query complexity because some of the strongest quantum-over-classical separations occur for partial functions, including the Deutsch–Jozsa and Simon problems (Deutsch and Jozsa, 1992; Simon, 1997).
A still more general task is a relation problem. Instead of requiring one exact output \(f(x)\), a relation specifies a set of acceptable outputs for each input. Formally, a relation is a subset
\[ R\subseteq D\times E. \]
On input \(x\), the algorithm succeeds if it outputs some \(y\) such that \((x,y)\in R\). For example, in a search problem where at least one marked item exists, any marked index may be accepted. Relation problems are important because many natural algorithmic tasks ask for a witness, not merely a yes-or-no answer.
Randomness changes the question
A deterministic algorithm has no internal randomness. Once the input is fixed, its behavior is fixed. A randomized algorithm, by contrast, may toss coins. It can choose queries randomly and may sometimes be wrong.
The most common success requirement is bounded error: for every valid input, the algorithm must output a correct answer with probability at least \(2/3\). The constant \(2/3\) is conventional. In many models, it can be replaced by any fixed constant greater than \(1/2\), because independent repetition and majority vote reduce the error probability. The study of randomized decision trees and their relation to deterministic and distributional complexity is a classical part of decision-tree complexity theory (Buhrman and de Wolf, 2002).
For \(\mathrm{OR}_n\), randomness helps in some input distributions but not in worst-case bounded-error query complexity by more than constant factors: a classical randomized algorithm still needs \(\Theta(n)\) queries to distinguish the all-zero input from inputs with a single \(1\) with constant success probability. This contrasts sharply with the quantum case.
Quantum queries: asking in superposition
Quantum query algorithms use the same black-box philosophy but a different physical and mathematical model of information processing. A quantum algorithm has a state vector in a finite-dimensional Hilbert space. Instead of querying a single classical index \(i\), it may query a superposition of indices.
Informally, a quantum algorithm can place its query register in a state such as
\[ \frac{1}{\sqrt{n}}\sum_{i=1}^n |i\rangle, \]
which represents a coherent superposition over all indices. A quantum oracle applies a unitary transformation that encodes the input values into phases or auxiliary registers. This does not mean that the algorithm “reads all bits at once.” Measurement outcomes are limited, and quantum information cannot simply be copied or inspected freely. The advantage comes from interference: computational paths can combine so that wrong answers cancel and useful information is amplified.
Grover’s algorithm is the canonical example. It solves unstructured search, and hence computes \(\mathrm{OR}_n\), using \(O(\sqrt n)\) quantum queries. This gives a quadratic improvement over the \(\Theta(n)\) classical randomized query complexity. The matching quantum lower bound was established through early hybrid and oracle lower-bound arguments, showing that Grover’s query complexity is optimal up to constant factors in the black-box model (Grover, 1996; Bennett et al., 1997).
This is one of the central lessons of quantum query complexity:
Quantum algorithms can extract global information from an oracle more efficiently than classical algorithms, but not arbitrarily efficiently.
Understanding the exact boundary between possible and impossible quantum speedups is the main purpose of the field.
Why lower bounds are as important as algorithms
In ordinary algorithm design, an upper bound is an achievement: it gives a method that works. In query complexity, lower bounds are equally central because the model is precise enough that impossibility can often be proved.
A lower bound says that no algorithm of a specified kind can solve the problem using fewer than a certain number of queries. For example, proving that every deterministic algorithm for \(\mathrm{OR}_n\) needs \(n\) queries is a deterministic lower bound. Proving that every quantum algorithm for \(\mathrm{OR}_n\) needs \(\Omega(\sqrt n)\) queries is a quantum lower bound.
Several major lower-bound methods will appear throughout this book.
The polynomial method associates a query algorithm with a polynomial that approximates the function being computed. In the quantum case, a \(T\)-query algorithm gives rise to acceptance probabilities representable by real multilinear polynomials of degree at most \(2T\). This connection yields many quantum lower bounds and makes approximate degree a bridge between approximation theory and quantum algorithms (Beals et al., 2001).
The adversary method studies how well an algorithm can distinguish pairs of inputs with different correct outputs. Each query can make only limited progress in separating such inputs. Ambainis introduced a powerful quantum adversary method, later generalized into spectral and negative-weight forms (Ambainis, 2002; Høyer, Lee, and Špalek, 2007).
The general adversary bound gives a semidefinite-programming characterization of quantum query complexity up to constant factors. This was a major unification: a lower-bound method became, in a precise sense, also an algorithm-design principle through its connection with span programs (Reichardt, 2009; Reichardt, 2011).
A span program is a linear-algebraic model of computation in which one decides whether a target vector lies in the span of available input-dependent vectors. Span programs were introduced in classical complexity theory by Karchmer and Wigderson and later became central in quantum query algorithms because their witness size corresponds closely to the general adversary bound (Karchmer and Wigderson, 1993; Reichardt, 2009).
Thus, modern quantum query complexity is not merely a collection of clever algorithms. It is a mature theory in which algorithms, lower bounds, convex optimization, and linear algebra interact tightly.
What this book is trying to teach
This book has three goals.
The first goal is to build the subject from first principles. We start with deterministic decision trees because they are the cleanest expression of query complexity. A deterministic decision tree is simply a rooted tree whose internal nodes ask input questions and whose leaves output answers. From this simple model arise fundamental measures such as certificate complexity, sensitivity, block sensitivity, and degree. These measures form the classical language needed later.
The second goal is to explain how quantum query complexity changes the picture. Quantum computation is not introduced as mystery or metaphor. We will develop the necessary finite-dimensional linear algebra, define quantum states and measurements carefully, and then define quantum oracles precisely. Only after that will we analyze algorithms such as Deutsch–Jozsa, Bernstein–Vazirani, Simon’s problem, Grover search, amplitude amplification, quantum walks, and span-program algorithms.
The third goal is to prepare the reader for research. This requires more than knowing famous results. It requires learning how to choose a model, formulate a promise, compare total and partial functions, recognize when a polynomial lower bound is appropriate, build an adversary matrix, interpret a semidefinite program, use composition theorems, and identify where known techniques fail.
By the end of the book, a reader should be able to read current papers in query complexity and quantum algorithms with confidence, understand the main proof strategies, and begin asking research-level questions.
A map of the journey
The book begins classically. Chapters 1 through 7 develop the query model, mathematical foundations, deterministic and randomized decision trees, classical lower-bound techniques, Boolean function measures, and the polynomial method. This material is not merely background. Many quantum lower bounds and separations are best understood as refinements or transformations of classical ideas.
Chapters 8 through 11 introduce quantum computation and the quantum query model, then develop the first quantum query algorithms. The emphasis is on mechanisms: phase kickback, interference, Fourier sampling, amplitude amplification, and geometric rotation. These mechanisms recur throughout quantum algorithm design.
Chapters 12 through 16 form the technical core of modern quantum query lower bounds and their algorithmic duals. We study the polynomial method, approximate degree, hybrid arguments, adversary methods, the general adversary bound, and span programs. These chapters explain why quantum query complexity is one of the most mathematically developed parts of quantum algorithms.
Chapters 17 through 23 broaden the theory. We examine composition, direct-sum and direct-product phenomena, separations between classical and quantum models, graph and property-testing problems, quantum walks, learning graphs, relation problems, nonstandard oracles, and connections to communication complexity, learning theory, cryptography, and pseudorandomness.
Chapter 24 surveys research frontiers. The point is not to pretend that the field is complete. It is not. Important open questions remain about total-function separations, approximate degree, graph problems, time-query tradeoffs, noisy and fault-tolerant queries, and the transfer of query algorithms into full computational models.
The right mental model
A useful way to read this book is to treat every query problem as a game between two forces.
The algorithm tries to learn enough about the input while asking few questions.
The lower-bound prover tries to show that, after too few questions, the algorithm cannot distinguish inputs that require different outputs.
In deterministic complexity, the lower-bound prover may keep two possible inputs alive. In randomized complexity, the prover may choose a hard distribution. In quantum complexity, the prover may track inner products, polynomials, adversary matrices, or feasible solutions to semidefinite programs. The technical tools differ, but the philosophical structure is stable: a query lower bound is a proof that information has not yet become distinguishable enough.
At the same time, quantum algorithms show that distinguishability can grow in surprising ways. Grover’s algorithm does not find a marked item by checking locations one by one. Simon’s algorithm does not learn a hidden xor mask by reconstructing the entire function table. Quantum Fourier sampling does not behave like ordinary random sampling from input bits. These algorithms exploit global structure in the oracle, and query complexity gives us the language to say exactly how much structure is being exploited.
The field is beautiful because it is both concrete and abstract. One can ask a simple question about bits, graphs, or marked items, and the answer may require approximation theory, spectral graph theory, convex duality, or quantum measurement theory.
What query complexity does not claim
Because query complexity ignores some computational costs, a query-efficient algorithm is not automatically a time-efficient algorithm. An algorithm might use few oracle calls but require exponential postprocessing. Conversely, a query lower bound does not always imply a time lower bound in an ordinary model, because an ordinary algorithm may access its input differently from the oracle model.
This is not a defect. It is the point of the model. Query complexity studies one resource in isolation. The results are most powerful when the oracle model accurately captures the bottleneck of a real computational setting, or when a query lower bound can be transferred to another model, such as communication complexity.
Quantum query complexity also does not claim that a quantum computer can read an entire database in one query. Superposition access is a specific unitary operation, and measurement restricts what classical information can be extracted. The power of quantum queries lies in interference and distinguishability, not in unlimited parallel reading.
Keeping these limitations in mind will make the theory clearer and prevent common misconceptions.
Beginning the study
We now turn to Chapter 1, where the query model is defined carefully. The first task is to separate three things that are often blended together in informal discussions:
- the input object,
- the oracle interface through which it is accessed,
- the cost measure charged to the algorithm.
Once these are separated, many questions become precise. What counts as one query? What is the difference between a total function and a promise problem? What does it mean to solve a relation? How should we compare deterministic, randomized, and quantum algorithms when they use different kinds of access?
The rest of the book is an extended answer to those questions.
References
Ambainis, A. (2002). Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4), 750–767.
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.
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5), 1510–1523.
Buhrman, H., & de Wolf, R. (2002). Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1), 21–43.
Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907), 553–558.
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).
Høyer, P., Lee, T., & Špalek, R. (2007). Negative weights make adversaries stronger. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (pp. 526–535).
Karchmer, M., & Wigderson, A. (1993). On span programs. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference (pp. 102–111).
Reichardt, B. W. (2009). Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (pp. 544–551).
Reichardt, B. W. (2011). Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 560–569).
Simon, D. R. (1997). On the power of quantum computation. SIAM Journal on Computing, 26(5), 1474–1483.