How Grover's Algorithm Works (And Why It Matters)

Most quantum computing breakthroughs sound impossibly abstract. Grover’s algorithm is a rare exception. It solves a problem everyone can understand — finding a needle in a haystack — and it does so in a way that reveals something genuinely strange about the universe.

Published by Lov Grover in 1996, it remains one of the most important algorithms in quantum computing. Here’s how it works, and why people keep talking about it thirty years later.

The problem: searching without a shortcut

Imagine a phone book with a million entries, but the entries aren’t in alphabetical order. They’re completely random. You’re looking for one specific name.

With a classical computer, there’s no clever trick available. You have to check entries one by one. On average, you’ll need to look through about half a million entries before you find the right one. In the worst case, you’ll check all one million.

This is called an unstructured search. There’s no pattern to exploit, no index to consult, no way to skip ahead. The only strategy is brute force, and brute force is slow.

Now here’s the question Grover asked: can a quantum computer do better?

The answer: yes, quadratically better

Grover’s algorithm finds the right entry in roughly 1,000 checks instead of 500,000.

That’s not a typo. For a search space of $N$ items, a classical computer needs on the order of $N$ operations. Grover’s algorithm needs on the order of $\sqrt{N}$ — the square root.

For a million items, $\sqrt{1{,}000{,}000} = 1{,}000$. For a billion items, it’s about 31,623 instead of a billion.

The speedup gets more dramatic as the problem gets bigger. That’s what makes it interesting.

So how does it actually work?

The magic of Grover’s algorithm comes down to a trick called amplitude amplification. It’s easier to understand if you think of it in three stages.

Stage 1: Put everything in play at once

A classical computer checks one possibility at a time. A quantum computer does something fundamentally different. Using a property called superposition, it creates a state where every possible answer exists simultaneously, each with an equal probability of being measured.

Think of it like a thousand tuning forks, all vibrating at the same volume. Each tuning fork represents one candidate answer. At this point, the quantum computer hasn’t done anything useful yet — every answer is equally likely, so measuring now would just give a random result.

Stage 2: Turn up the volume on the right answer

This is where the algorithm earns its keep. Grover’s algorithm applies two operations in a loop:

First, the oracle. This is a black box that can recognise the correct answer when it sees one. It doesn’t find the answer — it just marks it. In our tuning fork analogy, the oracle flips the phase of the correct fork. It’s now vibrating in the opposite direction, but at the same volume. You still can’t tell by listening.

Second, the diffusion operator. This is the subtle part. It takes the average amplitude of all the tuning forks and reflects everything around that average. The fork that was flipped — the one vibrating in the opposite direction — gets pushed further away from the average in the positive direction. Its volume increases. Meanwhile, all the wrong answers get pushed slightly quieter.

One round of this barely makes a difference. But repeat it about $\sqrt{N}$ times, and the correct answer’s amplitude grows until it dominates. The wrong answers fade to near-silence.

Stage 3: Measure

After enough rounds of amplification, you measure the quantum state. The correct answer now has a high probability of being the result — not certainty, but high probability. Run it a few times and you’ll get your needle.

Why $\sqrt{N}$ rounds?

There’s a natural rhythm to amplitude amplification. Each round nudges the correct answer’s probability upward by a small, consistent amount. Push too few times and the signal is too weak. Push too many times and something counterintuitive happens — the amplitude overshoots and starts swinging back down. The sweet spot is right around $\sqrt{N}$ iterations.

This isn’t a design choice; it falls out of the mathematics of how quantum states rotate in a high-dimensional space. The angle of rotation per step is fixed by the size of the search space, and $\sqrt{N}$ steps brings you to the peak.

Formally, after $k$ iterations the probability of measuring the correct state is:

$P(k) = \sin^2\!\bigl((2k+1)\,\theta\bigr)$

where $\theta$ relates to the fraction of valid solutions in the search space. This reaches its maximum near $k \approx \frac{\pi}{4}\sqrt{N}$.

What it isn’t

A few common misconceptions are worth clearing up.

It isn’t exponential speedup. Shor’s algorithm (for breaking encryption) provides an exponential speedup. Grover’s is “only” quadratic. That might sound modest, but a quadratic speedup on a truly massive search space is transformative:

$\text{Classical: } O(N) \quad \longrightarrow \quad \text{Quantum: } O(\sqrt{N})$

It doesn’t require knowing the answer in advance. The oracle doesn’t need to contain the answer. It just needs to be able to verify one. There’s a big difference between recognising a correct solution and knowing what it is beforehand. Many real problems have this property: hard to solve, easy to check.

It isn’t limited to databases. The phone book analogy is just a teaching tool. Grover’s algorithm applies to any problem that can be framed as “search through $N$ possibilities and find the one that satisfies some condition.” That includes optimisation problems, constraint satisfaction, and cryptographic puzzles.

Why it matters

Grover’s algorithm is one of a small handful of quantum algorithms with a proven advantage over any possible classical algorithm. It’s not just faster than the best known classical method — it’s been mathematically shown that no classical algorithm can do better than brute force on unstructured search, and no quantum algorithm can do better than Grover’s. It’s optimal on both sides.

That combination of generality and provable optimality is rare. It means Grover’s algorithm isn’t a trick that works on one specific problem. It’s a fundamental statement about what quantum computers can do that classical computers cannot.

Thirty years after its publication, researchers are still finding new applications for it. Wherever there’s a large search space and a way to verify answers, Grover’s algorithm offers a $\sqrt{N}$ shortcut that no classical machine can match.

Why this matters for Bitcoin mining

Bitcoin mining is, at its core, an unstructured search. Miners compute billions of SHA-256 hashes per second, looking for a single output that meets a difficulty target. There is no shortcut — the only classical strategy is brute force.

That makes it a textbook application for Grover’s algorithm. The search space is vast, the verification is trivial (check if the hash meets the target), and the difficulty keeps increasing — which means the quantum advantage compounds over time. Classical mining costs scale linearly with difficulty. Quantum costs scale as the square root.

There’s a further insight that makes this particularly interesting for near-term hardware. Mining already has an inherently low success probability. Each hash attempt is overwhelmingly likely to fail. This means a quantum miner doesn’t need error correction — the noisy, imperfect quantum hardware available today (known as NISQ devices) is sufficient for the task. You don’t need a perfect quantum computer. You need the right quantum circuit.

This is the thesis behind Mining-Capable Quantum Circuits (MCQCs) — purpose-built quantum devices designed specifically for mining, not general-purpose computation. And it’s what we’re building at Dots.

---

Dots is a quantum technology company building purpose-built quantum circuits for Bitcoin mining. Learn more about our approach or connect the dots.