Case Study 2: The Database That Was Never There

The proposal

A company has a large customer database — tens of millions of records — and slow lookups on unindexed fields. Someone reads that Grover's algorithm searches an unsorted database of $N$ items in $\sqrt N$ steps and proposes a quantum accelerator.

The arithmetic is compelling. Ten million records, $\sqrt{10^7} \approx 3{,}163$. A three-thousandfold speedup on their worst query pattern.

The description they read is the standard one. It appears in press releases, popular articles, and a depressing number of technical introductions.

It is wrong, and the way it is wrong is worth being precise about, because the underlying capability is real — just not this one.

What the oracle actually is

Grover queries $O_f$, and $O_f$ is a unitary you construct out of gates.

$$O_f|x\rangle = (-1)^{f(x)}|x\rangle$$

To search real data, $f$ must recognize the target among your records. That means the records have to be encoded into the circuit — the oracle must contain, in some form, the information that record 4,829,110 is the one matching the query.

Constructing that oracle requires touching all $N$ records.

$$\underbrace{\mathcal{O}(N)}_{\text{build the oracle}} \;+\; \underbrace{\mathcal{O}(\sqrt N)}_{\text{Grover search}} \;=\; \mathcal{O}(N)$$

The first term dominates and the speedup vanishes. You have done a linear scan to build the thing that lets you avoid a linear scan.

And you have to do it again for every query, because the oracle encodes what you are looking for, not just the data.

The QRAM objection, and why it does not rescue this

The standard rebuttal is QRAM: a hypothetical quantum memory that returns $\sum_x |x\rangle|D_x\rangle$ in superposition, letting the oracle consult the data without enumerating it.

Three problems, and they compound.

QRAM does not exist. There is no demonstrated device, and the proposed architectures require a number of components proportional to $N$ — a bus of $\mathcal{O}(N)$ switches for $N$ addresses.

Building the QRAM is itself $\mathcal{O}(N)$. Loading ten million records into a quantum memory is ten million operations. If the data changes, you reload.

And the error-correction burden is severe. The QRAM must stay coherent across all $\sqrt N$ Grover iterations — a fault-tolerant memory of $N$ items, which Chapter 15's accounting prices well beyond the search itself.

So the honest position is: Grover's $\sqrt N$ is a real bound on queries, and for actual stored data the query is not the expensive part.

What Grover is genuinely for

The capability is real. It applies when the "database" is implicit — a space of candidates that is never enumerated, recognized by a circuit that is small compared to the space.

In every case the oracle is small and the space is enormous, which is exactly the opposite of the database situation, where the oracle would have to be as large as the data.

$$\text{Grover helps when } |{\text{oracle}}| \ll N, \text{ not when } |{\text{oracle}}| \sim N$$

That is a clean criterion, and it disqualifies database search immediately.

And even then, the constants

Suppose the problem does fit — an implicit space, a small oracle. Chapter 21 §21.6 priced it:

     n         N       iterations       TOTAL T
    16    65,536              201        44,622
    20 1,048,576              804       229,944

Through Chapter 15's estimator, a 16-bit search needs 278,010 physical qubits and 0.3 seconds. Classical brute force at 20 bits is under a second on one core.

Quantum wins when $\sqrt N > c_q/c_c$, and with fault-tolerant T gates against classical clock cycles that ratio is $10^9$–$10^{12}$ — requiring $N > 10^{18}$.

A quintillion. Ten million is not close.

Where it does hold: a 128-bit key space is $N = 2^{128} \approx 3\times10^{38}$, and $\sqrt N = 2^{64}$. That is the regime the constants stop mattering in, and it is why Grover's practical significance is cryptographic — a point Chapter 21 §21.7 develops with the necessary qualifications about parallelization.

The counter-question worth asking

The team's actual problem was slow lookups on unindexed fields.

Build an index. A B-tree gives $\mathcal{O}(\log N)$ — for ten million records that is about 23 comparisons, against Grover's 3,163 fault-tolerant iterations.

$$\text{classical index: } \mathcal{O}(\log N) \;\ll\; \text{Grover: } \mathcal{O}(\sqrt N)$$

The classical algorithm is exponentially better than the quantum one, because the problem has structure — sortable keys — and Grover's $\sqrt N$ is a bound for unstructured search.

Grover is optimal for unstructured search, and almost nothing real is unstructured. That is Chapter 19 §19.7's third gap — the classical lower bound holds only for query-only algorithms — in its most practical form.

The lessons

"Grover searches a database" is false, and the precise reason is that the oracle is a circuit. Data must be encoded into it, which costs $\mathcal{O}(N)$ before the $\mathcal{O}(\sqrt N)$ begins.

The criterion is oracle size against space size. Grover helps when the oracle is small and the space is enormous — hash preimages, key recovery, constraint satisfaction. It cannot help when the oracle would have to be as large as the data.

Check whether the problem is actually unstructured. Grover's bound is optimal for unstructured search, and sortable, indexable, or prunable data is not unstructured. A B-tree beats Grover by an exponential on the problem in this case study.

Constants decide near-term relevance, and here they decide it against. A quadratic speedup with a $10^9$ constant needs $N > 10^{18}$, which is the cryptographic regime and essentially nowhere else.

And the most useful response to "can quantum speed this up?" is often "what is the best classical algorithm?" — which in this case was an index, took an afternoon, and beat the quantum proposal by more than the quantum proposal claimed to beat brute force.

Reproduce it: code/example-03-what-grover-costs.py prices the search and works through the crossover arithmetic.