Quantum search without entanglement

Abstract

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.