The Tunnelling Salesman: Truncated Variational Approximations for Quantum Mechanical Global Optimization
Oliver B. Downs, Hagai T. Attias, Chris J. C. Burges +1 more
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 wavefunctions. 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 oneand two-dimensional toy problems, and apply it to factoring biprimes with 10 bits. Introduction The state of the art in global optimization for general problems is simulated annealing and its derivatives. The algorithm can be viewed in the physical context of a classical thermal system. This inspires the novel approach presented here, in which we draw upon intuition from non-classical physical systems which obey quantum mechanics (QM), and in particular exhibit the phenomenon of quantum tunnelling. In QM, a potential function V (x) describes the energy terrain experienced by a particle, which may contain multiple minima separated by barriers. Combined with a term describing the kinetic energy of the particle, it defines the Hamiltonian operator: Ĥ = − 2 2m ∇2 + V (1) QM captures all available information on the state of the particle in a (complex) wave function ψ(x). For instance, |ψ(x)|2 is the probability distribution over the position x of the particle. To obtain ψ(x) one solves the eigenvalue problem Ĥψ = Eψ (2) known as the Schroedinger equation, where E is the energy. The solution is a set of wave functions termed eigenstates, and a matching set of energies. The eigenstate with the lowest energy is the ground state, ψ. By choosing the particle’s mass sufficiently large, the probability density associated with the ground state wave function becomes localized to the global minimum of the potential. Hence, a given optimization problem involving the minimization of a cost function can be restated as the problem of finding the ground state of the QM system with a potential specified by that cost function. In particular, computationally ‘hard’ integer problems, including factoring [1] and the travelling salesman problem, can be cast as QM problems involving a quartic polynomial potential, [3]. However, solving the Schroedinger equation exactly for these potentials is generally an analytically intractable problem. In our approach we approximate the groundstate of such a system using a method based on perturbation theory.
•Oct 1, 2002•0 citations