Reflection-based adiabatic ground-state preparation

Grover’s search and adiabatic quantum computation (AQC) are two well-known quantum algorithms for achieving potential quantum speedups over classical algorithms in tackling various hard combinatorial search problems. While Grover’s search is based on the effects of constructive and destructive quantum interference of amplitudes, AQC relies on adiabatic evolution of the ground state of a system to find a solution to an optimization problem. For unstructured search problems, Grover’s algorithm possesses an optimal query complexity. However, many real-world computational problems are endowed with additional structures, and exploiting them can result in more efficient heuristics.

We present a new circuit-model quantum algorithm that is based on a combination of concepts from both Grover's search and AQC. Our algorithm deploys a sequence of reflections determined by the instantaneous eigenspaces of intermediate Hamiltonians along an adiabatic evolution in order to prepare a ground state of a target problem Hamiltonian. Using the NP-hard Max-2-SAT problem, we provide numerical evidence suggesting that, for combinatorial search problems, our algorithm can, on average, find a solution faster than Grover's search.