The relationship between the quantum approximate optimisation algorithm and quantum annealing

已经提出了许多量子算法来解决组合优化问题。优化问题的例子包括利润最大化或时间最小化。提出的算法包括量子退火（QA）和量子近似优化算法（QAOA）。本博士的目的是研究两者之间的重叠，以了解它们的能力和局限性。在QA/QAOA中，系统处于某种初始状态。目标是将系统从初始状态进化到编码优化问题解决方案的最终状态。系统的演化是由哈密顿量（系统能量的描述）决定的。哈密顿函数由两部分组成，驱动程序和特定问题部分。接下来的问题是如何改变这两个部分以找到优化问题的解决方案。在这方面，QAOA和QA呈现了两种不同的设计理念。在QA中，哈密顿量在驱动程序和特定问题部分之间平滑地变化。QAOA受到QA的启发，但这里的算法采用近似的数字化路径。也就是说，在任何时候，哈密顿量都可以由驱动部分或特定问题部分组成，但不能两者都包含。因此，在QAOA中，哈密顿量在这两个部分之间交替。由于问题和驾驶员汉密尔顿量之间的转换次数增加，对QAOA的性能了解不多。然而，对于低数量的转换，QAOA通常优于经典算法。在我的博士学位中，我将尝试利用QA和QAOA之间的联系来检查带有大量转换的QAOA的潜在性能。这将有助于深入了解QAOA的有用性，或展示QA和QAOA之间的根本区别。

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.