Query complexity

Query complexity counts calls to an oracle. It does not count gates inside the call. The two measures answer different questions, and swapping them is the most common way a quantum speedup gets mis-quoted.

Grover's algorithm is a query algorithm: on the order of the square root of N calls for one marked item among N. Bennett, Bernstein, Brassard, and Vazirani prove that, relative to a random oracle, you should not expect a quantum Turing machine to solve NP in substantially less than the square root of the search space. That is a lower bound on queries, in the oracle model they define. Shor's algorithm is not stated that way. Its bound is a gate count for concrete arithmetic, modular exponentiation included. Amplitude amplification stays inside query accounting when the amplified procedure is itself charged per use. If a page gives a big-O expression, the first question is which of these it is counting. The HHL page keeps two accountings apart: a 2009 gate-time bound, and a later count of queries to a sparse-entry oracle. Neither is a search bound. A different query question, how many membership queries it takes to learn a halfspace, is the subject of the digest of 19 Oct 2026. The logarithmic bound there does not cancel a linear gate cost.