Grover's algorithm & using wave interference for computing

Question

Grover's quantum search algorithm contends that it is possible to search for a specific item in an N-sized unsorted database in only $\sqrt N$ attempts. Classically, it takes N/2 attempts on average to find this item, because the database is not presorted in any way.

It has been mentioned, however, that this speed up is in fact the result of utilizing wave interference for computing the answer, rather than from any use of quantum exclusive phenomena.

Is there a concrete example of how exactly to compute anything useful and getting the answer by utilizing interference - by reading it, measuring it, correlating it, or any other means?

The optical experiment description in Bhattacharya et al is quite technical, as a result I cannot quite grasp what it is about interference that is actually being utilized there. I suspect there is a simple "double-slit" type textbook case out there for using wave interference as a computing mechanism, but I can't think of any way to do so.

Answer 1

Quantum mechanics is just wave mechanics on phase space, so you can say that any quantum algorithm is "just" using wave interference.

What makes quantum algorithms interesting is that the phase space is huge. The wave function of a system of $n$ qubits has $2^n$ components, which would require $O(2^n)$ space to encode in a classical wave.

That's the most fundamental problem with the paper of Bhattacharya et al (DOI, PDF, arXiv). Their apparatus maxes out at $N=32$. To break 128-bit encryption would require an apparatus around $2^{123}\approx 10^{37}$ times larger. They acknowledge that problem at the end.

I see a few other problems that they don't acknowledge:

• In place of the oracle in Grover's algorithm, they use a plate that inverts the phase of the wave at the appropriate location. That means they already know the appropriate location, i.e. the answer. They don't suggest any means of implementing an oracle that uses the equivalent of quantum gates, which is the only situation in which Grover's algorithm might actually be useful. (It would be possible in principle to do it, though.)

• They claim at the end that their algorithm has the same time complexity as Grover's, but they seem to have overlooked that the time per iteration scales as $N$ (or maybe $N^{1/2}$ or $N^{1/3}$ if the apparatus could be made 2- or 3-dimensional) because of the speed-of-light limit, so the speed goes as $N^{3/2}$ (or maybe $N$ or $N^{5/6}$), worse than Grover's algorithm and not even better than brute force except maybe in the 3D case.

• The answer shows up as a spike in the wave somewhere. In Grover's algorithm, you find it by measuring the qubits. In their version, you have to search for the spike in all of the $N$ locations where it might be, which is just as hard as the problem they claim to be solving.

• Since you have to search $N$ locations anyway, you may as well just pass the wave once through the oracle and then look for the inverted pulse. The best classical algorithm therefore requires only $1$ query of the oracle, not $\sqrt{N}$.

Lloyd's paper (DOI, arXiv) is a purely theoretical discussion of an experiment similar to Bhattacharya et al's. He also acknowledges the impracticality of the idea for large $N$. He treats the oracle as a black box, avoiding my complaint about its implementation, and he minimizes the total wave energy passed through the oracle instead of the number of queries to the oracle, avoiding my complaint that you can just do one query. The paper still has the problem that the speed-of-light limit kills the speedup, and that you need to search through $N$ locations to find the answer.