Blekos, K., Brand, D., Ceschini, A., Chou, C. H., Li, R. H., Pandya, K., & Summer, A. (2024). A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068, 1-66. https://doi.org/10.1016/j.physrep.2024.03.002
量子近似优化算法（Quantum Approximate Optimization Algorithm, QAOA）是一类变分量子算法，专门用于解决经典计算机难以有效处理的组合优化问题。QAOA 通过将一个经典的优化问题映射到量子电路上，并使用量子态的演化来找到近似解。
QAOA结合了量子计算和经典算法的优势，通过一系列可调参数的变分过程来优化问题的解。
QAOA工作原理
通过交替应用成本哈密顿量与混合哈密顿量来构造量子态演化/绝热演化。其中成本哈密顿量是用于编码目标函数的哈密顿量，例如MAXCUT的权重矩阵；混合哈密顿量对量子态进行扰动，使得某种关系更紧密。
组合优化问题有如：最大割（MAXCut）、最大独立集（MIS）、二次无约束二值优化问题（QUBO）。
性能评估：，所设计函数在问题上得到的结果与最优解的比值，最优比值为1。QUBO问题里需要找到最优向量，QUBO问题无约束，变量无约束。QUBO可以实现最小化或最大化问题，仅需翻转cost函数符号。
QAOA基本步骤：
- 初始化均匀叠加态：
- 成本层和混合层哈密顿量：
- 绝热演化：
层数越多越好，但受限于硬件噪声。
QUBO问题与MAXCUT问题
QUBO
二次无约束二值优化问题（Quadratic Unconstrained Binary Optimization, QUBO），目标是在二元/二进制变量的集合上，最大或最小化一个二次目标函数。
找到一个向量使得最大或最小化，矩阵定义为的权重矩阵。
MAXCUT
无向图，将图的顶点集合分成两部分，使得两部分的边权重和最大化，每条边有权重，MAXCUT：
其中 .
MAXCUT问题转化为QUBO
- QUBO标准形式是最小化问题，将MAXCUT最大化问题转换为最小化问题：
首先显然是权重和，即常数，不需要对其优化。目标函数可以写为：
现在得到了QUBO提到的矩阵.
- 一般QUBO问题中的变量表达为或，如果要使用Ising Model，一个简单的转换方法：
QAOA优势
- 在有限参数层的量子线路中能够得到问题的近似解，层数趋于无穷时逼近最优解，但受限于硬件噪声。但目前能够在NISQ上有效运行，当量子线路的复杂度较低时，能减少噪声的影响。
- 混合量子-经典模型充分利用量子计算的并行处理优势，以及经典算法对参数计算的准确性和稳定性。
简单的QUBO示例
假如想要找到这个公式的最小值，那么可以很容易的把真值表写成：
从这个真值表中，易见时，达到最小值 。
假设有这么一种公式：
三个未知项，解空间为。另外需要将其转写为：
对一次项做平方，然后就可以写成矩阵形式了：
得到QUBO矩阵，这里的问题即：
如果将公式这样写：
写成了类似Ising Model的形式，这意味着可以使用量子退火来处理QUBO问题。
简单的MAXCUT示例
考虑一个仅有3个node的无向图，边权重均为1。MAXCUT的目标是找到一种顶点分割，使得两个分组的边的权重最大化。
转换为QUBO形式：
成本哈密顿量：
混合哈密顿量：
量子态演化/绝热演化：
- 如只有一层 ，初始量子态 ，波函数公式：
其中参数 都是可训练的。
- 定义期望值：
- 有参数使得期望最大：
- 近似程度的比值：
QAOA算法改进文献：
QAOA参数优化文献：
QAOA变体的理论性边界：
QAOA在量子硬件平台真实实验的数据：
QUBO任务可与Ising模型一一对应[40-42]。受绝热定理的启发，退火方法被用来寻找物理系统的基态。QUBO也适用于使用量子退火进行绝热量子计算求解的问题。
QAOA主要针对QUBO问题求解，限制是变量之间二次交互。QUBO问题可扩展到高维问题。多项式无约束二元优化问题PUBO，分析如何将PUBO问题映射到QUBO问题。2.1最后部分提到了一些映射方法文献。
用于实现近似QUBO问题的算法分别有经典算法和变分量子算法VQA。其中VQA中分有变分量子特征求解器VQE，量子绝热算法QAA。
变分原理用于寻找波函数的特定可观测值（基态能量）可以得到最低的期望值。用哈密顿量和波函数表示，找到系统的基态能量：
变分算法的目的是找到参数化的，能够使哈密顿量的期望值最小化，ansatz就是用来逼近厄密算子的，参数的选择通常在量子系统上下文中在合理范围内随机选择，
Ansatz的选择本身就是一个问题，取决于系统的哈密顿量[60-62]，灵感来自待解决问题的背景。可以使用通用量子门或酉算子将哈密顿量编码。Ansatz也是一样的，能通过角度旋转参数化来构建参数化ansatz波函数。
量子比特是波函数的基本和通用表现形式，在经过一组参数化的量子门改变系统及其波函数后，测量波函数以得到该量子线路系统的期望值和能量。VQE是结合经典和量子计算资源来求解给定哈密顿算子的特征值问题的算法。最初是用来替代量子相位估计算法的[65]，后续改进[1]。参数化线路在量子计算机上进行实现，可用进行表示，其中为参数在经典计算机中以某种算法进行计算更新。
优化问题可以表达为：
其中，所以进一步有：
对于许多例子，尤其是在NISQ中，混合量子经典计算是一个强大的框架，因为量子计算机在执行参数优化等任务时，效率和容错能力都低于传统计算机。通过优势互补最大限度提升整体性能。梯度下降的优化方法[67,68]计算误差或偏离理想解的超平面。一个MaxCut问题的混合模型训练[69]从真实量子计算机的实验中证明了有效性。
BUT，混合计算并不总是最优的，如果量子硬件更强的时候[64,70]。近期VQE也被提出用于有效解决组合优化问题，类似QAOA[11,69]。
量子绝热算法QAA，绝热定理表示从一个随时间变化的哈密顿量的机台开始，如果哈密顿量演变时间足够慢，最终状态将是哈密顿量的基态。绝热定理可以推广到任何其它的本征态，只要不同的本征态之间不存在重叠（简并）。初始哈密顿量的第个特征态~最终的第个特征态，QAA[71,72]用于解决量子计算机上的优化问题，更一般的称为量子绝热计算AQC[73]。
对于参数化量子线路PQC，VQE和QAOA在训练时主要会遇到的挑战是贫瘠高原[75]，Cost函数可能会使得梯度与量子数量相比呈现指数小的情况，导致梯度消失。
对于所有的变分算法，量子线路的训练策略很重要。一些变体的Ansatz选择取决于问题类型，如图表示的组合问题[77]，其设计必须平衡专用通途和通用性，避免过拟合的同时保持泛用性。QAOA的最优分析是一个被广泛研究的课题。
量子交替算子Quantum alternating operator ansatzes[88]结构，图的约束编码到ansatz的不同方法。一般是在Cost哈密顿量中增加惩罚项，但[108]提出的混合器以不同约束条件进行修改。统一量子交替算子UQAOA[109]，近期的工作是努力将这两种不同的方法统一为一种。该框架几乎允许任何组合问题建模为QAOA问题。
1. Introduction
变分量子算法VQA通过量子-经典混合优化方法来实现对量子资源的利用。使用较浅的量子线路能够减少噪声的影响，此类算法在量子化学模拟、机器学习和优化等多个领域得到应用。
量子近似优化算法QAOA是最有前途的VQA之一，其设计目的是尝试在复杂的组合优化问题中得到近似解。QAOA将问题相关的哈密顿编码到量子线路，通过绝热时间演化和分层优化量子线路中的变分参数，就能通过测量QAOA线路的最佳参数集来构造问题的近似解。QAOA的性能通常用来衡量，表示最优解的成本，随着层数的增加，比值会愈加接近，当层数 时即绝热演化。
量子绝热定理——“绝热”：系统参量的变化足够足够慢。体系中的哈密顿量初值逐步演化到末值，若初始处于第个本征态，那么也随之演化到最后的的第本征态。知乎、Introduction to Quantum Mechanics 量子力学概论。
QAOA适用于为优化问题找到不错的近似解：
- Max E3LIN2
目前一些应用例子有：
目前针对哪些问题QAOA能够超越经典算法，以及在量子设备的噪声下是否能提供量子优势，各文献存在矛盾意见。为此，这篇综述对QAOA现状进行全面回顾和总结不同方向现有的结果。主要关注QAOA的各种扩展、变体、改进参数优化的策略、效率和算法性能分析，噪声影响问题。在MaxCut问题上评估一些QAOA变体的效率和性能。
2. Background
一般情况下，组合优化问题是在一组可行的解决方案中寻找最佳的方案，给定一些对离散变量集的约束条件。目标函数可以是最小化、最大化的，可被看作是一个，可行的解决方案所满足条件之和（或是加权的）。
一些经典的组合优化问题包括Knapsack 背包、Traveling Salesman 旅行商和 MaxCut 最大割问题，由于这类问题的组合性，解空间会随着输入数量的增加而剧烈增长，优化过程将难以进行。许多组合优化问题属于NP困难，这意味着经典算法不能有效检索出最优解，因为所需的时间与输入的数量呈指数关系。
在这种情况下，近似优化算法被用来在多项式时间内找到一个好的近似解。一个例子：给定一个组合优化问题，形式为的二进制比特字符串上，目标是最大化给定的经典目标函数，近似优化算法的目标是找到一个解决方案，使得近似率 在理想情况下尽可能接近1，其中。尽管近似算法找到的解可能不是最优解，但一般都有一个最优性保证，通常是解决方案质量的下限。例如：当且仅当一种算法能够在问题的每个实例的最优解因子内找到一个解时，该算法就被称为该问题的近似算法。如果存在这种算法，那么就证明了近似解至少值最优解的倍。然而对于某些优化问题，近似解和最优解的差距无法在多项时间内减少，这意味着最优解有关的下限是很难找到的，除非。
更正式地说，许多问题可以转化为二元无约束二值优化QUBO形式。，然而QUBO问题通常是NP-complete的，也就是说要找到一个解，通常需要遍历一个随问题规模呈指数增长的解空间。由于量子比特的叠加性质，量子计算有望实现指数级的计算速度。量子系统的指数级增长的希尔伯特空间可以自然地容纳组合优化问题的解空间。因此，在解决这类问题时可能比经典机器更有优势。
QAOA就是利用量子线路找到近似解，从而解决QUBO问题。虽然QAOA有潜力应用于各种优化问题，但其有效性取决于具体问题的特征。
2.1 QUBO 问题和应用
QAOA的目的是解决QUBO问题，其属于NP-hard类型。意思是随着问题规模的增大，目前没有一种已知算法能够高效地解决该问题的所有实例。在一系列QUBO问题中，MaxCut经常应用于QAOA中，它的概念简单，且有足够的深度和复杂度。