Exponential convergence dynamics in Grover's search algorithm

Abstract

Grover's search algorithm is the cornerstone of many applications of quantum computing, providing a quadratic speed-up over classical methods. One limitation of the algorithm is that it requires knowledge of the number of solutions to obtain an optimal success probability, due to the oscillatory dynamics between the initial and solutions states (the ``soufflé problem''). While various methods have been proposed to solve this problem, each has their drawbacks in terms of inefficiency or sensitivity to control errors. Here, we modify Grover's algorithm to eliminate the oscillatory dynamics, such that the search proceeds as an exponential decay into the solution states. The basic idea is to convert the solution states into a reservoir by using ancilla qubits such that the initial state is nonreflectively absorbed. Trotterizing the continuous algorithm yields a quantum circuit that gives equivalent performance, which has the same quadratic quantum speedup as the original algorithm.