%0 Journal Article
%T Quantum search without entanglement
%A Seth Lloyd
%J Physics
%D 1999
%I arXiv
%R 10.1103/PhysRevA.61.010301
%X Entanglement of quantum variables is usually thought to be a prerequisite for obtaining quantum speed-ups of information processing tasks such as searching databases. This paper presents methods for quantum search that give a speed-up over classical methods, but that do not require entanglement. These methods rely instead on interference to provide a speed-up. Search without entanglement comes at a cost: although they outperform analogous classical devices, the quantum devices that perform the search are not universal quantum computers and require exponentially greater overhead than a quantum computer that operates using entanglement. Quantum search without entanglement is compared to classical search using waves.
%U http://arxiv.org/abs/quant-ph/9903057v1