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 , and you have rotated by . 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 , and exact amplitude amplification for known .
- Prove the averaging lemma behind exponential search for an unknown number of marked items.
- Identify Grover's success amplitude as and connect it to QSVT.
Two reflections make a rotation
For a unit vector let : it fixes and negates its orthogonal complement. In a real plane, the reflection about the line at angle is
Multiply the matrices.
Angle-addition formulas; e.g. the top-left entry is .
A rotation by twice the angle from the first mirror to the second.
In Grover's algorithm the invariant plane is spanned by (angle ) and (angle ). The oracle acts there as and the diffusion as , a mirror at angle with . So . Off the plane the operators act differently, but the plane is invariant and contains , so nothing else matters.
Two mirror lines through the origin meet at angle . Reflecting in one and then in the other is
- a reflection about their bisector
- a rotation by
- a rotation by
- the identity
Show the answer
C. a rotation by
. 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 the ideal real-valued count is . Write with and . Then , so
the last step because .
, one marked item. What is ?
Show the answer
804 iterations
, so and . The failure probability is below .
Fixed points. Plain Grover is fragile when is uncertain: overshooting rotates you away. Grover's 2005 "" 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 for every , using the optimal queries.
Unknown M: exponential search
Use .
A product-to-sum identity that makes the sum telescope.
Sum the telescoping series and divide by .
Set . The last step uses .
Exponential search. Start with and repeat: draw , run iterations, measure, verify with one query; on failure set with . Until reaches the cost is a geometric series. After that each round succeeds with probability at least , and keeps the expected remaining cost, a series in , convergent. The total expected number of queries is , and if no item is marked the search can be stopped after queries.
Grover as a polynomial
Write for the initial success amplitude. Chebyshev polynomials satisfy , and , so
After iterations the success amplitude is : an odd polynomial of degree in the initial amplitude.
Key takeaways
- Two reflections whose axes meet at angle make a rotation by ; the Grover iterate has eigenphases on the invariant plane.
- gives success at least ; with known, shrinking the angle (or tuning phases) makes it exactly .
- Averaging over a random gives success at least once : the basis of search for unknown .
- The success amplitude is : 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.
What are the eigenvalues of the Grover iterate restricted to , where ?
Show the answer
B.
is a rotation by of a real plane, whose eigenvalues are with eigenvectors .
In exponential search, why is the number of iterations chosen at random from ?
- To hide the marked item from an adversary
- Because random circuits are easier to compile
- To make the algorithm exact
- Because the average of over such is at least once , whatever the unknown
Show the answer
D. Because the average of over such is at least once , whatever the unknown
Without knowing no fixed is safe, since oscillates. Randomizing averages the oscillation to for large enough .
With known, how does exact amplitude amplification reach success probability exactly ?
- By running iterations with the success amplitude slightly reduced, so that the final angle is exactly
- By running infinitely many iterations
- By measuring after every iteration
- It cannot: Grover's algorithm always fails with probability at least
Show the answer
A. By running iterations with the success amplitude slightly reduced, so that the final angle is exactly
An ancilla rotation lowers the angle from to with exactly; alternatively, tuned phases in the last iteration do the same.
As a function of the initial success amplitude , the success amplitude after Grover iterations is
- , a Chebyshev polynomial of degree
- exactly
Show the answer
C. , a Chebyshev polynomial of degree
With , .
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).