Comment on a classical limit of Grover's algorithm

Kazuo Fujikawa, Koichiro Umetsu

Published 2018-04-26Version 1

A classical limit of Grover's algorithm is discussed by assuming a very rapid decoherence (or dephasing) between consecutive Grover's unitary operations, which leads pure quantum states to completely decohered mixed states. One can identify a specific element among $N$ unsorted elements by a probability of the order of unity after $k\sim N/4$ steps of classical amplification defined by the decohered mixed states, in contrast to Grover's $k\sim \pi \sqrt{N}/4$ steps in quantum mechanical amplification. This difference is caused by the loss of quantum coherence with or without the loss of entanglement depending on each case.