# Quantum query complexity

Quantum query complexity measures how many black-box accesses to an input a quantum algorithm needs to compute a function of that input. In the query model, an algorithm must compute a function f(x1, ..., xN) whose input bits are available only through a black box that, given an index i, outputs xi; the cost of an algorithm is the number of such queries it makes.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> For over thirty years this model has been a central source of knowledge about both the capabilities and the limitations of quantum computers, because nearly every quantum algorithm, including Grover search and a key subroutine of Shor's factoring algorithm, can be analyzed within it.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup>

| Key fact | Value |
|---|---|
| Unstructured search on N items | N queries classically, Θ(√N) quantumly (optimal)<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Collision problem on n items | Θ(\(n^{1/3}\)) quantum queries<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Element distinctness on \(n\) items | \(\Theta(n^{2/3})\) quantum queries<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> |
| Classical vs quantum, total functions | D(f) = O(Q(f)^4), with examples reaching D(f) ≈ Q(f)^4<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Randomized vs quantum, total functions | R(f) ≈ Q(f)^3 known; optimal exponent lies between 3 and 4<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Largest partial-function separation | One quantum query vs R₂(f) = Ω(√N / log N) classical queries<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> |
| Exact characterization | Q(f) = Θ(Adv±(f)), the negative-weight adversary bound<sup>[3](https://cs.uwaterloo.ca/~breic/papers/fastalg.pdf)</sup> |

## The black-box query model

A query asks the oracle for input bits at chosen positions. Classically, each query reveals one bit xi. A quantum query acts on a superposition: a single query can access multiple bits of the input string, one in each branch of a superposition state.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

Oracle results in the query model relativize: they hold in a world where both classical and quantum machines are given the same oracle, which is both the model's strength and the source of its main caveat about the real world.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

## Upper bounds: what quantum algorithms achieve

The foundational result is unstructured search. The 1994 theorem of Bennett, Bernstein, and Vazirani shows that a quantum computer needs Ω(√N) queries to search an unordered list of size N for a single marked item, proving the optimality of [Grover's algorithm](https://www.edgepedia.org/grovers-algorithm) two years before that algorithm was discovered.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> Search therefore takes N queries classically and O(√N) quantumly, which transfers directly to generic exhaustive-search problems: any 3-SAT instance solvable by brute force over its assignments gains the same quadratic speedup.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup>

Structured problems do better. Brassard, Høyer, and Tapp's collision algorithm uses \(O(n^{1/3})\) quantum queries, together with \(O(n^{1/3})\) bits of classical memory and \(O(\log n)\) qubits. Six years later, Ambainis gave an element distinctness algorithm using \(O(n^{2/3})\) quantum queries and \(O(n^{2/3})\) qubits; the 2002 Aaronson–Shi lower bound showed both query counts optimal.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> Element distinctness, which asks whether all \(n\) input values are different, requires \(N\) queries classically and \(\Theta(N^{2/3})\) quantumly.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup>

These algorithms matter beyond the model. Element distinctness is related to black-box models of algorithms for breaking collision-resistant hash functions, an important cryptographic primitive, and serves as a subroutine in algorithms ranging from checking matrix products to solving typical subset-sum instances.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup>

## The polynomial method

The polynomial method turns an algorithm's behavior into algebra. Beals et al. showed in 1998 that a quantum algorithm making \(T\) queries has an acceptance probability that is a real polynomial of degree at most \(2T\) in the input bits.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> Consequently \(\widetilde{\deg}(f) \le 2Q(f)\) for every function \(f\) computed with bounded error.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup><sup> • </sup><sup>[9](https://arxiv.org/abs/quant-ph/9802049)</sup> A lower bound on the required polynomial degree is therefore a lower bound on queries. For symmetric Boolean functions this connects to approximate degree: \(Q_{\mathrm{E}}(f) \geq \deg(f)/2\), and \(Q_{2}(f) = \Omega(\sqrt{\deg(f)})\).<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup>

Proofs in this style follow a common three-part structure on the distance between the algorithm's final states on a yes-input and a no-input: an initial condition (the states start close), a final condition (they must end at distance at least 1/3 if the algorithm succeeds with probability at least 2/3), and a per-query growth bound on the distance.<sup>[4](https://www.ias.edu/sites/default/files/Hamoudi%20Lecture%201%20July%2024.pdf)</sup>

Beals et al. used the method to show D(f) = O(Q(f)^6) for all total Boolean functions; after Huang's 2019 proof of the Sensitivity Conjecture, this was improved to D(f) = O(Q(f)^4).<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> The method is nonetheless not tight for total functions: Ambainis exhibited gaps between approximate degree and Q(f) in 2003, later improved to a fourth-power gap, which is tight.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

## The adversary method and its characterization

The adversary method proves lower bounds from a progress measure: one fixes a pair of matrices over the input points, with an entry weighting how hard it is to distinguish two inputs, and shows that every query advances the algorithm only a bounded amount toward distinguishing them. The original (positive-weight) form hits a ceiling called the certificate complexity barrier: for element distinctness it cannot prove lower bounds better than \(\Omega(N^{1/2})\), while Aaronson and Shi proved the true \(\Omega(N^{2/3})\) with the polynomial method.<sup>[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.434/LIPIcs.STACS.2013.434.pdf)</sup> Høyer, Lee, and Špalek extended the method by allowing negative weights, and the resulting bound \(\mathrm{ADV}^{\pm}(f)\) breaks that barrier.<sup>[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.434/LIPIcs.STACS.2013.434.pdf)</sup>

The negative-weight variant turns out to capture the whole model. Reichardt's theorem states that for any function f : D → {0,1} with D ⊆ {0,1}^n, the general adversary bound characterizes quantum query complexity: Q(f) = Θ(Adv±(f)), confirming a conjecture and removing an earlier log Adv±(f)/log log Adv±(f) factor.<sup>[3](https://cs.uwaterloo.ca/~breic/papers/fastalg.pdf)</sup> Because the general adversary bound composes, its tightness yields optimal results for the query complexity of composed functions.<sup>[3](https://cs.uwaterloo.ca/~breic/papers/fastalg.pdf)</sup> A 2025 survey adds that the adversary method can also be used to derive upper bounds, not only lower bounds.<sup>[6](https://www.arxiv.org/pdf/2508.08852)</sup>

Neither method contains the other. The adversary bound can be strictly stronger than polynomial degree: Ambainis exhibited a function with polynomial degree \(d\) and adversary bound \(\Omega(d^{1.3})\), and the major lower-bound techniques have been explicitly related through reductions, for example to the multiplicative adversary method.<sup>[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.434/LIPIcs.STACS.2013.434.pdf)</sup> In the reverse direction, for the \(n\)-input collision problem the best plain adversary lower bound is only \(O(1)\), whereas the correct \(\Theta(n^{1/3})\) complexity was determined by the polynomial method together with a matching algorithm.<sup>[3](https://cs.uwaterloo.ca/~breic/papers/fastalg.pdf)</sup>

## By the numbers

| Problem | Classical queries | Quantum queries | Proven by |
|---|---|---|---|
| Search (N items) | N | Θ(√N)<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> | Grover upper bound; Bennett–Bernstein–Vazirani lower bound<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Collision (n items) | n | \(\Theta(n^{1/3})\)<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> | BHT algorithm; Aaronson–Shi lower bound<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Element distinctness (n items) | N | Θ(N^(2/3))<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> | Ambainis's element distinctness algorithm; Aaronson–Shi lower bound<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Total functions, D(f) vs Q(f) | polynomial in Q(f) | D(f) = O(Q(f)^4)<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> | Polynomial method plus sensitivity theorem<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Total functions, R(f) vs Q(f) | gap exponent between 3 and 4 | —<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> | Ben-David examples<sup>[2](https://arxiv.org/pdf/2109.06917)</sup> |
| Partial functions, Q₂ vs R₂ | Ω(√N / log N) | 1<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> | —<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup> |

## Largest separations and what they do and don't prove

For partial functions, where the algorithm only has to be correct on a promised subset of inputs, superpolynomial separations exist. There is a function f with Q₂(f) = 1 and R₂(f) = Ω(√N / log N), while k-Forrelation gives an O_ε(1) versus Ω(N^{1−ε}) separation for any ε>0; for total functions the biggest known gap is much smaller.<sup>[1](https://doi.org/10.1142/9789813272880_0181)</sup><sup> • </sup><sup>[10](https://ir.cwi.nl/pub/30886/)</sup> On the total-function side, Ambainis et al. gave a [Boolean function](https://www.edgepedia.org/boolean-function) with D(f) ≈ Q(f)^4 in 2015, refuting the earlier belief that Grover's quadratic gap was the largest possible, and Ben-David's R(f) ≈ Q(f)^2.5 was later improved to R(f) ≈ Q(f)^3, leaving the optimal exponent between 3 and 4.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

These results are statements about oracle worlds, and oracle separations sometimes mislead about the real world where no oracles are present. A famous example is the 1990 IP = PSPACE theorem: oracle separations had suggested interactive proofs were limited, yet non-relativizing techniques collapsed the classes. The same caution applies to every query-model separation here; non-relativizing techniques have so far made only minor inroads into quantum complexity theory outside [interactive proof systems](https://www.edgepedia.org/interactive-proof-system).<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

## Recent developments

Three developments postdate the standard picture. First, a 2025 survey now organizes quantum query lower-bound techniques into four major methods: the hybrid method, the polynomial method, the recording method, and the adversary method, with the recording method the recent addition to the toolkit.<sup>[6](https://www.arxiv.org/pdf/2508.08852)</sup>

Second, an open problem from the 2021 list was resolved: the relationship between polynomial degree and quantum query complexity for partial functions is now settled in one direction by a 2025 peer-reviewed result demonstrating an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function, with a constant-versus-polynomial separation when the alphabet size is unbounded.<sup>[7](https://link.springer.com/article/10.1007/s00037-025-00277-4)</sup> This supersedes the 2021 listing of the question as open.<sup>[2](https://arxiv.org/pdf/2109.06917)</sup>

Third, the simulation conjecture for constant-round algorithms has been settled by recent work showing that every t-query, d-round quantum algorithm can be simulated on most inputs with \(t^{O(d^2)}\) classical queries, suggesting that for unstructured problems superpolynomial speedups would require quantum circuits of superconstant depth, with new implications for the status of BPP versus BQP relative to a random oracle.<sup>[8](https://arxiv.org/pdf/2608.19158)</sup>

## References

1. Understanding quantum algorithms via query complexity (Ambainis survey), World Scientific. https://doi.org/10.1142/9789813272880_0181
2. How Much Structure Is Needed for Huge Quantum Speedups? / Open problems related to quantum query complexity (Aaronson et al.), arXiv. https://arxiv.org/pdf/2109.06917
3. Reflections for quantum query complexity: The general adversary bound is tight for every boolean function (Reichardt). https://cs.uwaterloo.ca/~breic/papers/fastalg.pdf
4. Quantum query complexity: polynomial and adversary methods (IAS lecture notes, Hamoudi). https://www.ias.edu/sites/default/files/Hamoudi%20Lecture%201%20July%2024.pdf
5. Explicit relation between all lower bound techniques for quantum query complexity (STACS 2013). https://drops.dagstuhl.de/storage/00lipics/lipics-vol020-stacs2013/LIPIcs.STACS.2013.434/LIPIcs.STACS.2013.434.pdf
6. Introduction to quantum query lower bounds (2025 survey), arXiv. https://www.arxiv.org/pdf/2508.08852
7. An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree, Computational Complexity (2025). https://link.springer.com/article/10.1007/s00037-025-00277-4
8. Quantum Speedups Require Structure or Depth (2026), arXiv. https://arxiv.org/pdf/2608.19158
9. Quantum Lower Bounds by Polynomials, https://arxiv.org/abs/quant-ph/9802049
10. Centrum Wiskunde & Informatica: k-Forrelation optimally separates quantum and classical query complexity, https://ir.cwi.nl/pub/30886/

---
*Topic: Encyclopedia › Physical world and mathematics › Physics › Quantum physics › Quantum information science › Quantum computing and algorithms › Quantum complexity theory › Quantum query complexity and lower bounds*

*Initially written Sep 17, 2026 · Edited: Oct 11, 2026; Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license