DAOrayaki DAO研究奖金池：

资助地址:  DAOrayaki.eth

投票进展：DAO Reviewer  1/0 通 过

赏金总量：60 USD

研究种类：Quantum Computing, QAOA

原文作者:   Cameron Wolfe

创作者：Xinyang@DAOrayaki.org

审核者：Tan Zhi Xuan@DAOrayaki.org

原文:The Quantum Approximate Optimization Algorithm from the Ground Up

引言

近年来，量子计算的出现让许多研究团体（如物理学、计算机科学、数学等的）非常兴奋。基于对量子计算主题的兴趣，使该领域出现了众多理论贡献，催化了有影响力的算法的发展，如 Grover 搜索、Shor 算法、绝热优化（adiabatic optimization）等等。尽管这些理论证明了量子的优越性和实用性，但这些算法利用了过多的电路深度和量子比特数量，超出了目前量子硬件所能达到的水平。到目前为止，这种要求在一个物理系统中是无法实现的。

目前，量子计算被认为存在于嘈杂的中尺度量子（NISQ）时代，在这个时代，硬件被限制在可用的量子比特数量上，而电路深度被量子系统内产生的越来越多的噪声所限制。因此，许多最著名的量子算法（如上面提到的那些）的实际应用有限，导致研究人员专注于开发 NISQ 友好的量子算法。在这一领域，研究最广泛的两种算法是变异量子解算器（VQE）和量子近似优化算法（QAOA），它们都是变异量子算法（VQA），使用参数化的量子电路（参数以经典方式优化）来优化函数（例如，最小特征值/特征向量对，最大割问题，最大顶点覆盖，等等）。在这篇文章中，我的目的是深入解释 QAOA，并假设你对量子计算的背景只有轻微的了解（例如量子比特、量子态和基本的线性代数）；如果你有兴趣了解更多关于VQE的信息，请看这篇博文。

我将首先在高维度上解释 QAOA，包括算法的组成部分以及如何使用它来解决所研究的问题。在对 QAOA 进行初步描述之后，我将概述量子力学和数学中与对QAOA进行深入理解有关的众多概念。在有了这样的背景知识后，我将解释量子计算的绝热算法的细节，它与 QAOA 有着复杂的关系，这可以帮助理解 QAOA 与之前的算法的关系。在文章的最后，我将回到对 QAOA 的讨论上，旨在通过与量子计算的绝热算法的联系来看待算法的组成部分的原因。

量子近似优化算法（QAOA）

QAOA 是一种变异量子算法（即涉及经典优化的参数化量子电路的混合量子—经典算法），它是作为寻找组合优化问题的近似解而被提出（例如，最大割 MaxCut，最大顶点覆盖，最大可满足性 MaxSAT 等）。在高维度上，QAOA 将一系列参数化的量子门应用于一些初始状态，并优化这些门的参数，使最终状态（在量子门应用后）编码为一些所研究问题的近似解（如果你对最终状态相对于计算基础进行测量，它将产生一个高质量的解决方案）。QAOA 框架涉及几个组成部分。在这里，我只是简单地定义相关的组成部分，并说明它们是如何结合在一起的，而不深入考虑它们的原因，从而对 QAOA整体有一个基本的了解。

成本和混合器哈密顿量（Cost and Mixer Hamiltonians）

假设我们正在研究一个总共有 n 个量子比特的量子系统。在 QAOA 中，有两个相关的哈密顿量——混合器哈密顿量和成本哈密顿量。这些哈密顿量都是维度为 2^n x 2^n 的复值矩阵。但是，为了理解它们的目的，我们必须首先理解哈密顿量在量子系统中的作用。在量子力学中，哈密顿矩阵是一个编码量子系统能量的埃尔米特矩阵（hermitian matrix）。有一点要指出，哈密顿的特征值是实值，因为矩阵是隐式的，它代表了系统的可能能量水平（即测量系统总能量时的可能结果集）。

量子算法中的一个常见模式是在哈密顿量矩阵中编码一个所研究的问题（例如，某些函数的最小化/最大化），并找到一种方法来产生一个量子状态，当相对于该哈密顿量矩阵测量时，产生最低/最高的可能能量。在QAOA中，成本哈密顿量量（我们将表示为H_C）是以这种方式构建的，在其最低能量状态中编码一些所研究的问题（例如，MaxCut 或 MaxSAT 实例）的解决方案。对于 QAOA，成本哈密顿量通常是用伊辛模型（Ising model）构建的，它可以被用来将组合优化问题编码为具有单量子位 Pauli-Z 项的哈密顿量。尽管我们不会在这篇文章中详细介绍用伊辛模型构建成本哈密顿量，但这篇论文相当广泛地涵盖了这个主题。与成本哈密顿量量不同，混合器哈密顿量量与问题的定义无关，其定义如下。

QAOA 的默认混合器哈密顿量量

在上述方程中，所有 sigmig(∑) 变量对应于第 i 个量子位上的单量子位 Pauli-X 矩阵。混合器哈密顿量的一个重要属性是，它不应该与成本哈密顿量换位。如果这些矩阵不换位，那么它们就不能共享任何特征向量，这就可以防止QAOA定理（见下文）卡在能量较高的非最佳状态。

初始状态

从这里开始，我们还必须定义QAOA中使用的初始量子态，如下所示：

QAOA 的默认初始状态

这里，z 被用来表示我们的量子系统的计算基础。这个初始状态也可以写成如下（即这两个定义是相同的）：

QAOA 的默认初始状态的另一种定义

正如上文所见，QAOA 中的初始状态只是每个量子位上最大叠加状态的产物。有趣的是，这个初始状态是混合器哈密顿量的最大特征向量——为什么这很重要，我们在后面的文章中会解释清楚。此外，这种状态极易构建——只需对系统中的每个量子比特分别应用一个哈达玛门（Hadmard gate）——这使得它成为QAOA在实际量子硬件上实现的理想选择。

QAOA 拟设（QAOA Ansatz）

现在，我们已经定义了 QAOA 的所有相关组件，但还不清楚如何将这些组件组合在一起以解决优化问题。如前所述，QAOA 使用一系列参数化的量子门来演化初始状态，其中每个量子门被描述为量子状态与一个么正矩阵的乘法。量子门始终是单元的，以确保量子态的演化是绝热的，并且保留了量子态的归一化属性。QAOA中初始状态的演化由以下拟设描述，它产生的最终状态（理想情况下）能编码出所研究问题的近似最优解。

QAOA 拟设

这里，β 和 γ 是实值标量参数。QAOA定理总共包含2P个参数，由一系列具有不同标量参数的交替单一门组成。可以看出，这个拟设的“深度”是p，因为交替的门结构连续应用于初始状态 p 次。演化初始状态的么正是通过取成本和混合器哈密顿量的矩阵指数来构建的（即，hermitian 矩阵的指数总是么正的）。因此，QAOA 使用上述拟设，通过对初始状态应用一系列基于成本和混合器哈密顿量的参数化单一门来产生一个新的量子态。如果我们想让这个最终状态编码一个我们所研究问题的解决方案，我们所要做的就是设置 β 和 γ 参数，使 QAOA 的输出是一个成本哈密顿的低能量状态。但是......我们怎样才能找到正确的参数？

优化 QAOA 参数

我们最终状态相对于成本哈密顿量的预期能量可以表示如下，其中 Tr() 表示矩阵的跟踪。

QAOQ输出状态的预期能量

这个期望值在实践中可以通过对 QAOA 拟设产生的状态进行重复的、相同的测量来计算。然后，使用经典计算机，可以计算出这个函数的梯度（例如，使用参数移动规则），使 β 和 γ 参数按照与成本哈密顿量有关的期望值最接近的方向更新。通过迭代重复这个过程，QAOA 拟设的参数被更新，从而使最终状态的能量达到最小。因此，通过产生这个最终状态并对计算基础进行测量，可以产生一个近似的最佳解决方案（即，由于量子系统的测量是随机的，可以重复多次以确保找到一个好的解决方案）。请注意，QAOA 提供的解决方案是近似的，并不保证是全局最优的。

帮你了解 QAOA 的背景信息

现在，我们明白了 QAOA 是什么，但其组件背后的原因还不清楚。如果你像我一样，QAOA中的结构可能看起来很随意，让你想知道为什么它能工作，甚至有人是如何设计出这样一种算法的。为了澄清这种困惑，必须了解一些背景信息，我将在本节中概述这些信息。

矩阵指数

尽管在描述 QAOA 时简要介绍了矩阵指数，但由于其与 QAOA 定理的相关性，值得进一步概述其一些主要属性。如前所述，Hermitian 矩阵的指数始终是么正的。事实上，任何么正矩阵都可以写成以下形式。

作为指数的么正矩阵

其中 H 是一个任意的 hermitian 矩阵，i 是虚数单位，gamma 是一个任意的标量参数。通常情况下，量子门是通过对量子态进行时间演化来构建的，对于所用的哈密顿量而言。这种时间演化采取如下所示的么正矩阵形式，其中 h 表示普朗克常数。

相对于任意哈密顿量量的时间演化

正如上面的表达式所证明的，在量子态的演化和（指数化的）哈密顿矩阵之间存在着复杂的联系。哈密顿量的矩阵指数经常作为在某些所研究系统中进行量子态的时间演化的一种方式出现。此外，在矩阵指数中使用的标量参数可以被解释为执行这种演化的总时间。在 QAOA 这里，演化以交替的方式发生在成本和混合器哈密顿量，我们进行经典的优化，以确定我们每个交替的单一门应用的最佳时间。

除了与量子态演化的关系外，还有一个矩阵指数的属性将是有用的。如果两个矩阵相互交换，那么矩阵指数的以下属性是真的。

当我们在后面的文章中讨论 Trotterization 时，这个属性就变得相关了。此外，基于这一属性，人们可能会注意到，如果成本和混合器哈密顿量相交，QAOA 拟设的么正矩阵的顺序将是不相关的，从而为两个哈密顿量必须不相交的要求提供额外的推理。

薛定谔方程

上述关于哈密顿量的时间演化的表达式似乎是凭空出现的，但它实际上是从薛定谔方程推导出来的——这是一个极其著名的偏微分方程，用于表达量子态以及它们如何随时间变化。这个方程有很多写法，在本文里，我将把它表达如下：

薛定谔方程

这里，薛定谔方程描述了量子态在时间 t 上相对于某个哈密顿量的动态。有趣的是，如果 H 是时间无关的（即哈密顿量不随时间t变化），上述方程可以被解出，得到以下结果。

具有时间无关的哈密顿量的薛定谔方程

可以看出，薛定谔方程给出的用于演化时间 t 的初始量子态的么正矩阵与上一节给出的表达式是相同的。

在这一点上，确定一个量子态的动力学似乎是很容易的——问题是什么？好吧，当有关的哈密顿量不是与时间无关的时候，问题就出现了。也就是说，如果哈密顿方程随时间t的变化而变化，那么薛定谔方程就变得非常难解（通常是不可能）。因此，我们必须找到它的近似解，以使量子态相对于与时间有关的哈密顿方程演化。

通过时间上的离散化实现近似演化

那么，我们如何找到这样一个近似解呢？好吧，我们知道量子态在时间 t 的演化可以由一个么正矩阵来描述。让我们把这个么正表示为下图，其中进化发生在时间t0到时间t。

通常情况下，对时间上连续的东西（如上图所示的么正矩阵）进行近似的第一步是将其划分为可以组合在一起的离散时间步长。如下图所示（注意，两个么正矩阵的乘积总是单一的）。

在时间上对么正矩阵进行离散

将我们的么正矩阵离散成许多更小的时间步长类似于用许多分段函数来趋近一个连续函数。也就是说，随着离散时间步数的增加，近似变得更加精确。再进一步说，每个离散时间段的么正矩阵可以用随时间变化的哈密顿量来表示，如下所示。

随时间变化的哈密顿量的离散演化

如上所述，通过采取离散的时间步长，我们可以通过反复做以下事情来近似地进行相对于时间依赖的哈密顿量的连续时间演化。(1) 在某个固定时间得到哈密顿量，(2) 假设哈密顿量在很短的时间间隔内是固定的，(3) 在很短的时间内对这个固定的哈密顿量进行演化。通过在很短的时间内进行这样的离散演化，我们创建了一个级联的么正矩阵，当这些矩阵组合在一起时，近似于所需的相对于时间依赖的哈密顿量的时间演化。

Trotterization（Suzuki-Trotter 分解）

时间上的离散化在很多时候并不是近似与时间相关的哈密顿演化的唯一必要组成部分。这是因为哈密顿量经常被表达为多个不相交的哈密顿量之和，产生一个类似于下面的表达式：

具有不相交哈密顿分量之和的么正

在上面的表达中，矩阵指数不能被分解为几个么正矩阵的乘积，因为哈密顿量的每个分量都不相交（回顾前面对矩阵指数的解释中的最后一个属性）。因此，我们遇到了以下问题：

由于实现基于多个非相交哈密顿分量之和的量子门是很困难的，从业人员经常依靠 Suzuki-Trotter 分解（即通常所说的“Trotterization”）来将这种表达式分解为多个么正矩阵的乘积。这种分解有以下形式：

Suzuki-Trotter 分解

使用 Suzuki-Trotter 分解，本节开头介绍的么正可以被哈密顿量的每个非相交分量的独立矩阵指数的重复级联所近似。这样的分解大大简化了这个么正矩阵作为量子门的实现，这对于 QAOA 这样的 NISQ 友好型量子算法极为重要。因此，Trotterization 在量子计算中经常出现。

量子绝热算法

深入了解 QAOA 的最后一步是了解其衍生的算法：量子绝热算法（QAA）。QAA 是一种算法，最初是为了利用绝热演化来寻找组合优化问题的精确解决方案而提出的。在高维度上，QAA 类似于QAOA，因为它从某种初始状态开始，并通过演化这种状态来产生成本哈米尔顿的低能量状态。然而，QAA 不是一种可以在 NISQ 设备上实现的算法，因为它需要在一个（潜在的）非常长的时间内进行演化，超过了当前硬件的能力。

绝热定理

QAA 依靠的是量子力学的绝热定理。给定一个随时间变化的哈密顿量和该哈密顿量在时间 t0 时的低能特征态，绝热定理指出，如果量子态在时间t内演化得足够慢，它将在整个时间内保持为哈密顿量的低能态（即演化后的状态是我们哈密顿量在时间 t0+t 的低能态）。这个定理依赖于这样一个假设，即在任何给定的时间，哈密顿量的两个最低特征值之间存在一个缺口（gap）。此外，演化所需的时间取决于这个缺口，如果缺口小，可能会变得任意大。此外，这个缺口的数值一般无法估计，因此很难确定进行这种演化所需的总时间。

用绝热定理解决优化问题

基于绝热定理，QAA 提出以下建议。假设我们有一些我们想要解决的组合优化问题实例。从前面对QAOA的描述中可以看出，我们可以将这个问题实例编码在一个成本哈密顿量中，这样问题的解决方案就由哈密顿的低能量状态给出。此外，回顾一下，之前定义的混合器哈密顿量有一个很容易构造的低能状态（即 QAOA 内的初始状态）。然后，假设我们根据在 QAOA 描述中定义的成本和混合器哈密顿量，定义以下随时间变化的哈密顿量：

成本和混合器哈密顿量之间的差值

鉴于上述随时间变化的哈密顿量，我们可以很容易地构建时间 0 时的低能状态（即它只是混合器哈密顿量的低能状态）。此外，时间 T 时的随时间变化的哈密顿量等于成本哈密顿量。因此，如果我们对这个初始状态进行足够长的演化，根据绝热定理，我们将最终产生成本哈密顿的低能状态（通过 Perron-Frobenius 定理，我们可以保证非零的特征缺口 eigengap）。因此，这样的演化产生了我们所研究问题的一个精确的解决方案！

回到 QAOA

现在我们已经涵盖了相关的背景信息，是时候回到 QAOA 并对其原因有一个更全面的了解了。特别是，QAOA 可以被解释为 QAA 的近似值，这个可以利用前文讨论过的工具推导出来。

从QAA到QAOA

QAOA 和 QAA 都从相同的初始状态（即平等的叠加状态）开始，并试图演化这个初始状态以产生成本哈密顿量的低能量状态。考虑以下时间相关的哈密顿量，它是混合器和成本哈密顿量之间的插值。

如前所述，以封闭形式表达与时间相关的哈密顿量的演化是非常困难的。因此，我们必须用离散的时间步长来近似这种演化，如下所示。我们把准确表达我们的量子态相对于时间依赖的哈密顿量的演化的单元表示为U。

此外，上述表达式中的每个随时间变化的哈密顿项都可以相对于成本和混合器哈密顿量来表示（从这里开始，为了便于阅读，只列出序列中的第一个项，其他项也遵循同样的模式）。

现在，我们可以采取 Suzuki-Trotter 分解法，得出以下表达式，其中我们把 p 看作是某个大的正整数。回顾一下，成本和混合哈密顿量并不相交。因此，我们需要进行 Trotter 化，以这种方式分解矩阵指数。

这看起来有点熟悉......通过将每个哈密顿量的常数（不包括虚数部分）表示为 β 和 γ，我们得出以下表达式：

所以，在将我们的演化分解为离散的时间步长并应用 Trotterization 之后，我们得到的表达式（几乎）完全类似于我们在 QAOA 中的拟设！因此，QAOA 可以被用做 QAA 的近似，其中 β 和 γ 参数并不固定，深度 p 可以任意设置！直观地说，随着 QAOA 深度的增加，这种近似的质量必须提高，因为 Suzuki-Trotter 分解只有在无限 p 的极限下才是真的。有趣的是，通过假设一个无限深度的拟设，以及与 QAA 和绝热定理的联系，我们衍生出了 QAOA 的几个理论结果。

重要的区别

尽管 QAOA 可以被解释为 QAA 的近似值，但这些算法之间有几个重要的区别。首先，QAOA 是一种变异量子算法，包含参数化的量子电路，这些电路被经典地优化以满足一些目标。相比之下，QAA 中的相应“参数”是固定的，根据编码了量子态随时间变化的么正矩阵的近似中使用的时间间隔。因此，QAOA 不一定近似于 QAA，因为它的参数可以任意设置，可能不反映 QAA 内出现的离散时间间隔常数。此外，QAA 的深度可能是任意大的，而 QAOA 拟设的深度通常要小得多，以适应量子硬件的限制（已经在物理上实现的最深的 QAOA 拟设的深度只有3）——记住，QAOA 是 NISQ 时代量子计算机的实用算法。因此，实用的 QAOA 算法和 QAA 之间的联系，在现实中是相当有限的。最后，QAOA 为所研究的问题找到一个近似的解决方案，而 QAA 则是在有足够时间的情况下找到全局最优的解决方案，这使得这两种算法的目标有些不同。

结语

在这篇文章中，我试图从基础开始对 QAOA 提供一个相对全面的了解。通过提供相关背景，我在 QAA 和 QAOA 之间建立了联系，揭示了 QAOA 可以被解释为 QAA 的近似值（尽管这两种算法之间存在实际差异）。这揭示了 QAOA 各方面的原因，如混合器哈密顿量的选择（即来自 QAA）和交替的么正结构（即可以解释为离散的、Trotterized 的QAA的近似）。

感谢你的阅读，我希望你喜欢这篇文章。如果你发现任何错误或有建议，请随时与我联系。此外，如果你对这个话题感兴趣，我鼓励你来参观我在莱斯大学的研究实验室，该实验室进行的研究与量子计算的许多主题有关。

参考链接：

1.Grover 搜索：

https://en.wikipedia.org/wiki/Grover%27s_algorithm

2.Shor 算法：

https://en.wikipedia.org/wiki/Shor%27s_algorithm

3.绝热优化（adiabatic optimization）：

https://en.wikipedia.org/wiki/Adiabatic_quantum_computation

4.这篇博文：

https://www.mustythoughts.com/variational-quantum-eigensolver-explained

5.哈密顿量：

https://en.wikipedia.org/wiki/Hamiltonian_(quantum_mechanics)

6.埃尔米特矩阵（hermitian matrix）：

https://zh.wikipedia.org/wiki/%E5%9F%83%E5%B0%94%E7%B1%B3%E7%89%B9%E7%9F%A9%E9%98%B5

7.伊辛模型（Ising model）：

https://en.wikipedia.org/wiki/Ising_model

8.Pauli-Z：

https://en.wikipedia.org/wiki/Pauli_matrices

9.Pauli-X：

https://en.wikipedia.org/wiki/Pauli_matrices

10.换位：

https://en.wikipedia.org/wiki/Commuting_matrices

11.哈达玛门（Hadmard gate）：

https://qiskit.org/textbook/ch-states/single-qubit-gates.html#hgate

12.么正：

https://en.wikipedia.org/wiki/Unitary_matrix

13.归一化属性：

http://farside.ph.utexas.edu/teaching/qmech/Quantum/node34.html

14.拟设：

https://pennylane.ai/qml/glossary/circuit_ansatz.html

15.矩阵指数：

https://en.wikipedia.org/wiki/Matrix_exponential

16.参数移动规则：

https://pennylane.ai/qml/glossary/parameter_shift.html

17.Perron-Frobenius：

https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem

18.最深的 QAOA 拟设：

https://arxiv.org/abs/2004.04197

19.与我联系：https://wolfecameron.github.io/

20.研究实验室：

http://akyrillidis.github.io/group/

21.Source：

https://www.newscientist.com/article/2252933-quantum-computers-may-be-destroyed-by-high-energy-particles-from-space/

通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！

官方网站：https://daorayaki.org

Media：https://media.daorayaki.org

Discord server: https://discord.gg/wNUPmsGsa4

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

Twitter: @daorayaki_

微信助手：DAOrayaki-Media

小宇宙：DAOrayaki

详情请参考：

Dora Factory支持去中心化DAO研究组织DAOrayaki

对DAOrayaki第一阶段的回顾--去中心化媒体的先驱

DAOrayaki ｜DAOrayaki 开启去中心化治理2.0时代

DAOrayaki ｜风险投资的范式转移：无限主义基金和无限游戏

DAOrayaki ｜DAOrayaki dGov 模型：基于Futarchy的正和游戏

更多关于DAO的文章，关注Dorafactory，查看往期文章。