How Much Faster Is Quantum Search, Actually?

"A quantum computer can search a database instantly" is one of those claims that survives because nobody puts a number on it. So we ran the algorithm that the claim refers to — Grover's search — and counted the one thing that matters: how many times it has to look.

Over a list of 4,096 items, it looked 50 times. A classical search of the same list looks 2,048 times on average. That is a real and useful improvement, and it is roughly forty times, not four thousand.

Counting looks instead of quoting a formula

Grover's algorithm works by repeating two steps. One asks a question of the list — "is this the item I want?" — and marks the answer. The other spreads that mark out across everything else. The first step is called the oracle, and it is the step worth counting, because it is the only one that touches the data.

We built the state vector directly and ran the loop for list sizes from 4 up to 4,096, recording the oracle count at the point where the right answer became most likely.

The improvement grows as the list grows, which is why the algorithm is worth having. But look at how it grows: quadrupling the list from 1,024 to 4,096 doubled the oracle calls from 25 to 50. Four times the data, twice the work.

Quadratic, and why that word does the real work

The relationship is that the number of calls goes as the square root of the list size. We checked it rather than asserting it: across every size from 64 upward, the number of calls squared, divided by the list size, stayed between 0.5 and 0.61. A constant ratio there is what a square-root relationship looks like when you measure it.

This is the distinction that gets flattened in headlines. There are two quite different things a quantum algorithm might do to a problem, and they are not the same word:

• A quadratic improvement turns a million steps into a thousand. Useful, and survivable if you are the one being attacked — you double the key length and you are back where you started.
• An exponential improvement turns a number that is astronomically large into one that is merely large. That is the kind that breaks things, and it is what Shor's algorithm does to factoring.

Grover is the first kind. This is why a quantum computer running Grover against a symmetric cipher is a reason to prefer 256-bit keys over 128-bit ones, and not a reason to think encryption has stopped working. The gap between a square root and an exponential is what logarithms measure, and our logarithm calculator will show you its size for any list you care about.

The part nobody mentions: running it longer makes it worse

One property was sharper than we expected. Grover's algorithm doesn't converge on the answer and stay there; it rotates toward the answer, reaches it, and keeps rotating past.

We ran every list size five oracle calls beyond its best point. In all 11 sizes tested, the chance of success fell. At a list of 32 items it fell from 0.9992 to 0.0542 — from very nearly certain to barely one chance in twenty, by doing more work.

That has a practical consequence which is easy to state and easy to get wrong: you have to know when to stop, and knowing when to stop requires knowing how big the list is. Grover is not a procedure you run until it finds something. It is a procedure you run a precomputed number of times and then measure, hoping.

Which brings us to the other thing the word "instantly" hides.

It does not return the answer. It makes the answer likely

Every row in that table has a "chance of success" column, and none of them reads 1 except by rounding. At 4,096 items the best the algorithm manages is 0.9999. That is excellent odds, and it is still odds.

A classical search has no such column. It looks at items until it finds the one it wants, and then it has found it. Grover hands you a probability distribution that is heavily weighted towards the right answer, and you take one sample from it. Usually you get the answer. Sometimes you get a wrong one, discover it is wrong by checking, and run the whole thing again.

For a search that is fine — checking a candidate is cheap. The comparison is not quite like for like, though: 50 quantum oracle calls plus a verification, against 2,048 classical looks that end in certainty.

What the speed-up is actually worth

None of this is a debunking. A forty-fold reduction in the number of times you touch the data is a serious result, and Grover's structure generalises well beyond searching a list — it is the engine underneath a family of quantum algorithms for optimisation and constraint problems.

It is also worth being precise about what "the list" means, because the word "database" in the usual telling does quiet damage. Grover does not search a stored table. The oracle is a function that recognises a correct answer, and the "list" is the space of things you could feed it. That is why the algorithm suits problems where checking an answer is easy and finding one is hard — and why it is not a faster way to query the customer records already sitting on your disk. Loading real stored data into a quantum machine is its own unsolved cost, and none of it is counted in the table above.

The honest framing is narrower than the headline and more useful. Grover turns N into roughly the square root of N, and it does so probabilistically, with a stopping point you must calculate in advance. If you are counting how many arrangements a problem has before deciding whether any of this applies, our permutation and combination calculator will size it for you, and our scientific calculator will take the square root of the answer. That second number is roughly what Grover would cost.

This guide explains a published algorithm using our own simulation. It is educational and is not security advice; decisions about key lengths should follow current guidance from a standards body.