Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Optimality: the BBBV Lower Bound

Why no quantum algorithm beats √N for unstructured search.

Could a cleverer quantum algorithm search NN items in log⁡N\log N steps? No. Bennett, Bernstein, Brassard and Vazirani proved that every quantum algorithm needs Ω(N)\Omega(\sqrt N) 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 ∑x∥ψTx−ψT∥2≤4T2\sum_x\norm{\psi_T^x-\psi_T}^2\le4T^2 by the hybrid argument and derive T=Ω(N)T=\Omega(\sqrt N).
  • Show that every TT-query algorithm has average success probability at most (2T+1)2/N(2T+1)^2/N, 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 x∈{0,…,N−1}x\in\{0,\dots,N-1\}, accessed through Ox=I−2∣x⟩ ⁣⟨x∣⊗IO_x=\id-2\dyad{x}\otimes\id (the bit-flip oracle works the same way: all we use is that OxO_x differs from I\id only where the query register holds xx, with ∥Ox−I∥≤2\norm{O_x-\id}\le2). A TT-query algorithm produces ∣ψTx⟩=UTOxUT−1⋯U1OxU0∣0⟩\ket{\psi_T^x}=U_TO_xU_{T-1}\cdots U_1O_xU_0\ket0. Let ∣ψt⟩\ket{\psi_t} be the state after tt steps of the same algorithm with every query replaced by I\id: a run with no marked item.

DerivationProof of D_T ≤ 4T²
  1. ∣ψt+1x⟩−∣ψt+1⟩=Ut+1[Ox(∣ψtx⟩−∣ψt⟩)+(Ox−I)∣ψt⟩]\ket{\psi_{t+1}^x}-\ket{\psi_{t+1}}=U_{t+1}\Big[O_x\big(\ket{\psi_t^x}-\ket{\psi_t}\big)+\big(O_x-\id\big)\ket{\psi_t}\Big]

    Add and subtract Ox∣ψt⟩O_x\ket{\psi_t}. The first term carries the old discrepancy forward; the second is the new discrepancy created by querying the unperturbed state.

  2. bt+1,x≤bt,x+2at,x,bt,x:=∥ψtx−ψt∥,at,x:=∥(∣x⟩ ⁣⟨x∣⊗I) ψt∥b_{t+1,x}\le b_{t,x}+2a_{t,x},\qquad b_{t,x}:=\norm{\psi_t^x-\psi_t},\quad a_{t,x}:=\norm{(\dyad{x}\otimes\id)\,\psi_t}

    Triangle inequality and unitarity. Ox−IO_x-\id acts only on the part of ∣ψt⟩\ket{\psi_t} that queries xx, with norm at most 22.

  3. ∑xat,x2=∑x∥(∣x⟩ ⁣⟨x∣⊗I) ψt∥2=∥ψt∥2=1\sum_xa_{t,x}^2=\sum_x\norm{(\dyad{x}\otimes\id)\,\psi_t}^2=\norm{\psi_t}^2=1

    The crucial fact: one state cannot query all NN positions strongly at once. On average it puts weight 1/N1/N on each. This is where the lack of structure enters.

  4. Dt+1≤∑x(bt,x2+4bt,xat,x+4at,x2)≤Dt+4Dt+4=(Dt+2)2D_{t+1}\le\sum_x\big(b_{t,x}^2+4b_{t,x}a_{t,x}+4a_{t,x}^2\big)\le D_t+4\sqrt{D_t}+4=\big(\sqrt{D_t}+2\big)^2

    Square, sum over xx, and bound the cross term by Cauchy–Schwarz: ∑xbt,xat,x≤Dt (∑xat,x2)1/2=Dt\sum_xb_{t,x}a_{t,x}\le\sqrt{D_t}\,\big(\sum_xa_{t,x}^2\big)^{1/2}=\sqrt{D_t}.

  5. D0=0⟹DT≤2T⟹DT≤4T2D_0=0\quad\Longrightarrow\quad\sqrt{D_T}\le2T\quad\Longrightarrow\quad D_T\le4T^2

    Induction on tt.

Decision version. To tell "marked item at xx" from "no marked item" with error at most 13\frac13, the two final states need overlap ∣⟨ψTx∣ψT⟩∣≤223\abs{\braket{\psi_T^x|\psi_T}}\le\frac{2\sqrt2}{3}, hence ∥ψTx−ψT∥≥c=(2−423)1/2≈0.34\norm{\psi_T^x-\psi_T}\ge c=\big(2-\frac{4\sqrt2}{3}\big)^{1/2}\approx0.34, for every xx. Summing over xx, Nc2≤DT≤4T2Nc^2\le D_T\le4T^2, so T≥c2NT\ge\frac c2\sqrt N.

A sharp bound on success

Grover's algorithm achieves sin⁡2((2T+1)θ)≈(2T+1)2/N\sin^2((2T+1)\theta)\approx(2T+1)^2/N while T≪NT\ll\sqrt N, so the bound is tight in that regime. Inverted, average success pp requires T≥12(pN−1)T\ge\frac12\big(\sqrt{pN}-1\big).

Predict before you look

N=106N=10^6 and an algorithm making T=100T=100 queries. What is the largest average success probability this bound allows, in percent?

Show the answer

4 %

(2⋅100+1)2/106=40401/106≈4.0%(2\cdot100+1)^2/10^6=40401/10^6\approx4.0\%. Grover's algorithm reaches sin⁡2(201θ)≈3.99%\sin^2(201\theta)\approx3.99\% here, essentially matching it; high success needs T≈785T\approx785.

Exact optimality and consequences

Parallel search. Zalka also showed that pp quantum computers working in parallel cannot beat the obvious strategy of splitting the space into pp parts and running Grover on each: time Θ(N/p)\Theta(\sqrt{N/p}), a speedup of only p\sqrt p from pp machines, whereas classical search parallelizes perfectly.

Small error. Driving the error down to ε\varepsilon costs Θ(Nlog⁡(1/ε))\Theta\big(\sqrt{N\log(1/\varepsilon)}\big) queries (Buhrman, Cleve, de Wolf & Zalka 1999), less than repeating Grover log⁡(1/ε)\log(1/\varepsilon) times.

Complexity. BBBV's own corollary: relative to a random oracle, with probability 11, NP\mathsf{NP} is not contained in quantum time o(2n/2)o(2^{n/2}). Black-box quantum search cannot solve NP-complete problems efficiently.

Cryptography. Generic key search against a kk-bit cipher costs about 2k/22^{k/2} 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 2k/22^{k/2} suggests, and post-quantum security definitions account for this by bounding circuit depth.

Check your understanding

Does the BBBV theorem prove that NP⊈BQP\mathsf{NP}\not\subseteq\mathsf{BQP}?

  1. Yes: SAT is a search problem, so it needs Ω(2n/2)\Omega(2^{n/2}) quantum time
  2. No: it is an oracle result, and a quantum algorithm for SAT could exploit the formula's structure, which a black box hides
  3. Yes, but only under randomized reductions
  4. 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 NP\mathsf{NP} from BQP\mathsf{BQP} unconditionally would in particular separate P\mathsf{P} from NP\mathsf{NP}, which remains open.

Key takeaways

  • Hybrid argument: ∑x∥ψTx−ψT∥2≤4T2\sum_x\norm{\psi_T^x-\psi_T}^2\le4T^2, because a query moves the state by at most 2at,x2a_{t,x} and ∑xat,x2=1\sum_xa_{t,x}^2=1.
  • Distinguishing every xx from "no marked item" forces DT=Ω(N)D_T=\Omega(N), hence T=Ω(N)T=\Omega(\sqrt N); average success is at most (2T+1)2/N(2T+1)^2/N.
  • Zalka: Grover's algorithm is optimal even in the constant, and pp parallel machines achieve only time Θ(N/p)\Theta(\sqrt{N/p}).
  • Relative to random oracles NP needs Ω(2n/2)\Omega(2^{n/2}) 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.

Question 1

Where does the hybrid argument use the absence of structure in the search problem?

  1. In the unitarity of the UjU_j
  2. In ∑xat,x2=1\sum_xa_{t,x}^2=1: a single state spreads its query weight over all NN possible marked positions
  3. In the triangle inequality
  4. In assuming the final measurement is in the computational basis
Show the answer

B. In ∑xat,x2=1\sum_xa_{t,x}^2=1: a single state spreads its query weight over all NN possible marked positions

Each query can increase ∥ψtx−ψt∥\norm{\psi_t^x-\psi_t} by at most 2at,x2a_{t,x}, and the at,x2a_{t,x}^2 sum to 11 over the NN candidates: a query cannot be "aimed" at the unknown xx. With structure (say, a sorted list) the relevant states would not be related this way.

Question 2

Success for every xx forces DT≥cND_T\ge cN for a constant c>0c>0. Combined with DT≤4T2D_T\le4T^2, this gives

  1. T≥cN/4T\ge cN/4
  2. T≥log⁡2NT\ge\log_2N
  3. T≥N/2T\ge N/2
  4. T≥12cNT\ge\frac12\sqrt{cN}
Show the answer

D. T≥12cNT\ge\frac12\sqrt{cN}

4T2≥DT≥cN4T^2\ge D_T\ge cN gives T≥12cN=Ω(N)T\ge\frac12\sqrt{cN}=\Omega(\sqrt N).

Question 3

With pp quantum computers working in parallel, the best possible time for unstructured search over NN items is

  1. Θ(N/p)\Theta(\sqrt{N/p})
  2. Θ(N/p)\Theta(\sqrt N/p)
  3. Θ(N/p)\Theta(N/p)
  4. Θ(log⁡N)\Theta(\log N) once p≥Np\ge\sqrt N
Show the answer

A. Θ(N/p)\Theta(\sqrt{N/p})

Zalka showed that splitting the space into pp parts of size N/pN/p and running Grover on each is optimal, giving time N/p\sqrt{N/p}: pp machines buy only a factor p\sqrt p.

Question 4

Every TT-query algorithm has average success probability at most (2T+1)2/N(2T+1)^2/N. For N=104N=10^4 and target average success 12\frac12, the bound says TT is at least about

  1. 55
  2. 7070
  3. 3535
  4. 50005000
Show the answer

C. 3535

T≥12(0.5⋅104−1)=12(70.7−1)≈35T\ge\frac12(\sqrt{0.5\cdot10^4}-1)=\frac12(70.7-1)\approx35. Grover needs TT with (2T+1)θ≥π4(2T+1)\theta\ge\frac\pi4, about 3939: within 15%15\% 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.