tutorials/mbqc/QAOA_CN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于测量的量子近似优化算法\n",
    "\n",
    "<em> Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. </em>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 多项式无约束布尔优化问题\n",
    "\n",
    "在应用数学和理论计算机科学中，**组合优化问题（combinatorial optimization problem）** 是在一个离散的解空间中寻找最优解的一类问题。在[量桨平台教程：量子近似优化算法](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html)中，已经介绍过了一般的组合优化问题。在这里，我们关注一类具体的问题：**多项式无约束布尔优化问题（polynomial unconstrained boolean optimization problem, PUBO）**。\n",
    "\n",
    "给定一个变量为 $x = \\{x_1,\\cdots,x_n\\}$ 的 $n$ 元多项式，\n",
    "\n",
    "$$\n",
    "C(x) = \\sum_{\\lambda \\in \\Lambda } \\alpha_{\\lambda} \\prod_{j \\in \\lambda} x_j,\\tag{1}\n",
    "$$\n",
    "\n",
    "其中每个变量 $x_i \\in \\{0,1\\}$，$\\underset{j \\in \\lambda}{\\prod} x_j$  为一个单项式，$\\lambda \\subseteq [n]:= \\{1, 2, ..., n\\}$ 为一个指标集，$\\Lambda$ 为指标集的集合，$\\alpha_\\lambda$ 为每个单项式对应的实系数。在 PUBO 中，$C(x)$ 称为目标多项式，我们需要寻找一组最优解 $x^* = \\{x_1^*, x_2^*, ..., x_n^*\\} $ 使得目标多项式的取值最大，即\n",
    "\n",
    "$$\n",
    "x^* = \\underset{x}{\\text{argmax}} \\ C(x).\\tag{2}\n",
    "$$\n",
    "\n",
    "多项式无约束布尔优化问题是一种应用极为广泛的数学优化模型，对这种模型的高效求解有助于解决很多现实中的问题。如果需要求解的目标多项式次数为二，则称为二次多项式组合优化。这类模型可以描述例如最大独立集（MIS）、最大割（Max-Cut）、最大点集覆盖（Max-Coverage）等很多图论中的组合优化问题，并在诸如统计物理，网络设计，超大规模集成电路（VLSI）设计，数据聚类分析，金融分析和机器调度等方面有广泛应用。如果目标多项式次数大于二，这样的多项式组合优化则在信号处理（SP）和计算机视觉（CV）中图像重构等领域有重要应用。但是一般 PUBO 的求解是 NP-困难的，目前，精确求解这类问题没有有效的多项式时间复杂度的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 量子近似优化算法\n",
    "\n",
    "在 2014 年 Farhi 及其合作者通过经典计算与量子计算混合迭代的思路，提出了量子近似优化算法 **(quantum approximate optimization algorithm, QAOA)** [1]，一方面希望利用量子计算机的能力更好地解决组合优化问题，另一方面也希望通过此问题展现量子计算机的优势。关于 QAOA 原理的详细论述请参见[量桨平台教程：量子近似优化算法](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html)，此处我们简要回顾一下该算法的基本思想和实现步骤。\n",
    "\n",
    "要将组合优化问题翻译为量子版本，我们需要先将待优化的变量编码为量子态，以及将目标多项式编码为系统的哈密顿量。接下来，我们对这两点逐一进行讲解。\n",
    "\n",
    "### 变量编码为量子态\n",
    "\n",
    "对于变量 $x$，根据定义，它的每个比特的取值均为 $0$ 或 $1$，这便很自然地与量子态的 $|0\\rangle$, $|1\\rangle$ 系统相对应。于是长度为 $n$ 的布尔变量 $x$ 可以对应于一个 $n$ 量子比特构成的量子态，即：\n",
    "\n",
    "$$\n",
    "|x\\rangle = |x_1x_2...x_n\\rangle,\\tag{3}\n",
    "$$\n",
    "\n",
    "从而寻找原问题的最优解 $x^{*}$ 就相当于寻找某一个量子态 $|x^{*} \\rangle$。\n",
    "\n",
    "### 目标多项式编码为系统哈密顿量\n",
    "\n",
    "对于目标多项式 $C(x)$，我们可以将其编码到一个系统哈密顿量 $H_C$ 的对角元上，并使其满足对任意的 $x$，\n",
    "\n",
    "$$\n",
    "H_C |x\\rangle = C(x) |x\\rangle.\\tag{4}\n",
    "$$\n",
    "\n",
    "值得注意的是，假设原问题的一个最优解是 $x^{*}$，那么我们有：\n",
    "\n",
    "$$\n",
    "\\langle x^{*} | H_{C} |x^{*} \\rangle = C(x^{*}).\\tag{5}\n",
    "$$\n",
    "\n",
    "于是寻找原组合优化问题的最优解 $x^{*}$ 等同于寻找系统哈密顿量 $H_C$ 的最大本征值对应的本征态 $|x^{*} \\rangle$，即：\n",
    "\n",
    "$$\n",
    "|x^{*}\\rangle = \\underset{|x\\rangle}{\\text{argmax}} \\ \\langle x | H_C | x \\rangle.\\tag{6}\n",
    "$$\n",
    "\n",
    "**注意**：以上给出了编码目标多项式到系统哈密顿量的方式，但是如何更方便的找到 $H_C$ 的表达式呢？我们不妨先考虑一个简单的例子。假设目标多项式为 $C(x) = 1-2x$，即 $C(0) = 1, C(1) = -1$，则可以跟据定义快速找到对应的系统哈密顿量为 $H_C = Z$，其中 $Z$ 为 Pauli $Z$ 门。那么一般地，我们可以先对目标多项式 $C(x)$ 进行变量替换 $1-2x_i = z_i$ (即 $x_i = (1-z_i)/2$)，其中 $z_i \\in \\{-1, 1\\} $，然后将 $z_i$ 变量替换为 Pauli $Z_i$ 算符，其中下角标 $i$ 表示对应的量子系统。可以验证这样构造的哈密顿量 $H_C$ 刚好满足 $H_C |x\\rangle = C(x) |x\\rangle$。\n",
    "\n",
    "为了方便使用，我们在 `qaoa` 中，定义了 `get_cost_hamiltonian` 函数，用来获取给定多项式的系统哈密顿量，我们可以直接调用它。\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import get_cost_hamiltonian\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QAOA 电路\n",
    "\n",
    "在将变量和目标多项式分别编码到量子态和系统哈密顿量上之后，我们引入辅助哈密顿量 $H_B$，具有如下形式：\n",
    "\n",
    "$$\n",
    "H_B = \\bigotimes_{j=1}^n X_j,\\tag{7}\n",
    "$$\n",
    "\n",
    "其中，$X_j$ 为作用到第 $j$ 个比特上的 Pauli X 门。依据绝热定理 [2,3]，在 QAOA 中，我们希望将 $H_B$ 最大本征值对应的本征态 $|+\\rangle^{\\otimes n}$ 演化到 $H_C$ 最大本征值对应的本征态。因此，我们可以构造量子电路实现如下的量子态演化，\n",
    "\n",
    "$$\n",
    "|\\gamma,\\beta\\rangle :=  \\left(\\prod_{i=1}^p U_B(\\beta_i)U_{C}(\\gamma_i)\\right)|+\\rangle^{\\otimes n},\\tag{8}\n",
    "$$\n",
    "\n",
    "其中 $U_{C}(\\gamma) = e^{-i\\gamma H_{C}}$，$U_B(\\beta) = e^{-i \\beta H_B}$，$\\beta,\\gamma$ 为待训练的参数 ，$p$ 为给定的算法深度，$p$ 越大，算法求得的解越精确，但是计算量也越大。\n",
    "\n",
    "关于电路模型下 QAOA 的详细介绍，请参见[量桨平台教程：量子近似优化算法](https://qml.baidu.com/tutorials/combinatorial-optimization/quantum-approximate-optimization-algorithm.html)，我们这里不做赘述。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  基于测量的量子近似优化算法\n",
    "\n",
    "如前所述，[基于测量的量子计算](MBQC_CN.ipynb)提供了一种不同于量子电路模型的计算方式。由于该模型的通用性，任何量子电路模型都可以找到与其相对应的 MBQC 版本。文献 [4] 提出了一种基于测量的变分量子本征求解器（measurement-based variational quantum eigensolver, MB-VQE），类似地，我们在此给出**基于测量的量子近似优化算法（measurement-based quantum approximate optimization Algorithm, MB-QAOA）** 作为 MBQC 模型的入门算法教程之一。注意到量子电路模型中，不同的电路可以实现完全相同的演化效果。同样地，我们也可以找到很多种不同的 MBQC 算法完成相同的功能。在这里，我们给出一种较为简洁的 MBQC 版本的 QAOA 算法，并使用我们设计的 MBQC 模块对该算法进行模拟。\n",
    "\n",
    "\n",
    "### 技术思路\n",
    "\n",
    "注意到 QAOA 的核心是对初始态完成 $U_{C}$ 和 $U_B$ 的交替演化。我们先用下面两个引理分别讲解在 MBQC 模型中该如何简单地完成这两种演化过程。感兴趣的读者可以尝试自行证明或者参见 [5]。\n",
    "\n",
    "**引理 1:** 假设 $|\\psi\\rangle_{1 \\cdots k}$ 为一个 $k$ 比特的量子态，对其进行 $e^{i\\theta Z_1Z_2\\cdots Z_k}$ 的演化，可以通过如下测量方案实现：\n",
    "\n",
    "$$\n",
    "M_0^{YZ}(2\\theta) \\left(\\prod_{j=1}^{k} CZ_{0,j}\\right) \\Big(|+\\rangle_0 \\otimes |\\psi\\rangle_{1 \\cdots k}\\Big) \\longrightarrow \\left(\\prod_{j=1}^{k} Z_j\\right)^{s_0}\\, e^{i\\theta Z_1Z_2\\cdots Z_k}\\, |\\psi\\rangle_{1 \\cdots k},\\tag{9}\n",
    "$$\n",
    "\n",
    "即我们先在 $0$ 系统上准备一个加态，然后对这个比特和输入态 $|\\psi\\rangle_{1 \\cdots k}$ 的每一个比特做 CZ 门，最后用 YZ 平面上的投影测量来测量 $0$ 系统上的比特，测量角度为 $2\\theta$，测量完成后，处于 $1,\\cdots,k$ 系统上的量子态将演化为箭头右边的状态，也就是 $e^{i\\theta Z_1Z_2\\cdots Z_k}\\, |\\psi\\rangle_{1 \\cdots k}$ 附加上 $\\left(\\prod_{j=1}^{k} Z_j\\right)^{s_0}$ 的副产品，其中 $s_0 \\in \\{0,1\\}$ 为 $0$ 系统的测量结果。\n",
    "\n",
    "注意到 $U_C$ 的本质是跟据目标函数连续完成多个不同的 $e^{i\\theta Z_1Z_2\\cdots Z_k}$ 的演化，因此将引理 1 中的实现方式重复使用多次，即可实现 $U_C$。\n",
    "\n",
    "**引理 2:** 设 $1$ 系统的量子态 $|\\psi\\rangle_1$ 为输入的单比特量子态，对其进行 $R_x(\\theta_2)R_z(\\theta_1)$ 的演化，可以通过如下测量方案实现：\n",
    "\n",
    "$$\n",
    "M_2^{XY}\\big((-1)^{1+s_1}\\theta_2\\big) M_1^{XY}(-\\theta_1) \\Big(CZ_{23} CZ_{12}\\Big) \\Big(|\\psi\\rangle_1 \\otimes |+\\rangle_2 \\otimes |+\\rangle_3 \\Big) \\longrightarrow Z^{s_1} X^{s_2} R_{x}(\\theta_2) R_z(\\theta_1) |\\psi\\rangle_3.\\tag{10}\n",
    "$$\n",
    "\n",
    "即我们先在 $2$ 和 $3$ 系统上分别准备一个加态，对 $1$， $2$ 系统和 $2$， $3$ 系统分别作用 $CZ$ 门，然后用 $XY$ 平面上的投影测量来测量 $1$ 系统上的比特，测量角度为 $-\\theta_1$， 记录测量结果为 $s_1$，再用 $XY$ 平面上的投影测量来测量 $2$ 系统上的比特，测量角度为 $(-1)^{1+s_1}\\theta_2$， 记录测量结果为 $s_2$，测量完成后在 $3$ 系统上的量子态将演化为箭头右边的状态，也就是 $R_{x}(\\theta_2) R_z(\\theta_1) |\\psi\\rangle_3$ 附加上副产品 $Z^{s_1} X^{s_2}$。\n",
    "\n",
    "注意到 $U_B$ 的本质是在不同比特上实现 $R_x$ 旋转门，因此我们可以利用引理 2 中的方式，令 $\\theta_1 = 0$ 来实现 $U_B$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过以上两个引理，相信大家对 MB-QAOA 的实现有了一些想法。接下来我们跟据 MBQC 模型“三步走”流程（量子图态准备、单比特测量、副产品纠正）进行详细介绍。\n",
    "\n",
    "### 量子图态准备\n",
    "\n",
    "由于量子图态和图一一对应，所以我们给出对应的图即可，我们称这个图为 **MB-QAOA 图**。\n",
    "\n",
    "#### 单层 MB-QAOA 图的构造\n",
    "\n",
    "根据目标多项式 $C(x)$ 中变量的个数 $n$，依次纵向排列 $n$ 个绿色、 $n$ 个蓝色节点和 $n$ 个灰色节点，并依次记绿色节点为 $G^v$，蓝色节点为 $B^v$，灰色节点为 $H^v$，其中 $1 \\leq v \\leq n$。连接并排的绿色和蓝色节点，以及蓝色和灰色节点；\n",
    "对目标多项式 $C(x)$ 做变量替换 $x = (1-z)/2$，得到新的目标多项式记为 \n",
    "\n",
    "$$\n",
    "C(z) = c + \\sum_{v} \\eta_v z_v + \\sum_{S} \\eta_S \\prod_{j \\in S} z_j,\\tag{11}\n",
    "$$\n",
    "\n",
    "其中 $c$ 为常数项，$1 \\leq v \\leq n$ 为线性项的指标，对应系数为 $\\eta_v$，$S$ 为非线性项的指标集，对应系数为 $\\eta_S$。我们要求补齐线性项中未出现的元素，并且设其对应系数为 $0$。那么对于 $C(z)$ 中除常数项外的每个非线性项的单项式 $\\prod_{j \\in S} z_j$，我们在绿色节点的左边添加一个新的红色节点，并记为 $R^S$，连接红色节点 $R^S$ 和绿色节点 $G^v$ ($ \\forall v\\in S$)。\n",
    "\n",
    "以上构造出来的图称为单层 MB-QAOA 图，根据之前讨论，我们将会通过测量红色节点来完成 $U_C$ 的演化，通过测量绿色和蓝色节点完成 $U_B$ 的演化，并且演化后的态存储在灰色节点中。为了方便理解，以下图 1 给出了一个具体的单层 MB-QAOA 图的例子。\n",
    "\n",
    "![QAOA graph](./figures/mbqc-fig-qaoa_graph_1.jpg)\n",
    "<div style=\"text-align:center\">图 1：一个单层 MB-QAOA 图的例子，其中变量替换后的目标多项式为 $C(z) = z_2 + z_1 z_3 + 5 z_3 z_4 - 2 z_1 z_2 z_4$。 </div>\n",
    "\n",
    "注：单项式的系数对 MB-QAOA 图结构的构造没有影响，但这些系数会影响到测量节点时的角度（见下文）。\n",
    "\n",
    "#### $p$ 层 MB-QAOA 图的构造\n",
    "\n",
    "由于电路模型下的 QAOA 会对 $U_C$，$U_B$ 交替演化 $p$ 次，MBQC 模型下的 $p$ 层 QAOA 也是如此。图 $1$ 所示为 $p=1$ 情况，对于一般的 $p>1$，我们需要在右侧将单层 MB-QAOA 图重复 $p$ 次，并且下一层的绿色节点（对应输入态）要和上一层的灰色节点（对应输出态）重合，以此保证量子态可以进行连续的演化。最终的量子态会保存在最右端的灰色节点上。为了方便理解，以下图 2 给出了一个具体的 $p$ 层 MB-QAOA 图的例子。\n",
    "\n",
    "![QAOA graph](./figures/mbqc-fig-qaoa_graph_p.jpg)\n",
    "<div style=\"text-align:center\">图 2：一个 $p$ 层 MB-QAOA 图的例子，其中变量替换后的目标多项式为$C(z) = z_2 + z_1 z_3 + 5 z_3 z_4 - 2 z_1 z_2 z_4$。 </div>\n",
    "\n",
    "在 `qaoa` 中，我们定义了 `preprocess` 函数，用于生成上述的 MB-QAOA 图，我们可以直接调用：\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import preprocess\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 单比特测量\n",
    "\n",
    "量子图态构造好之后，下一步就是设计每个比特上的测量方式了。根据以上两个引理，我们可以计算出每一步测量对应的角度，在这之中要注意的是测量角度对前面测量结果的依赖关系。\n",
    "\n",
    "假设 MB-QAOA 电路总深度为 $p$ 层，测量顺序按 MB-QAOA 图从左往右，从上到下的顺序按列进行测量，考虑第 $1 \\leq l \\leq p$ 层的 MB-QAOA图，具体每个节点的测量方式见表 1：\n",
    "\n",
    "|节点|测量基|测量角度|测量结果|\n",
    "|:---:|:---:|:---:|:---:|\n",
    "|$$R_l^S$$|$$M^{YZ}$$|$$T \\Big(1+\\sum_{v \\in S}\\sum_{k=1}^{l-1}s(B_k^v)\\Big) \\cdot 2 \\eta_{S} \\gamma_{l} $$|$$s(R_l^{S})$$|\n",
    "|$$G_l^v$$|$$M^{XY}$$|$$T \\Big(1+\\sum_{k=1}^{l-1}s(B_k^v)\\Big) \\cdot 2 \\eta_v \\gamma_l $$|$$s(G_l^{v})$$|\n",
    "|$$B_l^v$$|$$M^{XY}$$|$$T \\Big(1+\\sum_{k=1}^{l}\\sum_{S:v \\in S}s(R_k^S) + \\sum_{k=1}^{l}s(G_k^v)\\Big) 2 \\beta_l$$|$$s(B_l^{v})$$|\n",
    "\n",
    "<div style=\"text-align:center\">表 1：MB-QAOA 详细的测量方式 </div>\n",
    "\n",
    "其中 $1 \\leq v \\leq n$ 为变量替换后目标多项式的线性项指标，对应系数为 $\\eta_v$，$S$ 为变量替换后目标多项式的非线性项指标集，对应系数为 $\\eta_S$，$\\beta_l,\\gamma_l$ （$1 \\leq l \\leq p$）为待训练的参数，$M^{XY}$ 表示在 $XY$ 平面内的测量，$M^{YZ}$ 表示在 $YZ$ 平面内的测量，求和 $\\sum_{k=1}^0$ 约定为 $0$，函数 $T(x) = (-1)^x$。$R_k^S$ 代表图 2 中的红色节点，$s(R_k^S)$ 代表其对应测量结果；$G_k^v$ 代表图 2 中的绿色节点，$s(G_k^v)$ 代表其对应测量结果；$B_k^v$ 代表图 2 中的蓝色节点，$s(B_k^v)$ 代表其对应测量结果。\n",
    "\n",
    "为了方便 MB-QAOA 中测量角度的计算，我们在 `qaoa` 中，定义了测量角度函数 `adaptive_angle`。我们只需输入测量结果的字典, 待测量的比特标签, 待训练的角度参数和多项式系数等信息，即可按上表自动计算出测量角度。\n",
    "\n",
    "我们可以直接调用：\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import adaptive_angle\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 副产品纠正\n",
    "\n",
    "通过以上全部测量后（除最后一列灰色节点外），MB-QAOA 图中最末端灰色节点对应的量子态会演化为 $|\\gamma,\\beta\\rangle$ 附加上测量中产生的一些副产品。在第 $v$ 个节点上的副产品为 $X^{x}Z^{z}  $，其中指数：\n",
    "\n",
    "$$\n",
    "x = \\sum_{k=1}^{p} s(B_{k}^{v}), \\quad z = \\sum_{k=1}^{p} \\sum_{S: v\\in S} s(R_k^S) + \\sum_{k=1}^{p} s(G_k^v).\\tag{12}\n",
    "$$\n",
    "\n",
    "我们需要在测量完成后对这些副产品进行纠正，最后获得的量子态将为我们预期的 $|\\gamma,\\beta\\rangle$。为了方便使用，我们在 `qaoa` 中定义了 `byproduct_power` 用于求解副产品纠正的指数。我们只需要输入待纠正的副产品项，待纠正的比特位置，MB-QAOA 图，测量结果的字典，以及电路深度，即可计算出对应纠正项的指数：\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import byproduct_power\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码实现\n",
    "\n",
    "下面我们用 MBQC 模块，完整地实现上述 MB-QAOA 算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 量子态的演化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 引入模拟相关的模块\n",
    "from paddle_quantum.mbqc.simulator import MBQC\n",
    "from paddle_quantum.mbqc.utils import pauli_gate, kron, basis, permute_systems\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import preprocess, adaptive_angle, byproduct_power"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义 MBQC 模型下的 QAOA 函数\n",
    "def mbqc_qaoa(poly_x, depth, gamma, beta):\n",
    "    \n",
    "    # 对目标多项式函数进行预处理，获得变量替换后的多项式 C(z) 和 MB-QAOA 图\n",
    "    poly_classified, qaoa_graph = preprocess(poly_x, depth)\n",
    "    var_num, cons_item, linear_items, non_linear_items = poly_classified\n",
    "\n",
    "    # 实例化一个 MBQC 模型并设置图\n",
    "    mbqc = MBQC()\n",
    "    mbqc.set_graph(graph=qaoa_graph)\n",
    "\n",
    "    # 测量每一个节点\n",
    "    for i in range(1, depth + 1):\n",
    "        \n",
    "        # 测量红色节点\n",
    "        for item in non_linear_items:\n",
    "            angle_r = adaptive_angle(which_qubit=('R', item[0], i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=gamma[i - 1],\n",
    "                                     eta=to_tensor(item[1], dtype='float64')\n",
    "                                     )\n",
    "            mbqc.measure(which_qubit=('R', item[0], i), basis_list=basis('YZ', angle_r))\n",
    "\n",
    "        # 测量绿色节点\n",
    "        for v in range(1, var_num + 1):\n",
    "            angle_g = adaptive_angle(which_qubit=('G', v, i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=gamma[i - 1],\n",
    "                                     eta=linear_items[v])\n",
    "            mbqc.measure(which_qubit=('G', v, i), basis_list=basis('XY', angle_g))\n",
    "\n",
    "        # 测量蓝色节点\n",
    "        for v in range(1, var_num + 1):\n",
    "            angle_b = adaptive_angle(which_qubit=('B', v, i),\n",
    "                                     graph=mbqc.get_graph(),\n",
    "                                     outcome=mbqc.get_classical_output(),\n",
    "                                     theta=beta[i - 1],\n",
    "                                     eta=to_tensor([1], dtype='float64'))\n",
    "            mbqc.measure(which_qubit=('B', v, i), basis_list=basis('XY', angle_b))\n",
    "\n",
    "    # 纠正副产品\n",
    "    for v in range(1, var_num + 1):\n",
    "        pow_x = byproduct_power(gate='X', v=v, graph=mbqc.get_graph(), outcome=mbqc.get_classical_output(), depth=depth)\n",
    "        pow_z = byproduct_power(gate='Z', v=v, graph=mbqc.get_graph(), outcome=mbqc.get_classical_output(), depth=depth)\n",
    "        mbqc.correct_byproduct(gate='X', which_qubit=('H', v, depth), power=pow_x)\n",
    "        mbqc.correct_byproduct(gate='Z', which_qubit=('H', v, depth), power=pow_z)\n",
    "        \n",
    "    output_label = [('H', i, depth) for i in range(1, var_num + 1)]\n",
    "\n",
    "    # 对输出量子态进行系统顺序调整并返回\n",
    "    state_out = permute_systems(mbqc.get_quantum_output(), output_label)\n",
    "    \n",
    "    return state_out.vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MB-QAOA 优化网络的搭建\n",
    "\n",
    "优化网络搭建的流程与量桨上大部分机器学习的教程类似，唯一不同的是这里需要使用 `mbqc_qaoa` 函数作为前向传播函数。当算法完成后，我们会得到演化后的量子态，计算系统哈密顿量 $H_{C}$ 在该量子态下的期望值，将其作为损失函数接入飞桨优化器，对测量角度参数 $\\gamma_1, ... \\gamma_p, \\beta_1, ... \\beta_p$ 进行训练优化，最终得到优化后的参数。\n",
    "\n",
    "在 `qaoa` 中，我们定义了期望函数 `expecval`，用来计算系统哈密顿量 $H_C$ 在演化后的量子态 $|\\gamma,\\beta\\rangle$ 下的期望值 $\\langle \\gamma,\\beta| H_C| \\gamma,\\beta\\rangle$。\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import expecval\n",
    "```\n",
    "\n",
    "MB-QAOA 优化网络搭建的代码实现如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 引入飞桨优化器模块\n",
    "from paddle import nn\n",
    "# 引入期望函数\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import expecval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义 MB-QAOA 优化网络\n",
    "class MB_QAOA_Net(nn.Layer):\n",
    "\n",
    "    def __init__(self, depth, dtype=\"float64\"):\n",
    "        \n",
    "        super(MBQC_QAOA_Net, self).__init__()\n",
    "        \n",
    "        self.depth = depth\n",
    "        \n",
    "        # 定义训练参数\n",
    "        self.gamma = self.create_parameter(shape=[self.depth],\n",
    "                                           default_initializer=nn.initializer.Uniform(low=0.0, high=2 * pi),\n",
    "                                           dtype=dtype,\n",
    "                                           is_bias=False)\n",
    "        self.beta = self.create_parameter(shape=[self.depth],\n",
    "                                          default_initializer=nn.initializer.Uniform(low=0.0, high=2 * pi),\n",
    "                                          dtype=dtype,\n",
    "                                          is_bias=False)\n",
    "        \n",
    "    # 定义优化网络的前向传播机制，输入为目标多项式函数\n",
    "    def forward(self, poly):\n",
    "        \n",
    "        # 执行 MB-QAOA 算法并返回演化后的量子态\n",
    "        vector_out = mbqc_qaoa(poly, self.depth, self.gamma, self.beta)\n",
    "        \n",
    "        # 获取系统哈密顿量\n",
    "        HC = get_cost_hamiltonian(poly)\n",
    "        \n",
    "        # 计算系统哈密顿量在演化后量子态下的期望，作为损失函数\n",
    "        loss = - expecval(vector_out, HC)\n",
    "        \n",
    "        # 返回损失函数和量子态\n",
    "        return loss, vector_out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 答案解码\n",
    "\n",
    "运行完 MB-QAOA 优化网络后，我们得到最优的参数 $\\gamma^*,\\beta^*$，以及对应的输出态 $|\\gamma^*,\\beta^*\\rangle$，但是我们还需要从输出态中获取 PUBO 问题的最终解，所以我们需要对量子态 $|\\gamma^*,\\beta^*\\rangle$ 重复测量多次后，统计对应结果的概率分布，并将最大概率对应的比特串作为原问题的最优解。在 `qaoa` 中我们定义了 `get_solution_string` 函数，用来解码量子答案，在具体的例子当中，我们可以根据自己的需要使用。\n",
    "\n",
    "```python\n",
    "from paddle_quantum.mbqc.QAOA.qaoa import get_solution_string\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 示例\n",
    "\n",
    "在介绍完上述基于测量的量子近似优化算法之后，我们将该算法应用到两个具体的问题当中。在这两个例子中，我们可以直接调用 `qaoa` 中的 `MB_QAOA_Net` 运行 MB-QAOA 及参数的优化过程，具体示例请参见：\n",
    "\n",
    "- [MBQC 模型下求解多项式组合优化问题](PUBO_CN.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## 参考文献\n",
    "\n",
    "[1] Farhi, Edward, et al. \"A quantum approximate optimization algorithm.\" [arXiv preprint arXiv:1411.4028 (2014).](https://arxiv.org/abs/1411.4028)\n",
    "\n",
    "[2] Farhi, Edward, et al. \"Quantum computation by adiabatic evolution.\" [arXiv preprint quant-ph/0001106 (2000).](https://arxiv.org/abs/quant-ph/0001106)\n",
    "\n",
    "[3] Duan, Runyao. \"Quantum adiabatic theorem revisited.\" [arXiv preprint arXiv:2003.03063 (2020).](https://arxiv.org/abs/2003.03063)\n",
    "\n",
    "[4] Ferguson, R. R., et al. \"Measurement-based variational quantum eigensolver.\" [Physical Review Letters 126.22 (2021): 220501-220501.](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.126.220501)\n",
    "\n",
    "[5] Browne, Dan, and Hans Briegel. \"One-way quantum computation.\" [Quantum Information: From Foundations to Quantum Technology Applications (2016): 449-473.](https://onlinelibrary.wiley.com/doi/abs/10.1002/9783527805785.ch21)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}