The relationship between the quantum approximate optimisation algorithm and quantum annealing

点击翻译按钮获取中文摘要

A number of quantum algorithms have been proposed to tackle combinatorial optimisation problems. Examples of optimisation problems include maximising profit or minimising time. The proposed algorithms include quantum annealing (QA) and the quantum approximate optimisation algorithm (QAOA). The aim of this PhD is to examine the overlap between the two, in order to understand their capabilities and limitations.In QA/QAOA the system is prepared in some initial state. The goal is to evolve the system from this initial state to a final state that encodes the solution of the optimisation problem. The evolution of the system is dictated by a Hamiltonian (a description of the energy of the system). The Hamiltonian consists of two parts, a driver and a problem-specific part. The question is then how to vary these two parts in order to find the solution of the optimisation problem. In this respect, QAOA and QA present two different design philosophies.In QA the Hamiltonian is smoothly varied between the driver and problem-specific part. QAOA was inspired by QA, but here the algorithm takes an approximate digitised path. That is to say, at any one time, the Hamiltonian can consist of either the driver part or the problem-specific part but not both. Therefore, in QAOA the Hamiltonian alternates between the two parts. Not much is known about the performance of QAOA as the number transitions between the problem and driver Hamiltonian is increased. However, for a low number of transitions QAOA is often outperformed by classical algorithms. In my PhD I will attempt to exploit the links between QA and QAOA to examine the potential performance of QAOA with a large number of transitions. This will help to provide insight into the usefulness of QAOA or demonstrate fundamental differences between QA and QAOA.