The relationship between the quantum approximate optimisation algorithm and quantum annealing

量子近似优化算法与量子退火的关系

• 批准号: 2420903
• 金额: --
• 依托单位: University College London
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2420903
• 关键词: relationship; between; quantum; approximate; optimisation

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.

已经提出了许多量子算法来解决组合优化问题。优化问题的示例包括最大化利润或最小化时间。所提出的算法包括量子退火（QA）和量子近似优化算法（QAOA）。该博士的目的是检查两者之间的重叠，以了解它们的能力和局限性。在QA/QAOA中，系统是在某种初始状态中制备的。目标是将系统从此初始状态发展到编码优化问题解决方案的最终状态。系统的演变由哈密顿量（对系统能量的描述）决定。哈密​​顿人由两个部分，一个驾驶员和一个特定问题的部分组成。然后，问题是如何改变这两个部分以找到优化问题的解决方案。在这方面，QAOA和QA提出了两种不同的设计理念。在质量检查中，哈密顿量在驾驶员和特定于问题的部分之间平稳变化。 QAOA的灵感来自质量检查，但在这里，算法采用了近似数字化的路径。也就是说，在任何时候，哈密顿人都可以由驾驶员零件或特定于问题的部分组成，但不能同时组成。因此，在QAOA中，汉密尔顿两部分之间的交替。对于QAOA的表现尚不了解，因为问题与驾驶员Hamiltonian之间的数量过渡增加了。但是，对于较少的过渡，QAOA通常比经典算法表现出色。在我的博士学位上，我将尝试利用质量检查和QAOA之间的联系，以检查QAOA的潜在性能，并进行大量过渡。这将有助于洞悉QAOA的实用性或证明质量检查和QAOA之间的基本差异。