量子近似优化算法(一)

小贴士:百度量子 (量脉项目) 招聘实习生和工程师啦,点击了解详情 >>

Quantum Approximate Optimization Algorithm (QAOA) 即量子近似优化算法,是一种经典和量子的混合算法,用于解决组合优化问题,最为典型的案例即为最大切割 (MaxCut) 问题。在这篇学习汇报中,将主要介绍使用QAOA解决MaxCut 问题的基本策略。

参考文献

[1] Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.

[2] https://learn-quantum.com/EDU/originQuantumBook.html

[3] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106.

[4] 段乾恒.绝热量子计算理论研究[D].湖南:国防科学技术大学,2014. DOI:10.7666/d.D01107876.

MaxCut 问题

首先了解一下 MaxCut 问题,它非常便于描述。考虑如下的一个又节点和连线组成的系统,我们需要把所有点分成两部分,检查这两部分之间连线的个数,而目标是找到连线个数最多的分组方案。

这是一种典型的组合问题,最简单的方法则是枚举法,这也是唯一一种能找到全局最优解(无近似)的方法,但这种方法的复杂度较高,特别对于顶点个数N较大的情况,由于MaxCut仅将顶点分为两组,因此总共有 2^N 种分法,显然这是一个 NP-Hard 问题。

MaxCut 问题的量子描述

对于这样的高复杂度的问题,经典的算法显得有点力不从心,因而我们使用量子算法即QAOA进行优化。我们首先需要考虑的问题,就是如何将这样的问题使用量子计算的语言进行描述。恰好,使用二能级系统构造的量子体系(qubit)就可以很好地表达这个问题。

一个量子比特,其两种基态分别为 |0\rangle, |1\rangle,正好可以用来表示两种分组情况:|0\rangle 表示分到组0,|1\rangle 表示分到组1。因而多个量子比特就可以表示复杂系统的分组情况了。两个量子比特的情况如上图所示,四种切割方式中,只有 |01\rangle|10\rangle 有连接线被切割,因为A和B被分到了不同的组,并且之间有连接线。

我们来看一种更复杂的情况,即有四个点并以如下图的方式连接:

对于这样的链接,则有 2^4=16 种切割方式,如下图所示,

现在,我们找到了使用量子比特来表示各节点的分组的方法,但是,似乎我们一楼了一个问题:我们应该使用何种方法表示各节点的链接方式?答案是使用哈密顿量。以前面提到过最简单的情况为例:

我们现在需要的效果是:如果A和B分到同一组则返回0,如果在不同组则返回1。如果能构造出满足上述效果的哈密顿量,那实际上就指定了连线的方式。现在我们来一步步推导这个过程。首先,我们可以构造一个经典函数:

C_{ij}=\frac{1}{2}(1-Z_jZ_j)

这里解释一下,其中Z_iZ_j分别为A和B的泡利算符\sigma_i^z, \sigma_j^z的特征值,可分别取+1,-1。我们看出当A和B被分到同一组后,其乘积总为正,因此C=0,  而被分到不同组后,其乘积总为负, 因此C=1。则总的最大切割问题可以表达为求最大的:

MaxCut=\sum_{ij}C_{ij}

但是我们现在构造的只是一个经典函数,还不是哈密顿量,我们需要使用更进一步的推导来得到哈密顿量的方法。对于上面两节点的例子,共有四种切割方式:

|00\rangle=(1, 0, 0, 0)^T, E_{|00\rangle}=0

|01\rangle=(0, 1, 0, 0)^T, E_{|01\rangle}=1

|10\rangle=(0, 0, 1, 0)^T, E_{|10\rangle}=1

|11\rangle=(0, 0, 0, 1)^T, E_{|11\rangle}=0

其后面的E表示能量本征值,在这里即表示切割边数。因此其对应的哈密顿量可以用密度矩阵表示为H=\sum E_e |e\rangle\langle e|,即:

我们可以看出,对于这样一个两节点的系统的MaxCut问题,其实本质上就是一个问题异或操作:在同一组等于0,不在同一组等于1。

我们现在考虑使用泡利算符来表示异或操作。

首先我们来看看泡利算符与布尔变量的关系。对于一个泡利Z算符\sigma^z,它表示了一个二能级系统,这个系统可以处在两种能级态上,其本征态和本征值的表达式如下所示:

|0\rangle=(1, 0)^T, \alpha_{|0\rangle}=1

|1\rangle=(0, 1)^T, \alpha_{|1\rangle}=-1

如果我们定义|0\rangle为布尔值的真,而|1\rangle为布尔值的假,我们可以得到如下量子态与布尔变量的对应关系:

注意,\frac{I-\sigma^z}{2} =I-\frac{I+\sigma^z}{2}。介绍了这么多关于布尔变量与泡利算符的关系,我们来举个例子看看应该如何应用,我们这里就以逻辑与为例,使用量子态的语言就是如果节点A和B都为|0\rangle,则此时哈密顿量的能量本征值为1,否则都为0,则哈密顿量为

我们需要两个节点都为|0\rangle,用哈密顿量表示即为\frac{I+\sigma^z}{2},则两个粒子都为|0\rangle的情况即为H_{a\wedge b}=\frac{I+\sigma^z}{2} \otimes \frac{I+\sigma^z}{2},即等于上面的四阶矩阵。回到我们最初的问题,那就是异或,我们现在来考虑如何使用哈密顿量来表示异或操作。我们可以使用逻辑表达式来表示异或即a\oplus b=a \wedge (\neg b) + (\neg a) \wedge b,这写成哈密顿量的形式也非常简单:

H_{a\oplus  b}= \frac{I+\sigma_a^z}{2} \otimes  \frac{I-\sigma_b^z}{2} + \frac{I-\sigma_b^z}{2} \otimes  \frac{I+\sigma_a^z}{2}

即得到异或的矩阵:

我们之前已经分析了,对于一个简单的两粒子系统,其切割的操作等价于上面得到的这个哈密顿量,那么对于一个较为复杂的系统情况又是如何呢?其实是非常简单的,即很多个二粒子的哈密顿量相加即可:

H_{MaxCut}=H_1+H_2+\cdots+H_n=\sum_{ij}\frac{1}{2}(I-\sigma_i^z\sigma_j^z)

这里在一般的文献中更喜欢使用符号 \langle i,j \rangle 来表示一条边。这里还需要注意的是上述哈密顿量的含义,每一个两粒子哈密顿量表示这两个粒子在异或操作下的能量本征态和本征值,而 H_{MaxCut} 表示的所有两个粒子分组问题(即异或操作)的总和(整个系统)的能量本征值和本征态。因此我们可以看出,这个哈密顿量 H_{MaxCut} 实际上存储了一个连接图的结构

量子绝热算法(QAA)基本概念

我们先来看看传统的量子绝热定理表达了怎样的内容:

对于一个哈密顿量\hat{H}随时间t变化的量子系统,如果这个量子体系在t_i时刻处于\hat{H}(t_i)的第n个本征态上。而在系统演化过程中,演化速度足够缓慢,并且能级不发生交叉,则在演化结束时刻t_f,系统将相应地处于\hat{H}(t_i)的第n个本征态上,外加一个相位因子。

如何来理解这个定理呢?首先我们用一个演化算子\hat{U}(s,0)来表示系统演化:

|\psi(s)\rangle=\hat{U}_T(s)|\psi(0)\rangle

其中s=(t-t_i)/T, T=t_f-t_i,并且t表示当前时间, 因而s\in[0,1]是一个表示时间的归一化因子。

对于一个系统演化,若其开始时刻和结束时刻的哈密顿量固定,则演化时间T越长,其演化的速度就越慢,因而就约满足量子绝热定理,而当T趋于无穷大时,系统一定满足量子绝热定理,此时有:

\lim_{T\rightarrow\infty}\hat{U}_T(s)|E_n(0)\rangle=e^{i\alpha_n(s)}|E_n(s)\rangle

其中|E_n\rangle 表示的是第n个本征态,而对应的特征值是一个相位e^{i\alpha_n(s)},其中\alpha_n(s)为相位因子。这个公式说明了什么问题?也就是说在时刻s,演化算符\hat{U}_T(s)对初始哈密顿量\hat{H}(s)的第n个本征态|E_n(0)\rangle的操作的效果,是增加了一个相位,并依然对应了现在的哈密顿量\hat{H}(s)n个本征态。

那么这有什么意义呢?在量子计算上有什么作用?

对于一些不容易直接制备的基态的目标哈密顿量,我们可以先制备一个较为容易制备的初始哈密顿量,再通过控制参数,绝热地将初始哈密顿量调为目标哈密顿量。

举个例子,前面说的MaxCut问题,我们将这个问题的解编码在了哈密顿量H_{MaxCut} =\sum_{ij}\frac{1}{2}(I-\sigma_i^z\sigma_j^z)上。这个哈密顿量或许非常难以制备,因此我们需要通过制备一个简单的初始哈密顿量,然后通过绝热演化让这个初始哈密顿量不断地逼近H_{MaxCut}。这实际上也是一种分解的思路嘛,只是这是从时间上进行分解。考虑与时间相关的哈密顿量H(t)=(1-t/T)H_B+(t/T)H_C,其中H_B是方便制备的初始哈密顿量,而H_C是目标哈密顿量。这就是一个绝热演化过程,类似于线性插值

在后面的章节中我们来看看如何利用QAOA绝热量子算法来解决MaxCut问题。

量子近似优化算法(QAOA)

这里的内容,实质上是MaxCut的推广。

前面我们介绍了MaxCut问题,我们可以对其进行一些简单的抽象。简单来说一个量子基态例如 |0001\rangle  对应了一种分组的方法,即前三个粒子在组0,第四个粒子在组1。我们可以吧这个基态看成一个比特传0001,并且其对应了一个能量本征值,这里我们用C_{\alpha}(0001)表示,这样,问题就抽象成了字符串到能量的映射函数:

C(\mathbf{z}):\{+1, -1\}^N \mapsto \mathbb{R}_{\ge 0}

我们的目标就是要找到使得能量C_{\alpha}(\mathbf{z})最大的那一组\mathbf{z}。而这个问题本身是NP-hard问题,因为我们考虑使用量子算法来近似求解,“近似”意味着不一定能找到精确解,但是能找到一个r^*近似的解,即满足:

\frac{C(\mathbf{z})}{c_{max}} \ge r^*

其中,C_{max}=\max_{\mathbf{z}}C(\mathbf{z})表示真实的最优解。

前面我已经介绍过了如何使用哈密顿量来表示 MaxCut 问题,在这个抽象的模型中我们也需要使用哈密顿量吧这个映射C(\mathbf{z})用哈密顿量来表示,而MaxCut问题的哈密顿量我们已经在前面给出了,即H_{MaxCut} = \sum_{ij}\frac{1}{2}(I-\sigma_i^z\sigma_j^z),这里给出其一般形式:

H_C=C( \sigma_1^z,  \sigma_2^z, \cdots,  \sigma_N^z)

QAOA的过程到底是如何?

我们先不问为什么,总之过程很简单:

首先我们需要制备一个初态,即一个均匀分布的量子叠加态:

|s\rangle=|+\rangle^{\oplus N}=\frac{1}{\sqrt{2^n}}\sum_z|z\rangle

然后我们要在这个态上执行H_B=\sum_{j=1}^N\sigma_j^x和 $H_C$ 操作并得到量子|\psi_p(\vec{\gamma}, \vec{\beta})\rangle

这里一共执行了$p$ 次变换,区别在于这里的每次的参数不一样,分别为:

\vec{\gamma} = (\gamma_1, \gamma_2, \cdots, \gamma_p)^T

\vec{\beta} = (\beta_1 , \beta _2, \cdots, \beta_p)^T

随后,我们对量子态|\psi_p(\vec{\gamma}, \vec{\beta})\rangle进行测量,得到H_C|\psi_p(\vec{\gamma}, \vec{\beta})\rangle上的平均值:

F_p(\gamma, \beta)=\langle  \psi_p(\vec{\gamma}, \vec{\beta})  |H_C| \psi_p(\vec{\gamma}, \vec{\beta}) \rangle

这里我们仔细来看看这个平均值表达了什么含义。从基本的量子力学的只是可以看出,算符H_C在量子态|\varphi\rangle的平均值的定义是:

\langle H_C\rangle \equiv \langle\varphi|H_C| \varphi \rangle \equiv \sum_i|c_i|^2\lambda_i

即算符H_C的特征值的概率加权平均值,因此当本征值越大的本征态出现的概率越高时,则平均值\langle H_C\rangle越大。对应到我们的QAOA算法中的表述就是,能量本征值越高的那个本征态出现的概率越高时,则平均值越大;而如果当我们制备出的| \psi_p(\vec{\gamma}, \vec{\beta}) \rangle正好等于 能量本征值越高的那个本征态时,则平均值达到最大。

那QAOA算法整个过程的本质应当如何理解呢?

这个算法通过pe^{-i\gamma H_C}e^{-i\beta H_B}操作,将初始态|s\rangle制备为了一个能让\langle H_C \rangle尽可能最大化的量子态\vec{\gamma}, \vec{\beta}使得参数我们可以制备出这样的量子态|\psi_p(\vec{\gamma}, \vec{\beta}) \rangle,而关键在于找到参数\vec{\gamma}, \vec{\beta}使得参数我们可以制备出这样的量子态|\psi_p(\vec{\gamma}, \vec{\beta}) \rangle

(\vec{\gamma^*}, \vec{\beta^*}) \equiv \arg\max\limits_{\vec{\gamma},\vec{\beta}} F_p(\vec{\gamma},\vec{\beta})

其过程如下图所示:

现在我们对其思路也有了一定的了解,剩下的问题就是如何优化参数了。但是在学习参数优化之前,我们还有一个问题需要解决,那就是我们前面介绍了那么久的量子绝热算法QAA和QAOA到底有什么关系?

QAA和QAOA的关系

事实上,我们可以使用QAA来实现QAOA,还记得我们前面说的初始态|s\rangle吗?之前我们说这个初始态是一个均匀分布的叠加态,而若使用绝热量子算法,我们将|s\rangle设定为初始哈密顿量H_B能量本征值最高的本征态,而根据前面所说的绝热原理,经过足够长时间的演化,|s\rangle将演变为H_C的能量最高的本征态。而我们这里所说的足够长的时间,即指的p足够大。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
禁止转载,如需转载请通过简信或评论联系作者。
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 151,688评论 1 330
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 64,559评论 1 273
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 101,749评论 0 226
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 42,581评论 0 191
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 50,741评论 3 271
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 39,684评论 1 192
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 31,122评论 2 292
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 29,847评论 0 182
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 33,441评论 0 228
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 29,939评论 2 232
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 31,333评论 1 242
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 27,783评论 2 236
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 32,275评论 3 220
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 25,830评论 0 8
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 26,444评论 0 180
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 34,553评论 2 249
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 34,618评论 2 249

推荐阅读更多精彩内容

  • 光子晶体存储器,是基于量子光学理论,利用光学相干瞬态效应,制造具有特殊光学性质的超材料构造体即光子晶体,使用该构造...
    SchwarzMKII阅读 1,762评论 1 2
  • 有人在推特上讨论量子力学的平行宇宙诠释,以及讨论它和双缝实验的关系,并爱特了连围观都没围观单纯打酱油路过的我,所以...
    LostAbaddon阅读 3,376评论 31 72
  • “我对稳定没有兴趣。我知道的太清楚了,能养活我的,往往是我身上世故圆滑的东西,能让我招人喜欢的,却刚好是我的刻薄,...
    凉茶MY阅读 546评论 2 2
  • 【倒计时3 老友记第三届体重管理挑战赛招募 ️ 】 “老友记第三届体管赛”自12月15日开班,持续三个月,每周五晚...
    文艺气息的工程师阅读 160评论 0 0
  • 我因为身体原因,必须每月月底去协和医院开一次药。协和医院的号很不好挂。上个月底呢,就没有挂上。眼看着药没得用...
    朝霞满天_77阅读 436评论 6 16