A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement

Abstract

A new approach to the classical limit of Grover’s algorithm is discussed by assuming a very rapid dephasing of a system between consecutive Grover’s unitary operations, which drives pure quantum states to decohered mixed states. One can identify a specific element among [Formula: see text] unsorted elements by a probability of the order of unity after [Formula: see text] steps of classical amplification, which is realized by a combination of Grover’s unitary operation and rapid dephasing, in contrast to [Formula: see text] steps in quantum mechanical amplification. The initial two-state system with enormously unbalanced existence probabilities, which is realized by a chosen specific state and a superposition of all the rest of the states among [Formula: see text] unsorted states, is crucial in the present analysis of classical amplification. This analysis illustrates Grover’s algorithm in extremely noisy circumstances. A similar increase from [Formula: see text] to [Formula: see text] steps due to the loss of quantum coherence takes place in the analog model of Farhi and Gutmann where the entanglement does not play an obvious role. This supports a view that entanglement is crucial in quantum computation to describe quantum states by a set of qubits, but the actual speedup of the quantum computation is based on quantum coherence.