Sophisticated Quantum Search Without Entanglement
DAVID A. MEYER · Physical Review Letters · 2000
Grover's quantum search algorithm has recently been implemented without entanglement, by replacing multiple particles with a single particle having exponentially many states. We recall that all physical resources must be accounted for to quantify algorithm complexity, and that this scheme typically incurs exponential costs in some other resource(s). In particular, we demonstrate that a recent experimental realization requires exponentially increasing precision. There is, however, a quantum algorithm which searches a "sophisticated" database (not unlike a Web search engine) with a single query, but which we show does not require entanglement even for multiparticle implementations.