Grover's Algorithm may be a Dud

Grover's algorithm is supposed to be one of the great theoretical accomplishments of quantum computers, along with Shor's algorithm.

Now a new paper argues Grover's Algorithm Offers No Quantum Advantage

Scott Aaronson is not impressed:

I haven’t yet read that paper carefully, but have discussed it with some students and colleagues. My current impression is that it’s a mishmash of

(1) well-known observations about the difficulty of seeing a Grover speedup in practice given the overhead of quantum fault-tolerance, and

(2) a completely absurd argument about the Grover problem being “classically solvable with 1 query,” which would of course violate a known lower bound (what they mean is, in a model where you effectively get explicit access to the oracle function … in which case, we’re no longer talking about query complexity at all, and 0 queries suffice! 🙂 )

I don't know. This paper seems devastating to me, if it is right.

Grover's Algorithm is supposed to let you search N items with only &sqrt;N steps, using a quantum computer.

It is usually described as searching a database. But a relational database usually has an index that allows searching in log(N) steps, much faster than the quantum computer.

Quantum computers are supposed to do it without an index. It seems like magic. Useless magic.

Update: Scott Aaronson refutes the new paper here and here. He agrees with this:

Since the current practical infeasibility is well-known, I assumed the paper was observing something fundamental. It was not.

Okay, not news. Everybody already knew Grover's algorithm was a dud.