使用多参数问题独立层增强 QAOA Ansatz-煤油灯科技

使用多参数问题独立层增强 QAOA Ansatz

煤油灯科技2022-10-04 08:48

摘要

量子近似优化算法(QAOA)有望解决组合优化领域的经典棘手计算问题。然而，越来越多的证据表明，最初提出的QAOA ansatz的形式并不是最佳的。为了解决这一问题，我们提出了一种替代ansatz，我们称之为QAOA+，它在传统的 $p = 1$ QAOA ansatz的基础上增加了一个多参数问题独立层。QAOA+ ansatz允许获得比 $p = 1$ QAOA更高的近似比，同时保持电路深度低于 $p = 2$ QAOA，作为随机规则图的MaxCut问题的基准。此外，我们还表明，与标准QAOA相比，所提出的QAOA+ ansatz虽然使用了更多可训练的经典参数，但在大多数情况下优于替代多角度QAOA ansatz。

1.引言

随着含噪声的中型量子 (NISQ) 计算时代的成熟，越来越多强大的量子计算机出现，在解决一些重要的现实世界问题方面，正朝着超越经典计算机的计算能力稳步前进。仅在生物化学领域，量子退火器已被用于解决蛋白质折叠问题，基于门的量子计算机已被用于计算分子的基态能量。尽管量子硬件不断进步，但是，由于复合噪声的存在，现代量子计算机能够相当好地执行的量子电路在最大量子位数、量子位连通性和最大电路深度方面仍然受到严重限制，使得算法性能大大低于理论预测的最佳情况。

混合量子经典算法通过量子和经典计算资源的组合来解决问题，是在近期设备中实现量子优势的主要候选方法。量子经典混合算法的范围从量子机器学习技术到参数化量子电路，参数化量子电路是通过迭代经典优化例程获得的具有门参数的量子电路。参数化量子电路包括量子变分本征解器、量子自编码器和量子近似优化算法(QAOA)。

QAOA在NISQ设备中显示量子优势的潜力及其大量实际应用引起了人们的兴趣。QAOA解决了寻找哈密顿量的最低能量本征态对应的位串的组合优化问题。通过利用图结构的对称性，通过引入经典神经网络或其他经典方法来辅助参数优化，通过修改电路方法，通过增加电路参数化，以增加经典优化为代价，QAOA的性能得到了提高。虽然增加QAOA电路中独立参数的数量在某些情况下可以提高性能，但随着参数数量的增加，非凸优化环境可能阻碍参数优化。

在这项工作中，我们介绍了使用与问题无关的层来增强 MaxCut 问题的标准 QAOA方法的技术，以提高 $p = 1$ QAOA 的性能，同时保持电路深度低于 $p = 2$ QAOA。添加的层由一系列双量子位门组成，这些门以尽可能少的操作数纠缠所有量子位，然后是第二个单量子位门混合层。我们在 MaxCut 问题上测试了我们称为 QAOA+ 的ansatz的性能，用于具有多达 14 个节点的随机正则图，我们表明它以增加经典优化参数的数量为代价产生了近似比改进。我们还将 QAOA+ 与另一个 QAOA 变体，多角度 QAOA (ma-QAOA)进行了比较，并表明对于多达14个节点的随机正则图，对于独立参数数量较少的问题，QAOA+通常比ma-QAOA在MaxCut问题上获得更高的近似比。

2.背景

在本节中，我们将介绍在这项工作中使用的符号，并简要回顾使用QAOA解决MaxCut问题的相关结果和方法。

2.1QAOA

QAOA是一种受绝热进化原理启发的变分算法。在其最初的公式中，它可以被视为具有有限步数 $p$ 的量子退火演化的 Trotterized 版本。QAOA可以用来解决广泛的一般无约束组合问题，寻求用字符串表示的解，使代价函数最大化。这是通过使用交替算符序列制备一个参数相关的n-qubit 量子态来实现的：

其中 $U_{C} (γ) = e^{- iγ C}$ 是相位算子， $C$ 是问题哈密顿算子， $U_{B} (β) = e^{- i βB}$ 是混合算子， $B = Σ_{j} X_{j}$ ， $∣ s ⟩ =∣ + ⟩^{\otimes n}$ 是初始均匀叠加积态， $B$ 的最大能量激发态。演进之后是计算基础中的测量，测量结果概率遵循 Born 规则：

经典参数 $β, γ$ 在外循环中更新，以最大化量子进化测量结果的预期目标值：

QAOA的性能取决于这些参数的选择。识别最优QAOA参数的问题已经产生了大量的理论和计算工作，包括强化学习和重用相关问题实例中预优化的QAOA参数等方法，以显著降低参数优化的计算成本。

2.2MaxCut

MaxCut是一个典型的NP完全组合问题。考虑一个具有一组顶点 $V$ 和一组边 $E$ 的无向图 $G$ 。MaxCut的目标是找到一个顶点分配到两个不相交的子集，以使跨越两个子集的边数最大化。MaxCut的目标是使以下目标函数最大化：

QAOA的性能是用称为近似比(AR)的指标来评估的。它被定义为代价哈密顿量的期望值除以最大哈密顿能量。

基于梯度的方法常用于QAOA参数优化。不幸的是，优化参数的数量随着QAOA层数的线性增长，以及被称为“贫瘠高原”的梯度指数消失现象，使得该优化任务本身通常是一个NP-hard非凸优化问题。由于有限的相干时间和相对较大的双量子比特误差率，QAOA层数的增加也会导致量子电路大大超过NISQ硬件的能力。与此同时，浅QAOA电路不具备实现高近似比的能力。因此，调整QAOA方法以在现代量子处理器上最有效地使用是非常重要的。

2.3替代 QAOA ansatz

最初提出的QAOA ansatz的形式还没有被证明对任何特定的优化问题是最优的。事实上，越来越多的研究表明，替代QAOA ansatz优于标准QAOA ansatz，要么要求较浅的量子电路来匹配标准QAOA的性能，要么为相同的电路深度提供更好的结果，或者两者兼有。在前一种情况下，可以通过开发定制的特定于问题和硬件的ansatz来实现这些改进，例如ADAPT-QAOA。该方法使用基于梯度的准则从预定义的操作符池构建自定义QAOA混合层，一次系统地增长 ansatz 层。这被证明可以提高电路深度p>4 的 MaxCut 近似比，同时还导致变分参数数量减少和 CNOT 门数减少。

另一个替代的QAOA ansatz多角度QAOA(ma-QAOA)改进了MaxCut问题的近似比，但代价是增加了变分参数的数量，而不改变标准QAOA ansatz的形状。然而，这显著增加了经典优化过程的计算成本。多角度QAOA独立地对标准QAOA电路的相分离层和混合层中的每个门进行参数化。它的好处是需要较低的电路深度来产生近似比，类似于或高于标准QAOA ansatz所达到的近似比。因此，ma-QAOA比现代量子硬件上的标准QAOA提供了更高的性能，在现代量子硬件上，增加电路深度超过某一点会导致算法性能由于退相干而急剧下降。

3.QAOA+

我们提出了另一种 QAOA ansatz，称为 QAOA+，它由标准 $p = 1$ QAOA 层和一个附加的与问题无关的电路 ansatz 组成（见图 1）。附加层具有 MaxCut 的标准 QAOA 层的形式n 节点折线图；换句话说，相分离层从第一个到最后一个依次连接所有量子比特。这个与问题无关的层使用连接所有量子位的最小可能数量 $n - 1$ 的两个量子比特门。此外，与 ma-QAOA 类似，我们允许附加层中的所有变分参数是独立的。请注意，对于同一图，QAOA+ ansatz 中的经典参数数量几乎总是小于 ma-QAOA 中的。

对于密集图，其中边的数量接近与节点数量的二次缩放，与附加的 QAOA+ 线性 ansatz 层相关的附加电路深度明显小于一个附加 QAOA 层 $p = 2$ QAOA 的附加电路深度。因此，QAOA+ 在提高 MaxCut 近似比（如下所示）和增加总电路深度之间提供了有利的折衷方案。这对于稀疏图仍然适用，尽管影响较小。只有对于线性图上的 MaxCut，当标准 QAOA ansatz 的形状与 QAOA+ 中附加层的形状匹配时，QAOA+ 相对于 QAOA 的电路深度优势才会消失。相反，对于线性图，QAOA+ ansatz 具有与标准 $p = 2$ QAOA 相同的形状，减去变分参数的数量。

图1:QAOA+的电路布局，包括一个标准的 $p = 1$ QAOA层，接着是一个附加的由ZZ门组成的独立问题层，以及一个附加的X门混合层。附加层中的所有单量子比特门和双量子比特门都是独立参数化的。

表I比较了在 $p = 1$ QAOA、QAOA+和 $p = 2$ QAOA的非同构3、4 和 5 正则 8、10、12 和 14 节点图上 MaxCut 的平均近似比。结果在每一种类型的10个非同构随机图上取平均值。我们使用Broyden-Fletcher-Goldfarb-Shanno (BFGS)算法对QAOA参数进行优化，从每个图的初始参数随机的10次优化运行中选择最优解。利用张量网络量子模拟器QTensor计算QAOA的能量期望值。标准 $p = 1 和 p = 2$ QAOA的近似值从QAOAKit数据库中得到。在所有考虑的图类型中，QAOA+ ansatz产生p=1和p=2 QAOA之间的近似比率值，同时也使用中间数量的两个量子位门;图2是优化参数的数量、两个量子位门和8节点图的近似比的更详细的比较。由于双量子比特门是量子电路中误差的主要来源，当在NISQ器件上执行时，QAOA+ ansatz有可能比标准 $p = 2$ QAOA产生更好的结果，因为双量子比特门的数量更少。

表I：对于n = 8、n = 10、n = 12和n = 14个节点，对于p = 1 QAOA、QAOA+和p = 2 QAOA，所有3-、4-和5-正则图的近似比。

图 2：针对四种不同 QAOA 变体绘制的所有 3-reg、4-reg 或 5-reg 8-qubit 图的参数数量、双量子比特门数和平均逼近比：QAOA(p = 1 )、QAOA+ (p = 1)、多角度 QAOA (p = 1) 和 QAOA (p = 2)。

引入的QAOA+ ansatz不仅在 $p = 1 和 p = 2$ QAOA的MaxCut解质量和相关的QAOA电路深度方面提供了一个很好的折衷方案，它还在经典优化QAOA参数的复杂性方面提供了额外的灵活性。QAOA+中的附加门层可以设计为具有 $2 到 2 n + 1$ 个参数之间的任意位置(标准p=1 QAOA中的2个参数，两个量子比特门的问题无关层中的 $n - 1$ ，附加混合层中的n )，其中n 为量子比特的数量。然而，标准QAOA ansatz也可以修改为每个QAOA层有2个以上的参数。在该工作中，作者介绍了ma-QAOA ansatz，它允许标准QAOA层中的所有参数都是不同的。因为原始的ma-QAOA ansatz不少于2n−1 个参数，但是，为了比较QAOA+和ma-QAOA的性能，我们修改了两个ansatz，使其具有可调节的参数数量，对于QAOA+，从4 到 $2 n + 1$ ，而在ma-QAOA中，从2到与问题相关的最大参数数量。此外，由于参数的数量可以不均匀地分布在双量子位和混合层之间，对于QAOA+和ma-QAOA，我们已经平均了QAOA实例的近似比与优化参数之间的所有可能分布。对于每个实例，我们使用BFGS算法进行了10次重启，优化了所有5个可能的非同构8节点3正则图。结果如图3所示。

图 3：所有 8-qubit 3-reg 图的 ma-QAOA、标准 QAOA（ $p = 1 和 p = 2$ ）和 QAOA+ 的近似比比较。对于 ma-QAOA 和 QAOA+，通过改变独立参数的数量来比较相同参数数量下的算法性能。

独立优化参数的数量决定了QAOA经典优化的复杂度。我们已经观察到，在相同的参数数下，QAOA+总是比ma-QAOA给出更高的近似比，尽管在完整的20个参数情况下，ma-QAOA优于最大参数化的17个参数QAOA+。QAOA+和ma-QAOA之间的性能差距随着优化参数数量的减少而增大。事实上，4参数QAOA+的平均性能优于14参数的ma-QAOA，但在更大的电路深度下仍不如 $p = 2$ QAOA；参见图3。

我们没有观察到具有相同数量参数的ma-QAOA ansatze之间的性能有任何显著差异，但在成本层和混合层之间分布不同;见图4。虽然图中没有明确QAOA+ ansatz是否有利于辅助双量子比特层和第二混合层之间参数数量的任何特定分布的电路参数化，但可以清楚地看到，对于所有可能的参数组合，QAOA+比ma-QAOA+产生更高的近似比。

图4:使用具有不同参数数的ma-QAOA，所有非同构8节点3正则图的平均近似比。独立电路参数的总数等于 $n_{γ} + n_{β}$ 。

图5:所有非同构8节点3正则图的平均近似比，使用具有不同数量参数的QAOA+。其中 $β$ 和 $γ$ 是指在ansatz层中优化参数的个数。独立电路参数的总数等于 $n_{γ} + n_{β}$ 。

虽然图2给出了一个令人信服的例子，即具有4个优化参数的QAOA+(为简洁起见，我们将其称为QAOA+(4))，与具有更多参数的ma-QAOA相比，QAOA+给出了更高的近似比，但这些结果仅限于3规则8节点图的MaxCut问题。为了对更大的MaxCut实例建立这一事实，我们计算了QAOA+(4) ansatz的近似比，适用于所有类型的8节点和10节点随机正则图，平均超过10个每种类型的图，并使用BFGS优化和10次重启。然后，我们在相同的图上对maQAOA ansatz执行相同的平均过程，优化参数的数量从2增加到超过QAOA+(4)的近似比，记录ma-QAOA中超过QAOA+(4)所必需的最小参数数量。结果如图6所示。与图3不同的是，在ma-QAOA ansatz中，只考虑成本层和混合层之间的一个参数分布：对于每一个偶数个参数，它们在两层之间平均分配，而对于奇数个参数，成本层多一个参数。在maQAOA产生更高近似比的阈值之后，对每种类型最多10个随机规则图进行平均。当参数数低于该阈值时，QAOA+(4)优于maQAOA，而高于该阈值时，ma-QAOA开始产生更高的近似比，代价是QAOA参数的大维搜索空间。随着正则图的大小从8个节点增加到10个节点，阈值也随之上升，这表明与ma-QAOA相比，我们的 QAOA+ ansatz 的性能随问题大小而有利地扩展。

图6:对于d-正则8节点图和10节点图，maQAOA匹配QAOA+(4)性能所需的最小参数数。

4.讨论

为了提高标准QAOA方法所能达到的近似比，有必要通过增加QAOA层数来增加电路深度。然而，当在NISQ硬件上执行时，由于退相干，增加的电路深度会带来性能下降的严重后果。替代 QAOA ansatze 旨在修改QAOA 方法以降低电路深度方面的成本来增加 MaxCut 近似比。在这项工作中，我们引入了QAOA+作为替代ansatz，与标准 $p = 1$ QAOA 相比，它通过添加一个小于完整附加 QAOA 层的门辅助层来提高近似比。我们已经证明 QAOA+ 为中间 ansatz 提供了一个可行的替代方案，其近似比和电路深度介于 $p = 1$ 和 $p = 2$ QAOA 之间。

由于引入的 QAOA+ ansatz 允许大量经典优化参数，因此我们将 QAOA+ 与 ma-QAOA 进行了比较，ma-QAOA 是另一种具有低电路深度和大量参数的替代 QAOA ansatz。虽然当使用所有优化参数时，ma-QAOA 通常比 QAOA+ 产生更高的近似比，但我们已经证明，当 QAOA+ 和 ma-QAOA 中的参数数量相同时，QAOA+ 显着优于 ma-QAOA，性能差距越来越大问题大小。特别是，我们考虑了具有 4 个参数的 QAOA+，并证明 maQAOA 需要显着更多的优化参数来匹配 QAOA+ 的性能，这会带来很大的经典计算开销。因此，一般而言，QAOA+ 与 ma-QAOA 相比，在相同性能水平下需要更少的参数，同时具有更大的电路深度。当许多参数的目标函数最小化很困难时，QAOA+ 将是一个有价值的选择。与标准 $p = 2$ QAOA 相比，使用 QAOA+ 减少的电路深度对于密集图上的 MaxCut 实例尤为明显。

这项工作并没有对所有可能的替代QAOA方案进行详尽的研究。我们只考虑了由两个量子比特门的附加问题无关层的单一形状，它由纠缠所有量子比特的最小可能数量的门定义。QAOA+ ansatz的其他形状将在别处考虑，包括更硬件高效的ansatz，它尊重量子处理器可能的连通性限制。也可以考虑这样的修改，比如创建一个混合的ma-QAOA/QAOA+ ansatz，由多参数ma-QAOA和附加的多参数问题独立的QAOA+ ansatz层组成，以便将MaxCut近似比的改进更多地转移到经典计算，而不是增加QAOA电路深度。对拟议的QAOA+ ansatz中增加的优化参数的优化所需的计算资源的研究，以及贫瘠高原的相关挑战，也超出了本工作的范围。这里提出的性能比较是在所有优化实例的优化计算限制相等的假设下进行的，而不考虑参数的数量。此外，我们只考虑了 $p = 1$ 的情况，并且可以在更大的电路深度下分析性能。此外，由于这项工作的动机是在NISQ硬件上执行时潜在的性能改进，因此需要在现代量子处理器上进行噪声模拟和比较，以验证所提出的方法。

当能够以 $p ≫ 1$ 执行大规模 QAOA 实例的高保真量子计算硬件变得可用时，替代QAOA ansatze的真正价值将会显现出来。参数优化的计算复杂度和量子电路的可接受深度之间的最佳平衡将通过广泛的实验来确定。在此之前，继续提高 QAOA ansatz的能力以通过开发新的 ansatze 来解决 NP-hard 组合优化问题是至关重要的。我们希望本文中介绍的方法将有助于推动当前的标准QAOA向未来能够解锁实际量子优势的下一代QAOA发展。

原文链接：https://arxiv.org/pdf/2205.01192.pdf

---煤油灯科技victorlamp.com翻译整理---

上一篇：人工智能加速器和机器学习算法：协同设计和进化

下一篇：理解 CRISP-ML(Q)：机器学习生命周期过程

你可能也喜欢这些文章