Opening Grover's Algorithm
Grover's Algorithm
- Length
- 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Circuit satisfiability problem
Grover's algorithm finds the satisfying input of an -variable Boolean circuit in roughly steps, against for brute force. O'Donnell starts from Circuit SAT, assuming a single satisfying string to keep the analysis clean. Hadamard gates prepare an equal superposition over all inputs, and the classical circuit becomes a quantum oracle that negates the target amplitude. The Grover move pairs that oracle with a diffusion step reflecting every amplitude across their average. After about repetitions, measurement returns the target with constant probability; the graduate session assumes quantum states, matrices and Boolean Fourier analysis.
Your comment is kept while you sign up.Sign in
Builds Grover search for Circuit SAT from Hadamard gates, a sign-flipping oracle and reflection about the average.
Grover's algorithm finds the satisfying input of an -variable Boolean circuit in roughly steps, against for brute force. O'Donnell starts from Circuit SAT, assuming a single satisfying string to keep the analysis clean. Hadamard gates prepare an equal superposition over all inputs, and the classical circuit becomes a quantum oracle that negates the target amplitude. The Grover move pairs that oracle with a diffusion step reflecting every amplitude across their average. After about repetitions, measurement returns the target with constant probability; the graduate session assumes quantum states, matrices and Boolean Fourier analysis.
This lecture
Lecture 26 of 89 of A Theorist's Toolkit.
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.