Non-Convex Optimization by Hamiltonian Alternation

A major obstacle to non-convex optimization is the problem of getting stuck in local minima. Widely used gradient-based optimization algorithms such as stochastic gradient descent (SGD), simulated annealing, and variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) all face this difficulty. We introduce a novel approach to non-convex optimization using an engineered alternative Hamiltonian which shares a single minimum with the original Hamiltonian. For any given algorithm, alternating between the two Hamiltonians allows one to escape local minima. This technique is particularly useful when the energy of the target state is known, but one obtains an improvement even without this knowledge. We illustrate this idea by applying it to the problems of finding the ground state of the Sherrington-Kirkpatrick model of a spin glass, and the QAOA for the transverse-field Ising model.