Opening Grover's Algorithm
Grover's Algorithm
- Length
- 1 h 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2018
Chapter 1 of 9: Overview of Grover's algorithm
O'Donnell builds Grover search from a failed Hadamard attempt, then reflects amplitudes about their mean.
Grover's algorithm solves unstructured search, finding an input that satisfies a Boolean circuit with about queries instead of a linear scan of the truth table. O'Donnell, in CMU 15-859BB, sets this quadratic speedup against the strong exponential time hypothesis and the BBBV94 lower bound showing queries are optimal. The construction treats the circuit as a black box queried in superposition, through a sign implementation that writes function values into phases. A naive rotate-compute-rotate attempt with Hadamard transforms fails, which motivates reflecting amplitudes across their mean. About iterations drive the target amplitude near one, and a final section handles multiple or zero solutions.
Grover's algorithm solves unstructured search, finding an input that satisfies a Boolean circuit with about queries instead of a linear scan of the truth table. O'Donnell, in CMU 15-859BB, sets this quadratic speedup against the strong exponential time hypothesis and the BBBV94 lower bound showing queries are optimal. The construction treats the circuit as a black box queried in superposition, through a sign implementation that writes function values into phases. A naive rotate-compute-rotate attempt with Hadamard transforms fails, which motivates reflecting amplitudes across their mean. About iterations drive the target amplitude near one, and a final section handles multiple or zero solutions.
Grover 96
BBBV94
BBBV'94
This lecture
Lecture 20 of 27 of Quantum Computation and Quantum Information.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in