Entanglement of quantum variables is usually thought to be a prerequisite for obtaining quantum speedups of information processing tasks such as searching databases. This paper presents methods for quantum search that give a speedup over classical methods, but that do not require entanglement. These methods rely instead on interference to provide a speedup. 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.

• Received 12 March 1999

DOI:https://doi.org/10.1103/PhysRevA.61.010301