Oracle

An oracle, in the sense Grover's algorithm uses, is a black box that computes a predicate on an index and reveals nothing else. One call counts as one query. The algorithm's theorems are about how many calls suffice and how many are required.

The box is not a database product. If evaluating the predicate means scanning a classical table of N entries, the scan may dominate the square-root-of-N queries. If the predicate is a compact circuit — a key schedule, a constraint check — then each query has a gate cost and the total gate cost is queries times that cost. Query complexity is the name for the first accounting. Gate complexity is the name for the second. Bennett, Bernstein, Brassard, and Vazirani use oracles in a different role as well: a random oracle relative to which NP is not solvable too quickly on a quantum Turing machine. Same word, and the paper says which role. HHL assumes a different box. Given a row index, the box returns the nonzero entries of that row. Later linear-systems papers count those lookups. That count is not Grover's predicate count.