  We present a quantum algorithm that has rigorous runtime guarantees for
several families of binary optimization problems, including Quadratic
Unconstrained Binary Optimization (QUBO), Ising spin glasses ($p$-spin model),
and $k$-local constraint satisfaction problems ($k$-CSP). We show that either
(a) the algorithm finds the optimal solution in time $O^*(2^{(0.5-c)n})$ for an
$n$-independent constant $c$, a $2^{cn}$ advantage over Grover's algorithm; or
(b) there are sufficiently many low-cost solutions such that classical random
guessing produces a $(1-\eta)$ approximation to the optimal cost value in
sub-exponential time for arbitrarily small choice of $\eta$. Additionally, we
show that for a large fraction of random instances from the $k$-spin model and
for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a)
is the case. The algorithm and its analysis is largely inspired by Hastings'
short-path algorithm [$\textit{Quantum}$ $\textbf{2}$ (2018) 78].
