How Quantum is the Speedup in Adiabatic Unstructured Search?*

In classical computing, analog approaches have sometimes appeared to be more powerful than they really are. This occurs when resources, particularly precision, are not appropriately taken into account. While the same should also hold for analog quantum computing, precision issues are often neglected from the analysis. I will discuss in the above context the sensitivity of the quantum adiabatic unstructured search algorithm [Roland and Cerf, Phys. Rev. A 65, 042308 (2002)] against various types of imperfections and show that the speedup associated with the algorithm is generally not robust against the presence of finite precision. In addition, I will present a classical analog algorithm for unstructured search that can be viewed as analogous to the quantum adiabatic unstructured search algorithm and which provides a quadratic speedup over standard digital unstructured search.