Lucas Brady

Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA) are both instances of the same control problem in which a combination of two Hamiltonians is applied to minimize the energy of a quantum state. Previous work has suggested that the bang-bang structure of QAOA is optimal but with significant caveats, leaving open the question of what procedure is optimal in practice. In this work, we formalize the optimal control arguments proving that a time-constrained procedure has a bang at the beginning and end but can take on an annealing-like form in-between. In numerics on transverse field Ising models, we show that bang-anneal-bang procedures are common with optimal time-constrained QAOA Trotterizing the annealing portion. We furthermore show an equivalence between different types of time-constraints in this style of problem. The optimal procedures we find are far removed from a monotonically changing adiabatic path in the short-time limit, but we show that as the allowed time increases, the adiabatic limit and intuition from adiabatic quantum computing apply.

We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate the tunneling behavior of quantum adiabatic optimization algorithms. Specifically we look at symmetric cost functions defined over n bits with a single potential barrier that a successful optimization algorithm will have to tunnel through. The height and width of this barrier depend on n, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.