Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End

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−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. 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 are largely inspired by Hastings’ short-path algorithm.

Authors

• Alexander M. Dalzell
• Nicola Pancotti
• Earl T. Campbell
• Fernando G. S. L. Brandão

Keywords

• quantum algorithms
• quantum optimization
• super-Grover speedup