Generalized quantum optimization algorithms for near-term quantum computing architectures

在遥远的未来，大规模、理想的量子计算机将通过利用有限数量的基本量子算法来加速许多有趣的计算任务。然而，现在存在的或几年后我们可能看到的第一代量子计算机将容易出错，因此只能运行一组有限的量子程序。在这种情况下，迫切需要为这些机器找到有价值的应用。获得难优化问题的良好解就是这样一个应用。量子近似优化算法（QAOA）是目前最成熟的量子优化算法。然而，时至今日，QAOA相对于经典算法的优势仍然难以捉摸。更具体地说，最近的一系列结果对最朴素的QAOA版本建立了重大限制——尽管这些结果与近期量子计算机可解决的中等规模问题的相关性可能会受到质疑。从目前对QAOA局限性的理解出发，该项目将致力于设计该算法的通用版本并评估其性能。然后将探索这些构建块作为普通量子算法的浅层近似的潜在应用。随后将考虑这些近似算法的几种应用，可能包括增强经典优化启发式或变分量子特征解算器家族|的算法，这些算法是量子化学或量子计算机上的材料科学模拟的核心。

In a distant future, large-scale, ideal quantum computers will speed up many interesting computational tasks by leveraging a restricted number of fundamental quantum algorithms. However, the rst generation of quantum computers |those that exist now or that we may see in a few years| will be error-prone, hence merely capable of running a restricted set of quantum programmes. In this context, it is pressing to find valuable applications for these machines. Obtaining good solutions to hard optimization problems could be such an application.The Quantum Approximate Optimization Algorithm (QAOA) is the best-established quantum optimization algorithm for near-term hardware to date. However, as of today, the advantage of QAOA over classical algorithms has remained elusive. More specifically, a series of recent results established significant limitations on the most naive versions of QAOA - though the relevance of these results to the intermediate-scale problems addressable by near-term quantum computers may be questioned.Starting from the present understanding of the limitations of QAOA, the project will aim at designing generalized versions of the algorithm and assess their performance. Potential applications of these building blocks as shallow approximations of common quantum algorithms will then be explored. Several applications of these approximate algorithms will subsequently be considered, possibly including the enhancement of classical optimization heuristics or algorithms from the variational quantum eigensolver family |which are central to quantum chemistry or material science simulations on a quantum computer.