Home / Quantum from Scratch / Ep 11
Quantum algorithm
What Is a Quantum Algorithm? Grover's Search Explained Simply
Go deeper
What I say in the video
A quantum computer finds one item in a million in under a thousand tries.
A normal computer: half a million tries, on average.
That's Grover's algorithm: about the square root of a million.
How?
Bits are zero or one. Qubits carry a wave for every answer. Waves add or cancel, like noise-cancelling headphones. It doesn't check them all at once.
Each round tags the right answer; interference shrinks the rest and grows it.
Look, and it's almost always the right one.
That's a quantum algorithm: a recipe using quantum mechanics that can beat normal computers on some problems.
In plain words
What is a quantum algorithm, and why doesn't a quantum computer just "try every answer at once"?
In this Short I use Grover's search algorithm to show what a quantum algorithm really does:
- Every possible answer gets an amplitude (think: a wave).
- Each round, an "oracle" tags the right answer.
- Interference shrinks the wrong answers and grows the right one.
- After about the square root of N rounds, measuring gives the right answer almost every time.
For one item in a million, that's under a thousand quantum rounds (about 785), versus about half a million tries on average for a normal computer. It's a real speedup, but only for some kinds of problems.
The noise-cancelling headphones picture is an analogy: what cancels are amplitudes, not sound.
What I simplified
Headphones are the picture, not the physics: what cancels inside a quantum computer are amplitudes — the numbers that decide how likely each answer is. "Under a thousand tries" = Grover needs about (π/4)·√N rounds, roughly 785 for a million items; a normal computer needs about half a million on average.
One new quantum idea, every week
The next episode in your inbox, with its sources. Free, and one click to unsubscribe.