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.

The first and most important impact of our Centre will be through the cross-disciplinary technical training it provides for its students. Through this training, they will have not only skills to control and exploit quantum physics in new ways, but also the background in device engineering and information science to bring these ideas to implementation and to seek out new applications. Our commercial and governmental partners tell us how important these skills are in the growing number of people they are hiring in the field of quantum technologies. In the longer term we expect our graduates to be prominent in the development of new technologies and their application to communication, information processing, and measurement science in leading university and government laboratories as well as in commercial research and development. In the shorter term we expect them to be carrying out doctoral research of the highest international quality.

Second, impact will also flow from the students' approach to enterprise and technology transfer. From the outset they will be encouraged to think about the value of intellectual property, the opportunity it provides, and the fundraising needed to support research and development. As students with this mindset come to play a prominent part in university and commercial laboratories, their common background will help to break down the traditional barriers between these sectors and deliver the promise of quantum technologies for the benefit of the UK and world economies. Concrete actions to accelerate this impact will include entrepreneurship training and an annual CDT industry day.

Third, through the participation it nucleates in the training programme and in students' research, the Centre will bring together a community of partners from industry and government laboratories. In the short term this will facilitate new collaborations and networks involving the partners and the students; in the long term it will help to ensure that the supply of highly skilled people from the CDT reaches the parts of industry that need them most.

Finally, the CDT will have a strong impact on the quantum technologies training landscape in the UK. The Centre will organise training events and workshops open to all doctoral researchers to attend. We will also collaborate with CDTs in the quantum technologies and related research areas to coordinate our efforts and maximise our joint impact. Working in consort, these CDTs will form a vibrant national training network benefitting the entire UK doctoral research community.