Sophisticated quantum search without entanglement
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.
Meyer
DA
Project in Geometry and Physics, Department of Mathematics, University of California at San Diego, La Jolla, California 92093-0112 and Institute for Physical Sciences, Los Alamos, New Mexico.