Retrieval-augmented generation (RAG) is the now-standard way of letting a language model answer questions from an external library. A search step finds the most relevant passages among millions, and the model reads them before answering. Quantum algorithms are often advertised as speeding up exactly this kind of search: Grover-style search finds the best of $N$ items with about $\sqrt{N}$ evaluations instead of $N$. That promise rests on an assumption that is easy to overlook. The quantum computer must be able to read any stored passage vector "in superposition," meaning it can look up many addresses at once. The hardware that would do this is called quantum random access memory (QRAM), and it does not exist at scale. A careful critique argues it may never be cheaper than simply spending the same control hardware on classical search (QRAM: A Survey and Critique).
This note proposes to settle, with measured numbers rather than asymptotics, whether quantum search can help RAG at all, and if so where. The argument has three pieces. First, a counting bound says that any quantum lookup over a corpus, QRAM or not, must pay at least as many gates as the corpus has incompressible bits. Second, those bits can be measured directly: we find the smallest number of bits per passage that preserves retrieval quality on real benchmarks. Third, an end-to-end test checks whether exact search, the only thing quantum search would add over classical approximate search, changes answer accuracy at all. Together these turn a vague "QRAM is a problem" into a concrete break-even map. That map could show the opportunity is empty, or it could point to the narrow regime where it is not.
Core Claim
The claim is that the cost of any coherent oracle over a RAG corpus is bounded below by $N \cdot b^\star$ gates per call. Here $N$ is the number of retrievable units and $b^\star$ is the minimum bits per unit that keep retrieval recall at a target level. The counting argument behind this is that a reversible circuit whose output can depend on each of $N b^\star$ independent stored bits must touch each of them. Proving it carefully is part of the work. A Grover-type top-$k$ search makes about $\sqrt{Nk}$ oracle calls, so its total gate count is at least $\sqrt{Nk}\, N b^\star$. A classical brute-force scan pays about $N b^\star$.
So any quantum advantage for RAG retrieval must come from one of two sources. One is parallel depth, which the opportunity-cost argument of Jaques and Rattew disputes. The other is corpora whose relevance scores can be computed from a description much shorter than $N b^\star$. The QRAM-free range-minimum structure of Quantum data structure for range minimum query gets its $\Theta(\sqrt{nq})$ bound by assuming the array is available as an oracle. Our bound says what that oracle costs when the array is a real text corpus. This is the piece the existing literature leaves unquantified for retrieval.
Research Program
The first component is the bound itself. We will formalize the gate-count lower bound for oracles that store classical vectors. It applies to bucket-brigade QRAM, to read-only quantum memory, and to arbitrary compressed circuits. We will then specialize it to the access model used in Sublinear Time Quantum Algorithm for Attention Approximation. That paper approximates transformer attention in time sublinear in sequence length, but it explicitly assumes a QRAM oracle to $Q, K, V$. We will show what its sublinear preprocessing becomes if $n$ is reinterpreted as corpus size.
The second component measures $b^\star$. We take the passage embeddings of a dense retriever on two corpora: the 22-million-chunk Wikipedia corpus, and the 600,000 four-thousand-token units of LongRAG. We then compress them with product quantization and binary hashing at decreasing bit budgets. Recall@k is recorded on Natural Questions and HotpotQA. The smallest budget within one point of full-precision recall defines $b^\star$. Coarsening shrinks $N$ but may raise $b^\star$, because a 4K-token unit carries more content per vector. The product $N b^\star$ is therefore the quantity to compare, not $N$ alone.
The third component builds a resource model with three oracle realizations. The first is bucket-brigade QRAM with the pipelined protocol of Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory, which reduces access time from $O(nk)$ to $O(n+k)$ for word length $k$; we feed it the measured $b^\star$ as $k$. The second is a read-only lookup circuit. The third is the best compressed circuit we can find, a small network mapping passage id to quantized code. Each is charged gate count, depth, and the classical control processors it requires. We also count the coherence it needs, using the storage-time ratios of Quantum Memory: A Missing Piece in Quantum Computing Units. Those ratios put trapped ions and neutral atoms above $10^5$ and superconducting qubits near $10^4$.
The fourth component multiplies per-call cost by realistic call counts. Active and multi-hop systems retrieve many times per answer. Active Retrieval Augmented Generation (FLARE) retrieves whenever token confidence drops. Multi-Hop Dense Retrieval (MDR) chains beam-searched retrievals. We will log the number of retrieval calls per question for both and fold them into the cost.
Baselines
The naive reference point is classical brute-force exact inner-product search over the full-precision index. It is the method whose cost Grover search nominally improves on, and it defines the accuracy ceiling for exact retrieval. Its cost is measured on the same hardware and corpus as everything else. Exact search is not always the obvious choice even classically, as the title of To Index or Not to Index: Optimizing Exact Maximum Inner Product Search suggests. We will report brute-force cost alongside, not instead of, indexed search.
The strongest competitor on cost is a classical approximate index, a navigable small-world graph (HNSW) tuned for recall. This is the structure practitioners already pick to balance speed, build time and recall, and in practice it is already sublinear per query. Any quantum proposal must beat it at matched recall, so it gets the same embeddings, the same recall targets, and a fixed tuning sweep over its graph parameters. A quantum design "beats" it only if the modeled cost is lower at equal Recall@k and equal end-to-end exact match. The cost includes control hardware, counted as the classical processors that could otherwise run HNSW.
The strongest competitor on accuracy is LongRAG. It reports 62.7% exact match on Natural Questions, 64.3% exact match on HotpotQA, and Recall@1 rising from 52% to 71% by coarsening units. For multi-hop retrieval, MDR reports 81.2 supporting-passage exact match on HotpotQA. For active retrieval, FLARE reports 51.0 exact match on 2WikiMultihopQA, against 39.4 for single-time retrieval. We rerun LongRAG and FLARE with HNSW and with exact search under identical readers. That makes the accuracy delta attributable only to search exactness.
The ablation that isolates the key ingredient swaps full-precision vectors for $b^\star$-bit codes inside every pipeline. If end-to-end accuracy holds, then $b^\star$ is the right quantity to charge the quantum oracle.
Why not just…?
Why not just cite Jaques and Rattew and stop? Their critique (QRAM: A Survey and Critique) is general and mostly asymptotic. It does not say how large $N b^\star$ is for real retrieval corpora, how coarsening trades $N$ against bits per unit, or whether exactness matters for answers. The contribution here is those constants. If they confirm the critique, the RAG-specific version becomes a usable no-go result rather than an inference.
Why not just use HNSW? This is the real threat, and the proposal treats it as the default winner. HNSW is already sublinear in practice, while Grover search is $\sqrt{N}$ before oracle costs. The only target left for quantum search is exact retrieval. The decisive end-to-end experiment asks whether exact search improves exact match over HNSW at all. If it does not, there is nothing to accelerate, and we say so.
Why not just coarsen the corpus as LongRAG does? Coarsening is classical, free and effective. It is part of the measured design space, not an alternative to it. If coarsening lowers $N b^\star$ more than any oracle design lowers per-bit cost, the map will show it, and the recommendation will be purely classical.
Why not just apply quantum attention to the long-context reader instead? Song et al. assume QRAM access to the context and cannot yet handle causal masking (Sublinear Time Quantum Algorithm for Attention Approximation). The same counting bound applies to the ~30,000-token LongRAG context, and we will compute it. That reader cost is reported as a second row of the break-even map.
Proposed Experiments
The first decisive check runs LongRAG and FLARE on Natural Questions, HotpotQA and 2WikiMultihopQA under three conditions: exact search, HNSW at 0.95 recall, and HNSW at 0.99 recall. If the exact-match difference between exact search and HNSW at 0.99 recall is within seed noise, exact quantum search has no accuracy rationale.
The second check measures $b^\star$ on both corpora and plugs it into the three oracle cost models. The output is the crossover corpus size, if any, at which quantum top-$k$ beats HNSW in wall-clock time at equal hardware budget. The prediction is that no crossover exists for incompressible corpora. A positive finding would require $b^\star$ to fall sharply with coarsening or with learned compressed circuits. The compression curve directly tests that possibility.
The third check folds in measured retrieval calls per answer from FLARE and MDR. Repeated retrieval multiplies quantum and classical costs equally but also multiplies coherence demands. This tells us whether active RAG makes the quantum case worse.
Throughout, accuracy is reported as exact match, F1 on Qasper and MultiFieldQA-en, and supporting-passage exact match for HotpotQA. Cost is reported as gates, depth, control processors and coherence time.
References
- QRAM: A Survey and Critique
- Quantum data structure for range minimum query
- Sublinear Time Quantum Algorithm for Attention Approximation
- LongRAG: Enhancing Retrieval-Augmented Generation with Long-context LLMs
- Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory
- Quantum Memory: A Missing Piece in Quantum Computing Units
- Active Retrieval Augmented Generation
- Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
- To Index or Not to Index: Optimizing Exact Maximum Inner Product Search