The Tunnelling Salesman: Truncated Variational Approximations for Quantum Mechanical Global Optimization

In this work we present a novel method for global optimization, exploiting the mathematics of quantum mechanics, and in particular the tunnelling phenomenon. We consider a quantum mechanical system with a single particle in a potential specified by the cost function of our optimization problem. We assume the groundstate of the system is localised to the global minimum of the potential function, a condition which can be assured by choosing the particle mass sufficiently large. We then approximate this groundstate using a variational approach to optimise an expansion in terms of a truncated basis set of harmonic oscillator wave functions. We show how to encode integer factoring and travelling salesman problems in terms of finding the global minimum of a quartic polynomial cost function. We demonstrate our quantum algorithm on one- and two-dimensional toy problems, and apply it to factoring biprimes with 10 bits.