QAOA 量子近似优化算法介绍_杏彩体育特色食品注册销售站

量子近似优化算法(QAOA)是在近期的量子计算机上实现的最有前途的显示量子优势的算法之一。作为一种近似算法，它并不是给出最好的结果，而是给出一个“足够好”的结果，其精度取决于近似比率的下界。

这里我们将以MAXCUT问题为例来了解QAOA的工作原理，最大切割问题（MAXCUT）是原始量子近似优化算法论文中描述的第一个应用。QAOA很有意思的一个原因是它具有展示量子霸权潜力。

在QAOA我们给出一个n位串Z=Z?Z?…Zn、Z?∈{0,1}?和m条款,其目的是最大化一个给定的目标/成本函数C=∑C?(Z)。K的取值范围为1到m,每一个 $\\mathrm{C_M}\\in\\{0,1\\}$ 。对于最大化Z的问题，有 $2^n$ 种可能性。最微不足道的解决方案是穷举法来查询，而这种方法的复杂度为O(2?)。这个问题没有精确的解，但存在一些近似的解。接下来我们将看到一个量子近似算法给出良好解的详细过程。

在量子近似算法中，我们将目标函数C作为一个算子。

$C|z\\rangle=\\sum_{k=1}^{m}C_{k}(z)|z\\rangle=f(z)|z\\rangle \\\\$

在这里C的特征向量是 $|z\\rangle$ ，每个特征向量的特征值为 $\\sum C_{K}(Z)=f(z)$ 。我们的目标是找到f(z’)对应的Cx的最大特征值。对于一个给定的任意状态|z>，我们可以创建一个系数为A?的态的叠加，从而对于给定的状态|ψ>在给定的∑A?|z〉状态下 ∑|A?|2=1。在给定的|ψ>状态下，我们可以求得C算符的期望值=<ψ|C|ψ>，如果已知这个期望可以用经典的方法计算，但是我们不知道使最大的z值。解决方法是找到使C(z)最大化的状态|ψ>作为找到使C(z)最大化的|z>的解。

$\\langle C\\rangle=\\langle\\psi|C| \\psi\\rangle=\\sum_{z \\in\\{0,1\\}^{n}}f(z)\\left|a_{z}\\right|^{2}\\leq \\sum_{z \\in\\{0,1\\}^{n}}f\\left(z^{\\prime}\\right)\\left|a_{z}\\right|^{2}=f\\left(z^{\\prime}\\right) \\sum_{z \\in\\{0,1\\}^{n}}\\left|a_{z}\\right|^{2}=f\\left(z^{\\prime}\\right) \\\\$

从上式我们可以看出，只有|ψ>=|z '>时，x=f(z’)。

所以解释这将是如果我们最大化得到x,它相当于测量状态|ψ>在|z>基，也就是说以概率为1得到|z’>，但是完全得到x基本是不可能的，只有得到一个无限接近于最大值的。

举个例子，状态|ψ>是|z>基态的叠加:

$H^{\\otimes n}|0\\rangle^{\\otimes n}=\\frac{1}{\\sqrt{2^{n}}}\\sum_{z \\in\\{0,1\\}^{n}}|z\\rangle \\\\$

当我们多次测量它时，我们得到了|z'>的基状态的分布，期望值是C(z)，最大值是C(z')。

分布的平均值为:

$\\langle C\\rangle=\\sum_{z \\in\\{0,1\\}^{n}}f(z)\\left|a_{z}\\right|^{2}=\\frac{1}{2^{n}}\\sum_{z \\in\\{0,1\\}^{n}}f(z) . \\\\$

在上面给定的状态获得一个给定的状态甚至是|z’>的概率是 1/2?，因为它是均匀分布。

因此，我们看到|ψ>态不够有趣，但我们可以旋转这个状态使其接近|z'>。因此，我们引入了两种旋转 U(C,γ)和U(B,β)，这两种旋转分别等效为e^(-iγC)和e^(-iβB)。

下面我们来谈谈这两种旋转:

$U(C, \\gamma)=e^{-i \\gamma C}=e^{-i \\gamma \\sum_{\\alpha=1}^{m}C_{\\alpha}}\緻line{\緻line{T}}\\Pi_{\\alpha=1}^{m}e^{-i \\gamma C_{\\alpha}}\\\\$

在这里对于特定的|z>我们使用的是基于约束的相门，对于每一个满足的条件Cα，在|z>上加一个相e^(-iγ)。

$|\\psi\\rangle=\\sum_{z \\in\\{0,1\\}^{n}}a_{z}|z\\rangle \\frac{U(C, \\gamma)}{\\longrightarrow}\\sum_{z \\in\\{0,1\\}^{n}}\\left[\\Pi_{\\alpha=1}^{m}U\\left(C_{\\alpha}(z), \\gamma\\right)\\right]a_{z}|z\\rangle, \ ext{ where: }\\left\\{\\begin{array}{ll}U\\left(C_{\\alpha}(z), \\gamma\\right)=1, & \ ext{ if }C_{\\alpha}(z)=0 \\\\ U\\left(C_{\\alpha}(z), \\gamma\\right)=e^{-i \\gamma}, & \ ext{ if }C_{\\alpha}(z)=1 \\end{array}\\right. \\\\$

这里我们看到，如果Cα=1或满足条件，我们将叠加态与相门e^(-iγ)相乘，否则，如果条件不满足或Cα为0，各自的状态保持不变。有时候甚至需要一个辅助量子位，这由C来决定。

让我们举个例子，假设有一个状态|ψ>=|x?> |x?> |x?>，当n=3 一般情况是|x?>=α?|0>+α?|1>,|x?>=β?|0>+β?|1> 和 |x?>=γ?|0>+γ?|1>, 以下几个式子成立.

C?=1 , 如果 x1=1 , C?=1 如果 x1=x2=1 , C?=1 如果 x1=x2=x3=1.

这给了我们各自的真值表C?(000)=0,C?(001)=0,C?(010)=0,C?(011)=0,C?(100)=1,C?(101)=1,C?(110)=1,C?(111)=1和C?(000)=0,C?(001)=0,C?(010)=0,C?(011)=0,C?(100)=0,C?(101)=0,C?(110)=1,C?(111)=1和C?(000)=0,C?(001)=0,C?(010)=0,C?(011)=0,C?(100)=0,C?(101)=0,C?(110)=0,C?(111)=1。

|x1x2x3>→α0β0γ0|000>+α0β0γ1|001>+α0β1γ0|010>+α0β1γ1|011>+R(γ)α1β0γ0|100>+R(γ)α1β0γ1|101>+R2(γ)α1β1γ0|110>+R3(γ)α1β1γ1|111>.

对于特定的基，相变不会改变概率。因此需要引入旋转算子U(B，β)。

对于旋转算子U(B,β)，B被定义为：

$B=\\sum_{j=1}^{n}\\sigma_{j}^{x}\\\\$

现在我们定义交换一位运算符的β相关乘积:

$U(B, \\beta)=e^{-i \\beta B}=\\prod_{j=1}^{n}e^{-i \\beta \\sigma_{j}^{x}}\\\\$

B的分解是确切的因为这些算子是交换的。

我们有一个旋转算子Rx(θ)=e^(iθ/2σ?)，θ∈[0,2π]。用它来生成U(B，β)

$R_{x}(2 \\beta)=e^{-i \\frac{2 \\beta}{2}\\sigma^{x}}=U(B, \\beta) \\\\$

2β∈[0,2π]→β∈[0，π]。这可以通过depth 1轻松完成，而不需要任何控制辅助位(如之前的Unitary操作符)。

当|ψ'>=U(C，γ)U(B，β)|ψ>与|z'>足够接近时，不确定是否适用上述算符。我们必须多次使用两个操作符，每次用不同的β和γ。应用它p次，我们得到一个依赖于角度的状态，定义为:

$|\\psi(\\boldsymbol{\\gamma}, \\boldsymbol{\\beta})\\rangle=|\\boldsymbol{\\gamma}, \\boldsymbol{\\beta}\\rangle=U\\left(B, \\beta_{p}\\right) U\\left(C, \\gamma_{p}\\right) \\cdots U\\left(B, \\beta_{2}\\right) U\\left(C, \\gamma_{2}\\right) U\\left(B, \\beta_{1}\\right) U\\left(C, \\gamma_{1}\\right)|\\psi\\rangle \\\\$

γ=(γ1、γ2···,γp)和β=(β1,β2,···,βp)。预先确定合适的角度并不容易，需要进行二维优化，通过多次迭代找到最优角度。

Maxcut问题是这样定义的:给定一个图(V,E)，问题是将一个图的节点划分成两个集合，使连接相反集合中的节点的边的数量最大化。节点或顶点可以用这样的方式表示，我们有一个n位的字符串，其中每个位的值可以是0或1。分划的总数可以有2?。

假设有一组n顶点和边的连通图{jk}其尺寸m。我们给每个顶点分成两类，通过g (i)=1 g (i)=-1，在这里g (i)是一个函数

我们可以分类每个顶点为一组两个给值g (i)=1 g (i)=1, g (i)是一个函数告诉如果一个顶点属于一个分区。

我们定义当g(i)g(j)=-1时发生切割。我们需要找到一个与集合{jk}有最大分歧数的切线。真正的最大值可以小于m。

我们的目标函数是C=∑C，是一个边。

C=1/2(-g(i)g(j) + 1)={0,1}

C是0 g(i)g(j)=1意味着顶点都在同一分区g(i)g(j)=-1显示了两个不同的分区的顶点意味着有一个分割。

我们可以从量子的角度转换这个目标函数，将所有的顶点作为n个量子位，这些顶点可以被分类为|0>或|1>。因此2^n种划分被分成2^n个计算基，这些计算基由|0>?的迭加构成。因此目标函数被转换成一个操作符： C|z>=∑ C(z)|z>=C(z)|z>

其中

C|z>=1/2(-g g? + I)|z>

因此,2^n分划分为2^n计算基础由创建叠加| 0 >?。目标函数被翻译为一个操作符:

这样,如果有一个切割gg?=-I和zj zk为|0>或|1>如果没有切割然后gg?=I,他们属于不同的量子位。因此我们得到|z>或0。

因为我们想要的输出或|z>或 0,目标函数的最佳选择将是σ?，因为它给σ?|0>=+1 1σ?| 1 >=-1。因此gg?为-I或I。

因此 C=1/2(g g? + I )=1/2 (σ? σ + I).

接下来我们来构建U(B,β)或U(C,γ)：

U(C,γ)=e^(-iγC)=e^(-iγ∑C)=∏e^(-iγC)=∏ U(C,γ)

U(C,γ)=e^(-iγ.1/2(-σ?σ? ?+ I)=e^(-iγ/2(σ?σ).e^(-iγ/2I)

因此，我们得到了第一部分的两个电路，它可以用CNOT和R(-γ)来实现，而第二部分的电路可以用e^(-iγ/2I)来实现，其角度为-γ/2。电路可表示为:

当我们用一个两个量子比特系统来表示一个4顶点图，并应用上面的U(C，γ)，我们看到当两个顶点都不同时，相e^(iγ)被添加，这表示一个切割。

通过对β和γ参数的优化来提高|ψ>态，计算符U(B，β)的流程与前面讨论的相同。

接下来，我们装讨论用QAOA算法来解决MaxCut问题，使用Blueqat库。

References:

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv1411.4028.
Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Phys. Rev. A, 97(2):1–13, 2018.
https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf
Edward Farhi. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. arXiv Prepr.arXiv1602.07674 3

公司新闻

QAOA 量子近似优化算法介绍

新闻资讯

关于杏彩体育

杏彩体育注册

新闻资讯

杏彩体育登录