Optimality: the BBBV Lower Bound
Why no quantum algorithm beats √N for unstructured search.
Could a cleverer quantum algorithm search items in steps? No. Bennett, Bernstein, Brassard and Vazirani proved that every quantum algorithm needs queries, a result already known when Grover's algorithm showed it to be tight. Their hybrid argument is short enough to carry in your head.
What you’ll learn
- State the BBBV theorem precisely, for the decision and the search versions.
- Prove by the hybrid argument and derive .
- Show that every -query algorithm has average success probability at most , and compare with Grover.
- Describe Zalka's exact optimality, the limits of parallel search, and the consequences for complexity and cryptography.
The statement and the hybrid argument
Fix the search problem with one marked item , accessed through (the bit-flip oracle works the same way: all we use is that differs from only where the query register holds , with ). A -query algorithm produces . Let be the state after steps of the same algorithm with every query replaced by : a run with no marked item.
Add and subtract . The first term carries the old discrepancy forward; the second is the new discrepancy created by querying the unperturbed state.
Triangle inequality and unitarity. acts only on the part of that queries , with norm at most .
The crucial fact: one state cannot query all positions strongly at once. On average it puts weight on each. This is where the lack of structure enters.
Square, sum over , and bound the cross term by Cauchy–Schwarz: .
Induction on .
Decision version. To tell "marked item at " from "no marked item" with error at most , the two final states need overlap , hence , for every . Summing over , , so .
A sharp bound on success
Grover's algorithm achieves while , so the bound is tight in that regime. Inverted, average success requires .
and an algorithm making queries. What is the largest average success probability this bound allows, in percent?
Show the answer
4 %
. Grover's algorithm reaches here, essentially matching it; high success needs .
Exact optimality and consequences
Parallel search. Zalka also showed that quantum computers working in parallel cannot beat the obvious strategy of splitting the space into parts and running Grover on each: time , a speedup of only from machines, whereas classical search parallelizes perfectly.
Small error. Driving the error down to costs queries (Buhrman, Cleve, de Wolf & Zalka 1999), less than repeating Grover times.
Complexity. BBBV's own corollary: relative to a random oracle, with probability , is not contained in quantum time . Black-box quantum search cannot solve NP-complete problems efficiently.
Cryptography. Generic key search against a -bit cipher costs about quantum evaluations, and no generic attack does better. Doubling key lengths restores the margin; in practice the long sequential depth and error-correction costs make Grover attacks far costlier than suggests, and post-quantum security definitions account for this by bounding circuit depth.
Does the BBBV theorem prove that ?
- Yes: SAT is a search problem, so it needs quantum time
- No: it is an oracle result, and a quantum algorithm for SAT could exploit the formula's structure, which a black box hides
- Yes, but only under randomized reductions
- No, because BBBV only considers classical queries
Show the answer
B. No: it is an oracle result, and a quantum algorithm for SAT could exploit the formula's structure, which a black box hides
BBBV bounds algorithms that access the search space only through an oracle. A real SAT instance is given explicitly, and an algorithm may exploit its structure. Separating from unconditionally would in particular separate from , which remains open.
Key takeaways
- Hybrid argument: , because a query moves the state by at most and .
- Distinguishing every from "no marked item" forces , hence ; average success is at most .
- Zalka: Grover's algorithm is optimal even in the constant, and parallel machines achieve only time .
- Relative to random oracles NP needs quantum time: generic search cannot solve NP-complete problems efficiently, and symmetric keys need only doubling.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Where does the hybrid argument use the absence of structure in the search problem?
- In the unitarity of the
- In : a single state spreads its query weight over all possible marked positions
- In the triangle inequality
- In assuming the final measurement is in the computational basis
Show the answer
B. In : a single state spreads its query weight over all possible marked positions
Each query can increase by at most , and the sum to over the candidates: a query cannot be "aimed" at the unknown . With structure (say, a sorted list) the relevant states would not be related this way.
Success for every forces for a constant . Combined with , this gives
Show the answer
D.
gives .
With quantum computers working in parallel, the best possible time for unstructured search over items is
- once
Show the answer
A.
Zalka showed that splitting the space into parts of size and running Grover on each is optimal, giving time : machines buy only a factor .
Every -query algorithm has average success probability at most . For and target average success , the bound says is at least about
Show the answer
C.
. Grover needs with , about : within of the bound.
Further reading
- C. H. Bennett, E. Bernstein, G. Brassard & U. Vazirani, "Strengths and weaknesses of quantum computing", SIAM J. Comput. 26, 1510–1523 (1997).
- C. Zalka, "Grover's quantum searching algorithm is optimal", Phys. Rev. A 60, 2746 (1999).
- M. Boyer, G. Brassard, P. Høyer & A. Tapp, "Tight bounds on quantum searching", Fortschritte der Physik 46, 493–505 (1998).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §6.6 (Cambridge, 10th anniv. ed., 2010).
- R. de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415.