Imagine a very well-shuffled deck of 52 cards.

Someone asks you:

“Can you find the 2 of diamonds?”

There’s no trick. You pick up a card, look at it, and if it isn’t the 2 of diamonds, you move to the next one. If you’re lucky, it’s the first card. If you’re extremely unlucky, it’s the last.

On average, you’ll have to check about half the deck.

Now imagine the deck has a million cards. You’re still doing the same thing: checking cards one by one. So here’s the question:

Can we do better?

For a classical computer, if there’s genuinely no information about where the answer is, not really.

But a quantum computer can do something remarkable: it can search through possibilities in roughly the square root of the usual number of steps. So, instead of checking 1 million cards, it could find the right one in just about 1,000 steps!

And that idea is known as Grover’s algorithm. It was invented by Lov Grover, an Indian-American computer scientist and one of the pioneers of quantum computing. Here is the original paper by him:

Here is a simpler version! Let us dive in!

A quantum computer can represent all possible outcomes in a single quantum state.

Imagine we have three possible answers: A, B, and C.

A quantum computer can prepare all three in a single quantum state, with a coefficient (also called an amplitude) attached to each one:

0.5 A + 0.5 B + 0.707 C

These coefficients tell us the amplitude associated with each possible answer. When we measure the quantum state, we don't get all three answers. We get one of them.

And here’s the important part: the probability of seeing an answer depends on the square of its amplitude.

So in this example:

So superposition lets us store many possibilities in one quantum state—but measurement gives us only one of them depending on the amplitudes.

Now we can return to our search problem.

Suppose we have a billion possible answers.

In principle, we can prepare a quantum state using a quantum computer and put all of them into an equal superposition, so that every possible answer starts with the same amplitude, like:

0.577A + 0.577B + 0.577C

This is the first step. Our answer is one term in this huge superposition state. If you think of cards, each term would represent one card.

But a simple measurement now will randomly give us one output, and that may not be the correct answer.

The goal of a quantum algorithm is therefore to carefully twist and turn the amplitudes before we measure, such that the amplitude of that term is very, very high and the others are super low.

Let's say B is the correct answer. The algorithm applies a sequence of operations designed to increase B's amplitude while reducing the amplitudes of the wrong answers.

For our tiny example, imagine that we start with:

0.577A + 0.577B + 0.577C

After the quantum algorithm has done its work, we might end up with something like:

0.01A + 0.999B + 0.04C

Now the situation is very different. When we measure, the probability of each answer is the square of its amplitude:

So we now have about a 99.8% chance of measuring B.

That's the basic idea behind the quantum speedup:

This is the part that confused me when I first learned about Grover's algorithm.

If the computer doesn't know which one is the correct answer, then:

How can it increase the amplitude of the correct answer while decreasing the amplitudes of all the wrong ones?

I cannot answer this here but I let you think for yourself! Here is a hint for the advanced learners:

This is where the famous speedup comes from. If you have N possibilities, a classical search takes roughly N checks in the worst case.

Grover's algorithm needs roughly the square root of N iterations to increase the amplitude of the answer term and decrease the rest.

A billion possibilities? Classical search may need around half a billion attempts, while Grover’s algorithm needs roughly thirty thousand! That’s the dramatic speed up!

This is where we need to be a little careful.

Grover's algorithm isn't a magical “make any program faster” button. It is useful for a particular kind of problem:

You have a large number of possible answers, and you have a way to check whether an answer is correct.

That's it. Think about a giant puzzle. There might be billions or trillions of possible configurations. Most are wrong. But you have a test that can quickly tell you:

“Yes, this is a valid solution.”

Classically, you might have to search through the possibilities one by one.

Grover gives you a way to search that space quadratically faster.

This idea can be relevant to things like combinatorial search, constraint problems, optimization, and cryptography.

Sudoku gives us a nice intuition here: if we can create a quantum state representing all possible solutions, we can use Grover’s algorithm to search through this sea of possibilities and amplify the correct one. Here is GitHub repo if you want to play:

The important idea is the finite search space + efficient way of checking a candidate is correct answer or a wrong one.

Quantum computers today are incredibly difficult machines to build. Qubits are fragile. They are affected by noise. Quantum operations aren't perfect.

And keeping a large quantum computation running without errors requires sophisticated error correction.

Grover's algorithm doesn't need just one quantum operation.

For a huge search space, it needs many rounds of:

mark → amplify → mark → amplify → mark → amplify

And every one of those operations has to be performed reliably.

This creates a strange situation.

On paper, going from N operations to √N operations sounds incredible.

This is a question researchers have started looking at seriously.

In 2021, researchers including Google scientists published a paper:

Their argument was essentially this:

A quadratic speedup is great mathematically.

But once you account for the enormous overhead of building fault-tolerant quantum computers, it may not be enough to produce a practical advantage for some applications.

They looked at problems with even larger theoretical speedups and argued that those could be much more attractive targets for early fault-tolerant quantum computers.

In other words:

√N is impressive.

But maybe N to the power of 3 or 4 is where quantum computing becomes truly transformative.

This is where things get interesting.

From a theoretical computer science perspective, Grover's algorithm is unquestionably important. It proves that quantum mechanics can provide a genuine advantage for unstructured search.

But whether that advantage becomes practically useful is a different question.

And that's an important distinction.

There is a huge difference between:

and

We don't yet know how that story will end.

For me, the most fascinating thing about Grover's algorithm isn't even the square-root speedup.

It's the mechanism behind it. The computer doesn't know the answer. It doesn't magically look at every possibility and pick the right one.

Instead, we give it a way to recognize a correct answer.

The quantum computer then uses interference to amplify that answer. That's a very different way of thinking about computation.

Instead of asking:

“How do I check every possibility faster?”

we ask:

“How can I use interference to suppress the wrong possibilities and amplify the right one?”

That's the quantum trick.

We know Grover's algorithm works. We know that, in the appropriate search model, the square-root improvement is essentially the best possible quantum speedup for unstructured search.

The unanswered question is much more practical:

Can we build quantum computers powerful and reliable enough for this advantage to matter?

Maybe we can.

Maybe the overhead of quantum error correction will make Grover's speedup less exciting than it looks on paper.

Or maybe future quantum computers will become powerful enough that even a square-root improvement is enormously valuable.

For now, Grover's algorithm sits in an interesting place.

It is a beautiful example of something quantum computers can do that classical computers fundamentally cannot match in the same way.

But whether it becomes a practical tool, or remains one of the most elegant ideas in quantum computing, is still up to the future.

For any comments, questions or collaborations, please contact at: [email protected]