Grover’s algorithm is an approximation of imaginary-time evolution
ABSTRACT
We make a simple but powerful observation: Grover's algorithm can be regarded as a product formula approximation of effective imaginary-time evolution (ITE) with respect to a projector Hamiltonian. We show that this ITE follows the geodesic path between the initial state and the solution state in Grover's search, and that it is equivalent to Riemannian gradient ascent maximising fidelity to the solution state. We thus interpret Grover's algorithm as an approximation of both geodesic evolution and Riemannian optimisation. From this geometric insight, we explain different choices of Grover angles (π and π/3 algorithms) and propose new ones (π/2, QSP-based) with more favourable properties for certain initial states. Conversely, we exploit this connection to prove a lower bound on the complexity of implementing ITE via real-time evolution for projector Hamiltonians. Our analysis reveals that the exponential complexity growth of existing ITE algorithms is unavoidable in the worst case.
