Near-optimal quantum circuit for Grover's unstructured search using a transverse field
Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang · Physical Review A · 2017
Inspired by a class of algorithms proposed by Farhi et al. (arXiv:1411.4028), namely, the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduce a technique, based on spin-coherent states, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order $\mathrm{\ensuremath{\Theta}}(1/\sqrt{N})$, and the overlaps are of order $\mathrm{\ensuremath{\Theta}}(1)$, yielding a nearly optimal query complexity of $T\ensuremath{\simeq}\sqrt{N}\phantom{\rule{0.4pt}{0ex}}(\ensuremath{\pi}/2\sqrt{2})$. Our algorithm is a QAOA circuit that demonstrates a quantum advantage with a large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.