Simple Algorithm
Quantum Computing · Rydberg State · 26 min

The Geometry of Grover & Optimal Iterations

Two reflections make a rotation.

Grover's algorithm is two mirrors. Reflect about one axis, then about another at angle θ\theta, and you have rotated by 2θ2\theta. Taking that picture seriously gives the exact success probability, the optimal schedule, exact and fixed-point variants, and a surprising identity: Grover's algorithm is a Chebyshev polynomial.

What you’ll learn

  • Prove that two reflections compose to a rotation by twice the angle between their axes, and diagonalize the Grover iterate.
  • Derive optimal iteration counts, the bound P≥1−M/NP\ge1-M/N, and exact amplitude amplification for known aa.
  • Prove the averaging lemma behind exponential search for an unknown number of marked items.
  • Identify Grover's success amplitude as (−1)kT2k+1(a)(-1)^kT_{2k+1}(\sqrt a) and connect it to QSVT.

Two reflections make a rotation

For a unit vector ∣v⟩\ket{v} let Rv=2∣v⟩ ⁣⟨v∣−IR_v=2\dyad{v}-\id: it fixes ∣v⟩\ket{v} and negates its orthogonal complement. In a real plane, the reflection about the line at angle α\alpha is

Rα=(cos⁡2αsin⁡2αsin⁡2α−cos⁡2α).R_\alpha=\begin{pmatrix}\cos2\alpha&\sin2\alpha\\ \sin2\alpha&-\cos2\alpha\end{pmatrix}.
DerivationComposition of reflections
  1. RβRα=(cos⁡2βsin⁡2βsin⁡2β−cos⁡2β)(cos⁡2αsin⁡2αsin⁡2α−cos⁡2α)R_\beta R_\alpha=\begin{pmatrix}\cos2\beta&\sin2\beta\\ \sin2\beta&-\cos2\beta\end{pmatrix}\begin{pmatrix}\cos2\alpha&\sin2\alpha\\ \sin2\alpha&-\cos2\alpha\end{pmatrix}

    Multiply the matrices.

  2. =(cos⁡2(β−α)−sin⁡2(β−α)sin⁡2(β−α)cos⁡2(β−α))=\begin{pmatrix}\cos2(\beta-\alpha)&-\sin2(\beta-\alpha)\\ \sin2(\beta-\alpha)&\cos2(\beta-\alpha)\end{pmatrix}

    Angle-addition formulas; e.g. the top-left entry is cos⁡2βcos⁡2α+sin⁡2βsin⁡2α=cos⁡2(β−α)\cos2\beta\cos2\alpha+\sin2\beta\sin2\alpha=\cos2(\beta-\alpha).

  3. RβRα=Rot(2(β−α))R_\beta R_\alpha=\mathrm{Rot}\big(2(\beta-\alpha)\big)

    A rotation by twice the angle from the first mirror to the second.

In Grover's algorithm the invariant plane is spanned by ∣w⊥⟩\ket{w^\perp} (angle 00) and ∣w⟩\ket{w} (angle π2\frac\pi2). The oracle acts there as Rw⊥R_{w^\perp} and the diffusion as RsR_s, a mirror at angle θ\theta with sin⁡θ=M/N\sin\theta=\sqrt{M/N}. So G=RsRw⊥=Rot(2θ)G=R_sR_{w^\perp}=\mathrm{Rot}(2\theta). Off the plane the operators act differently, but the plane is invariant and contains ∣s⟩\ket{s}, so nothing else matters.

Check your understanding

Two mirror lines through the origin meet at angle α\alpha. Reflecting in one and then in the other is

  1. a reflection about their bisector
  2. a rotation by α\alpha
  3. a rotation by 2α2\alpha
  4. the identity
Show the answer

C. a rotation by 2α2\alpha

RβRα=Rot(2(β−α))R_\beta R_\alpha=\mathrm{Rot}(2(\beta-\alpha)). Each reflection reverses orientation, so the composition preserves it and is a rotation, by twice the angle between the mirrors.

Optimal schedules and exact search

With Pk=sin⁡2((2k+1)θ)P_k=\sin^2((2k+1)\theta) the ideal real-valued count is k~=π4θ−12\tilde k=\frac{\pi}{4\theta}-\frac12. Write π4θ=k∗+ϕ\frac{\pi}{4\theta}=k^\ast+\phi with k∗=⌊π4θ⌋k^\ast=\lfloor\frac{\pi}{4\theta}\rfloor and ϕ∈[0,1)\phi\in[0,1). Then (2k∗+1)θ−π2=θ(1−2ϕ)∈(−θ,θ](2k^\ast+1)\theta-\frac\pi2=\theta(1-2\phi)\in(-\theta,\theta], so

Pk∗ ≥ cos⁡2θ=1−MN,k∗≤π4θ≤π4NM,P_{k^\ast}\ \ge\ \cos^2\theta=1-\frac MN,\qquad k^\ast\le\frac{\pi}{4\theta}\le\frac\pi4\sqrt{\frac NM},

the last step because θ≥sin⁡θ\theta\ge\sin\theta.

Predict before you look

N=220N=2^{20}, one marked item. What is k∗=⌊π/(4θ)⌋k^\ast=\lfloor\pi/(4\theta)\rfloor?

Show the answer

804 iterations

θ=arcsin⁡(2−10)≈2−10\theta=\arcsin(2^{-10})\approx2^{-10}, so π/(4θ)≈π4⋅1024≈804.2\pi/(4\theta)\approx\frac\pi4\cdot1024\approx804.2 and k∗=804k^\ast=804. The failure probability is below 1/N≈10−61/N\approx10^{-6}.

Fixed points. Plain Grover is fragile when θ\theta is uncertain: overshooting rotates you away. Grover's 2005 "π/3\pi/3" algorithm never overshoots but loses the square-root speedup. Yoder, Low and Chuang (2014) found phase sequences whose success probability converges monotonically to at least 1−δ1-\delta for every a≥a0a\ge a_0, using the optimal O(log⁡(1/δ)/a0)O\big(\log(1/\delta)/\sqrt{a_0}\big) queries.

Unknown M: exponential search

DerivationProof
  1. Pˉm=1m∑k=0m−1sin⁡2((2k+1)θ)=12−12m∑k=0m−1cos⁡((2k+1) 2θ)\bar P_m=\frac1m\sum_{k=0}^{m-1}\sin^2\big((2k+1)\theta\big)=\frac12-\frac{1}{2m}\sum_{k=0}^{m-1}\cos\big((2k+1)\,2\theta\big)

    Use sin⁡2u=12(1−cos⁡2u)\sin^2u=\frac12(1-\cos2u).

  2. 2sin⁡x cos⁡((2k+1)x)=sin⁡((2k+2)x)−sin⁡(2kx)2\sin x\,\cos\big((2k+1)x\big)=\sin\big((2k+2)x\big)-\sin(2kx)

    A product-to-sum identity that makes the sum telescope.

  3. ∑k=0m−1cos⁡((2k+1)x)=sin⁡(2mx)2sin⁡x\sum_{k=0}^{m-1}\cos\big((2k+1)x\big)=\frac{\sin(2mx)}{2\sin x}

    Sum the telescoping series and divide by 2sin⁡x2\sin x.

  4. Pˉm=12−sin⁡(4mθ)4msin⁡(2θ) ≥ 12−14msin⁡(2θ) ≥ 14\bar P_m=\frac12-\frac{\sin(4m\theta)}{4m\sin(2\theta)}\ \ge\ \frac12-\frac{1}{4m\sin(2\theta)}\ \ge\ \frac14

    Set x=2θx=2\theta. The last step uses msin⁡2θ≥1m\sin2\theta\ge1.

Exponential search. Start with m=1m=1 and repeat: draw k∈{0,…,m−1}k\in\{0,\dots,m-1\}, run kk iterations, measure, verify with one query; on failure set m←min⁡(λm,N)m\leftarrow\min(\lambda m,\sqrt N) with 1<λ<431<\lambda<\frac43. Until mm reaches 1/sin⁡2θ=O(N/M)1/\sin2\theta=O(\sqrt{N/M}) the cost is a geometric series. After that each round succeeds with probability at least 14\frac14, and λ<43\lambda<\frac43 keeps the expected remaining cost, a series in (34λ)u(\frac34\lambda)^u, convergent. The total expected number of queries is O(N/M)O(\sqrt{N/M}), and if no item is marked the search can be stopped after O(N)O(\sqrt N) queries.

Grover as a polynomial

Write x=a=sin⁡θx=\sqrt a=\sin\theta for the initial success amplitude. Chebyshev polynomials satisfy Tn(cos⁡ϕ)=cos⁡(nϕ)T_n(\cos\phi)=\cos(n\phi), and x=cos⁡(π2−θ)x=\cos(\frac\pi2-\theta), so

T2k+1(x)=cos⁡((2k+1)(π2−θ))=(−1)ksin⁡((2k+1)θ).T_{2k+1}(x)=\cos\Big((2k+1)\big(\tfrac\pi2-\theta\big)\Big)=(-1)^k\sin\big((2k+1)\theta\big).

After kk iterations the success amplitude is (−1)kT2k+1(a)(-1)^kT_{2k+1}(\sqrt a): an odd polynomial of degree 2k+12k+1 in the initial amplitude.

Key takeaways

  • Two reflections whose axes meet at angle θ\theta make a rotation by 2θ2\theta; the Grover iterate has eigenphases ±2θ\pm2\theta on the invariant plane.
  • k∗=⌊π/(4θ)⌋k^\ast=\lfloor\pi/(4\theta)\rfloor gives success at least 1−M/N1-M/N; with aa known, shrinking the angle (or tuning phases) makes it exactly 11.
  • Averaging over a random k<mk<m gives success at least 14\frac14 once m≥1/sin⁡2θm\ge1/\sin2\theta: the basis of O(N/M)O(\sqrt{N/M}) search for unknown MM.
  • The success amplitude is (−1)kT2k+1(a)(-1)^kT_{2k+1}(\sqrt a): Grover's algorithm is a Chebyshev polynomial, the simplest instance of QSVT.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What are the eigenvalues of the Grover iterate GG restricted to span{∣w⟩,∣w⊥⟩}\mathrm{span}\{\ket{w},\ket{w^\perp}\}, where sin⁡θ=M/N\sin\theta=\sqrt{M/N}?

  1. ±1\pm1
  2. e±2iθe^{\pm2i\theta}
  3. e±iθe^{\pm i\theta}
  4. cos⁡2θ±sin⁡2θ\cos2\theta\pm\sin2\theta
Show the answer

B. e±2iθe^{\pm2i\theta}

GG is a rotation by 2θ2\theta of a real plane, whose eigenvalues are e±2iθe^{\pm2i\theta} with eigenvectors 12(∣w⊥⟩∓i∣w⟩)\frac{1}{\sqrt2}(\ket{w^\perp}\mp i\ket{w}).

Question 2

In exponential search, why is the number of iterations kk chosen at random from {0,…,m−1}\{0,\dots,m-1\}?

  1. To hide the marked item from an adversary
  2. Because random circuits are easier to compile
  3. To make the algorithm exact
  4. Because the average of sin⁡2((2k+1)θ)\sin^2((2k+1)\theta) over such kk is at least 14\frac14 once m≥1/sin⁡2θm\ge1/\sin2\theta, whatever the unknown θ\theta
Show the answer

D. Because the average of sin⁡2((2k+1)θ)\sin^2((2k+1)\theta) over such kk is at least 14\frac14 once m≥1/sin⁡2θm\ge1/\sin2\theta, whatever the unknown θ\theta

Without knowing θ\theta no fixed kk is safe, since PkP_k oscillates. Randomizing kk averages the oscillation to 12−sin⁡4mθ4msin⁡2θ≥14\frac12-\frac{\sin4m\theta}{4m\sin2\theta}\ge\frac14 for large enough mm.

Question 3

With aa known, how does exact amplitude amplification reach success probability exactly 11?

  1. By running ⌈π4θ−12⌉\lceil\frac{\pi}{4\theta}-\frac12\rceil iterations with the success amplitude slightly reduced, so that the final angle is exactly π2\frac\pi2
  2. By running infinitely many iterations
  3. By measuring after every iteration
  4. It cannot: Grover's algorithm always fails with probability at least M/NM/N
Show the answer

A. By running ⌈π4θ−12⌉\lceil\frac{\pi}{4\theta}-\frac12\rceil iterations with the success amplitude slightly reduced, so that the final angle is exactly π2\frac\pi2

An ancilla rotation lowers the angle from θ\theta to θ′\theta' with (2m+1)θ′=π2(2m+1)\theta'=\frac\pi2 exactly; alternatively, tuned phases in the last iteration do the same.

Question 4

As a function of the initial success amplitude x=ax=\sqrt a, the success amplitude after kk Grover iterations is

  1. x2k+1x^{2k+1}
  2. sin⁡(kx)\sin(kx)
  3. (−1)kT2k+1(x)(-1)^kT_{2k+1}(x), a Chebyshev polynomial of degree 2k+12k+1
  4. exactly (2k+1)x(2k+1)x
Show the answer

C. (−1)kT2k+1(x)(-1)^kT_{2k+1}(x), a Chebyshev polynomial of degree 2k+12k+1

With x=sin⁡θ=cos⁡(π2−θ)x=\sin\theta=\cos(\frac\pi2-\theta), T2k+1(x)=cos⁡((2k+1)(π2−θ))=(−1)ksin⁡((2k+1)θ)T_{2k+1}(x)=\cos((2k+1)(\frac\pi2-\theta))=(-1)^k\sin((2k+1)\theta).

Further reading

  • L. K. Grover, "Quantum mechanics helps in searching for a needle in a haystack", Phys. Rev. Lett. 79, 325 (1997).
  • M. Boyer, G. Brassard, P. Høyer & A. Tapp, "Tight bounds on quantum searching", Fortschritte der Physik 46, 493–505 (1998).
  • G. Brassard, P. Høyer, M. Mosca & A. Tapp, "Quantum amplitude amplification and estimation", Contemporary Mathematics 305, 53–74 (2002).
  • T. J. Yoder, G. H. Low & I. L. Chuang, "Fixed-point quantum search with an optimal number of queries", Phys. Rev. Lett. 113, 210501 (2014).
  • A. Gilyén, Y. Su, G. H. Low & N. Wiebe, "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics", Proc. 51st ACM STOC (2019).