Master's Defense: Andoni Agirre

Learning Quantum Optimization Games - Monte Carlo Tree Search as an alternative for quantum optimization

Hard combinatorial optimization problems have an abundance of real-life applications, but quickly become intractable and too costly to solve. By encoding them into ground states of spin-1/2 Hamiltonians, such problems can be formulated as ground state preparation problems, which can be tackled by quantum algorithms. A lot of effort is currently being made to determine if the limited quantum devices of today could provide better and faster platforms to solve these hard problems.

In this thesis we work with 3-satisfiability, the prime example of such hard problems, and try to solve it with algorithms based on two of the main near-term quantum computational paradigms for quantum optimization: Adiabatic Quantum Computation and Variational Quantum Algorithms. In view of the difficulties of quantum optimization, such as having to navigate exceedingly complicated cost landscapes, we employ the Monte Carlo Tree Search algorithm, a very peculiar way of approaching quantum optimization from the viewpoint of board game artificial intelligence.

We first implement and study the performance of our own version of the Monte Carlo Tree Search algorithm, both within a conventional game domain and a simple quantum system with two spins. We then successfully use our algorithm as a tool to optimize annealing schedules to solve hard instances of 3-satisfiability, as well as presenting and testing different methods of optimizing the parameters of the Quantum Approximate Optimization Algorithm with it. We also devise a number of concrete modifications to the standard version of the algorithm, which make it an even more compelling tool for quantum optimization.