Grover's search

Unstructured search: you have a predicate check(x) over N candidates and want an x where it returns true, with no structure to exploit — no sorting, no gradient, no index.

Clear one thing up immediately: this is not "searching a database". The oracle is a computable function compiled into a reversible circuit — a SAT clause check, a hash-preimage test, a constraint validator. If your data lives in storage, loading it into a quantum-addressable form costs at least N operations by itself, which erases the saving before the search begins.

Evaluate the predicate on candidates until one passes: expected N/2 evaluations, worst case N. Without structure, no classical algorithm does better than linear. What classical hardware does have is cheap parallelism — a thousand cores each take a slice, dividing wall-clock time by a thousand. Remember that when comparing a single QPU against real infrastructure.

It does not try all items at once and pick the winner — that mental model predicts a one-query algorithm, and Grover provably needs ~√N. Here is what actually happens, with real numbers for our 8-item demo.

Start in an equal superposition: all 8 amplitudes equal 0.354 (that is 1/√8). Each iteration has two moves:

• Oracle: flip the sign of the marked state's amplitude. Marked: −0.354. Probabilities are amplitudes squared, so nothing observable changed yet.
• Diffusion: reflect every amplitude about the mean. The mean dropped to 0.265, so the seven unmarked amplitudes fall to 0.177 while the marked one jumps to 0.884. Probability of the marked state: 78% after one iteration.

A second iteration lifts it to 94.5%. Each round rotates the state by the same small angle toward the marked state, which is why ~(π/4)√N rounds are needed — and why running past the optimum rotates away from the answer again. The speedup comes from amplitudes adding linearly while probabilities are their squares — nothing more exotic.

Grover's is provably correct and provably optimal — and still hard to turn into practical advantage.

• Quadratic, not exponential. It halves the exponent of brute force: 2^128 becomes 2^64 queries. This is why symmetric cryptography answers Grover by doubling key lengths, not by panicking — see the RSA-2048 reality check for the contrast with Shor's genuinely exponential threat.
• Every query costs a full oracle circuit. The predicate runs as a reversible circuit inside each of the √N iterations. An expensive predicate multiplies the whole runtime.
• No stored-data search. Searching data in memory needs QRAM, which does not exist at scale.
• Error correction may eat the advantage. Published resource estimates (Google's Babbush et al., 2021, among others) conclude that quadratic speedups are unlikely to beat classical hardware once error-correction overheads and slower logical clock speeds are priced in, at any feasible problem size.
• Queries are sequential. The √N iterations cannot be parallelised across machines the way classical search trivially can.

Where it may genuinely matter: as a subroutine amplifying other quantum algorithms, and for problems whose predicate is cheap and whose scale sits in a narrow window — see what counts as quantum advantage.

Two- and three-qubit Grover demonstrations succeed on all major platforms — the 3-qubit version here has run above 90% success on trapped-ion hardware. That is the current honest ceiling for clean results.

The obstacle is depth. Our two-iteration demo is ~40 gates before transpilation, and each CCX expands into six or more two-qubit gates on real devices (native gates and transpilation). Add a qubit and you double the search space but also deepen the circuit; noise compounds per gate, and beyond a handful of qubits the output is indistinguishable from uniform noise without error correction. Run the demo in the Lab, then check the compiled depth against real topologies on the comparison page.