{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 基于测量的量子近似优化算法\n", "\n", " Copyright (c) 2021 Institute for Quantum Computing, Baidu Inc. All Rights Reserved. " ] }, { "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", "