Affiliate disclosure

Book titles on this page link to Amazon. As an Amazon Associate, DataField.Dev earns from qualifying purchases — at no additional cost to you.

Further Reading: Grover's Algorithm

Tagged Tier 1 (confident it exists and recommended) and Tier 2 (real and worth seeking, but verify the current version or URL).

The primary sources

  • Grover, "A fast quantum mechanical algorithm for database search" (1996 STOC; arXiv:quant-ph/9605043). The original, and note the title — the "database" framing comes from the paper itself, which is a large part of why Case Study 2's misconception is so durable. Read it for the construction and read §21.7 for what the framing costs. Tier 1.
  • Boyer, Brassard, Høyer, and Tapp, "Tight bounds on quantum searching" (1998), Fortschritte der Physik 46, 493. The paper that supplies the iteration-count analysis this chapter measures: $P(k) = \sin^2((2k+1)\theta)$, the optimal $k$, the multiple-solutions case, and the algorithm for when $M$ is unknown — which is Case Study 1's fix, published two years after Grover. Tier 1.
  • Bennett, Bernstein, Brassard, and Vazirani, "Strengths and Weaknesses of Quantum Computing" (1997), SIAM Journal on Computing 26, 1510. The BBBV lower bound: no quantum algorithm does unstructured search in $o(\sqrt N)$ queries. This is what makes Grover optimal rather than merely good, and it is why §21.1 says the quadratic speedup is the price of dropping the promise. Exercise 21.27's subject. Tier 1.
  • Brassard, Høyer, Mosca, and Tapp, "Quantum Amplitude Amplification and Estimation" (2002), AMS Contemporary Mathematics 305, 53. The generalization: Grover with an arbitrary initial state preparation instead of $H^{\otimes n}$, plus quantum counting, which is the principled way to determine $M$. Exercise 21.26 and 21.29's subject. Tier 1.

On what Grover costs

  • Any current work on fault-tolerant Grover resource estimates for AES. Several groups have published detailed T-counts for AES-128/192/256 under Grover, and the numbers are the concrete form of §21.6's argument. They are also revised downward periodically, so check the date — Chapter 15 Case Study 1's lesson about Gidney and Ekerå applies here too. Tier 2.
  • NIST's post-quantum cryptography documentation on security categories. Where the "Grover halves symmetric key strength" claim is turned into concrete guidance, including the parallelization caveat §21.7 raises. The most practically useful thing on this list if you work in security. Tier 1.
  • Chapter 15's resource estimator, applied to your own oracle. §21.6's table is one predicate; the method transfers, and grover_cost() in this chapter's checkpoint does the accounting. Tier 1.

On the database misconception

  • Aaronson's writing on Grover and QRAM. The clearest available treatment of why "unstructured database search" is the wrong framing, and why QRAM does not rescue it. Case Study 2's argument owes its structure to this material. Tier 1.
  • Giovannetti, Lloyd, and Maccone, "Quantum Random Access Memory" (2008), Physical Review Letters 100, 160501. The QRAM proposal itself. Read it alongside the critiques — the architecture requires $\mathcal{O}(N)$ components, which is the crux. Tier 1.
  • Any careful analysis of quantum machine learning speedup claims that depend on QRAM. A substantial fraction of proposed QML advantages assume efficient state preparation from classical data, which is the same $\mathcal{O}(N)$ problem in different clothing. Directly relevant to Chapter 32. Tier 2.
  • Literature on amplitude estimation and its applications — Monte Carlo integration, option pricing, and related numerical problems. These are the settings where the quadratic speedup applies to something other than search, and where the constants are sometimes more favourable. Tier 2.
  • Work on Grover-based approaches to constraint satisfaction and optimization. Realistic assessments here are worth more than optimistic ones; look for papers that price the oracle rather than counting queries. Tier 2.

Forward references

  • Chapter 22 — phase estimation, which is what quantum counting runs on, and therefore the principled answer to Case Study 1's "how do I know $M$?"
  • Chapter 23 — the exponential speedup, for contrast: what it looks like when the conditions genuinely hold.
  • Chapter 38 — the security consequences of both Grover and Shor, and what post-quantum cryptography does about them.
  • Chapter 15 §15.8 — the T-gate cliff that makes §21.6's totals mean what they mean.

Where to go next. If one thing: Boyer, Brassard, Høyer, and Tapp. It contains the analysis this chapter measures and the unknown-$M$ algorithm that Case Study 1's team needed — published in 1998, and still routinely omitted from tutorials that hard-code $M = 1$.

If two: add BBBV, because knowing Grover is optimal changes how you read every "quadratic speedup" claim — the bound is not a gap waiting to be closed.

Then Chapter 22 — the Quantum Fourier Transform, where Chapter 19's one bit of phase kickback becomes many, and Part IV turns toward its most consequential result.