A direct proof of optimality for multi-target quantum adiabatic search using subspace projector Hamiltonians

Source abstract

Abstract We present a self-contained and rigorous proof that the quadratic speedup achieved by quantum adiabatic search for multiple marked items is optimal, where N is the total number of items and M is the number of marked items. The proof uses a final Hamiltonian that projects onto the subspace orthogonal to the marked states, i.e. , , and compares two adiabatic evolutions that target two disjoint subsets of marked items. By analyzing the time derivative of the fidelity between the two instantaneous ground states, we derive a lower bound on the time-integrated energy resource: . When the interpolation function g ( s ) is bounded (the standard setting), this directly implies . The argument is elementary, avoids solving differential equations, and naturally handles the degenerate ground-state subspace. It also reveals an explicit energy-time trade-off that generalizes previous single-target results. The proof is contrasted with existing approaches and its implications for adiabatic algorithm design are discussed.