Using reinforcement learning for finding the optimal quantum annealing schedule

Abstract

For NP-hard optimisation problems no polynomial-time algorithms exist for finding a solution. Therefore, heuristic methods are often used, especially when approximate solutions can be satisfactory. One such method is quantum annealing, a method where some initial Hamiltonian is slowly perturbed to anneal towards a problem Hamiltonian. The annealing schedule should follow the adiabatic theorem of quantum mechanics and should therefore be slow to yield the most accurate results. Finding a schedule that is both fast and still accurate has been referred to as a 'black art' and is usually just guessed. In this thesis reinforcement learning (RL) is explored to see if it can help with finding the optimal quantum annealing (QA) schedules. The Hamiltonians used are of
the form of a transverse field Ising model. These are well studied Hamiltonians that can map to many NP-complete problems [1]. Finding a good balance between going both fast and being precise proved to be difficult and needs further research. Therefore this thesis mainly dealt with training an RL agent to find the most accurate QA schedule. The results show that the agent learns to find the most accurate (slowest) annealing schedule after 300,000 learning steps for a problem Hamiltonian with a single coupling constant J and no reward shaping. Annealing in an environment with a spin glass problem Hamiltonian proved to be difficult and has not shown good results in this thesis This needs further investigation. Nonetheless, the result on the single coupling constant Hamiltonian shows the potential of an RL agent for learning in a quantum annealing environment with very sparse rewards. This paves the way for further research into an RL agent that can find a schedule that is both fast and accurate on a wide range of problem Hamiltonians.