量子近似優(yōu)化算法（一）

小貼士：百度量子 (量脈項目) 招聘實習(xí)生和工程師啦暑脆，點擊了解詳情 >>

Quantum Approximate Optimization Algorithm (QAOA) 即量子近似優(yōu)化算法，是一種經(jīng)典和量子的混合算法，用于解決組合優(yōu)化問題，最為典型的案例即為最大切割 (MaxCut) 問題。在這篇學(xué)習(xí)匯報中痢士，將主要介紹使用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].湖南:國防科學(xué)技術(shù)大學(xué),2014. DOI:10.7666/d.D01107876.

MaxCut 問題

首先了解一下 MaxCut 問題蘸嘶，它非常便于描述良瞧。考慮如下的一個又節(jié)點和連線組成的系統(tǒng)训唱，我們需要把所有點分成兩部分，檢查這兩部分之間連線的個數(shù)挚冤，而目標(biāo)是找到連線個數(shù)最多的分組方案况增。

這是一種典型的組合問題，最簡單的方法則是枚舉法训挡，這也是唯一一種能找到全局最優(yōu)解（無近似）的方法澳骤，但這種方法的復(fù)雜度較高，特別對于頂點個數(shù) $N$ 較大的情況澜薄，由于MaxCut僅將頂點分為兩組为肮，因此總共有 $2^N$ 種分法，顯然這是一個 NP-Hard 問題肤京。

MaxCut 問題的量子描述

對于這樣的高復(fù)雜度的問題颊艳，經(jīng)典的算法顯得有點力不從心，因而我們使用量子算法即QAOA進行優(yōu)化忘分。我們首先需要考慮的問題棋枕，就是如何將這樣的問題使用量子計算的語言進行描述。恰好妒峦，使用二能級系統(tǒng)構(gòu)造的量子體系（qubit）就可以很好地表達這個問題重斑。

我們來看一種更復(fù)雜的情況，即有四個點并以如下圖的方式連接：

對于這樣的鏈接啊终，則有 $2^4=16$ 種切割方式镜豹，如下圖所示，

現(xiàn)在蓝牲，我們找到了使用量子比特來表示各節(jié)點的分組的方法趟脂，但是，似乎我們一樓了一個問題：我們應(yīng)該使用何種方法表示各節(jié)點的鏈接方式例衍？答案是使用哈密頓量昔期。以前面提到過最簡單的情況為例：

我們現(xiàn)在需要的效果是：如果A和B分到同一組則返回0，如果在不同組則返回1佛玄。如果能構(gòu)造出滿足上述效果的哈密頓量硼一，那實際上就指定了連線的方式。現(xiàn)在我們來一步步推導(dǎo)這個過程梦抢。首先般贼，我們可以構(gòu)造一個經(jīng)典函數(shù)：

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

這里解釋一下，其中 $Z_i$ 和 $Z_j$ 分別為A和B的泡利算符 $\sigma_i^z, \sigma_j^z$ 的特征值奥吩，可分別取 $+1,-1$ 哼蛆。我們看出當(dāng)A和B被分到同一組后，其乘積總為正霞赫，因此 $C=0$ ,? 而被分到不同組后腮介，其乘積總為負，因此 $C=1$ 端衰。則總的最大切割問題可以表達為求最大的：

$MaxCut=\sum_{ij}C_{ij}$

但是我們現(xiàn)在構(gòu)造的只是一個經(jīng)典函數(shù)叠洗，還不是哈密頓量，我們需要使用更進一步的推導(dǎo)來得到哈密頓量的方法靴迫。對于上面兩節(jié)點的例子惕味，共有四種切割方式：

$|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$ 表示能量本征值，在這里即表示切割邊數(shù)玉锌。因此其對應(yīng)的哈密頓量可以用密度矩陣表示為 $H=\sum E_e |e\rangle\langle e|$ 名挥，即：

我們可以看出，對于這樣一個兩節(jié)點的系統(tǒng)的MaxCut問題主守，其實本質(zhì)上就是一個問題異或操作：在同一組等于0禀倔，不在同一組等于1。

我們現(xiàn)在考慮使用泡利算符來表示異或操作参淫。

首先我們來看看泡利算符與布爾變量的關(guān)系救湖。對于一個泡利Z算符 $\sigma^z$ ，它表示了一個二能級系統(tǒng)涎才，這個系統(tǒng)可以處在兩種能級態(tài)上鞋既，其本征態(tài)和本征值的表達式如下所示：

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

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

如果我們定義 $|0\rangle$ 為布爾值的真力九，而 $|1\rangle$ 為布爾值的假，我們可以得到如下量子態(tài)與布爾變量的對應(yīng)關(guān)系：

注意邑闺， $\frac{I-\sigma^z}{2} =I-\frac{I+\sigma^z}{2}$ 跌前。介紹了這么多關(guān)于布爾變量與泡利算符的關(guān)系，我們來舉個例子看看應(yīng)該如何應(yīng)用陡舅，我們這里就以邏輯與為例抵乓，使用量子態(tài)的語言就是如果節(jié)點A和B都為 $|0\rangle$ ，則此時哈密頓量的能量本征值為1靶衍，否則都為0灾炭，則哈密頓量為

我們需要兩個節(jié)點都為 $|0\rangle$ ，用哈密頓量表示即為 $\frac{I+\sigma^z}{2}$ 颅眶，則兩個粒子都為 $|0\rangle$ 的情況即為 $H_{a\wedge b}=\frac{I+\sigma^z}{2} \otimes \frac{I+\sigma^z}{2}$ 蜈出，即等于上面的四階矩陣√涡铮回到我們最初的問題掏缎，那就是異或，我們現(xiàn)在來考慮如何使用哈密頓量來表示異或操作煤杀。我們可以使用邏輯表達式來表示異或即 $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}$

即得到異或的矩陣：

我們之前已經(jīng)分析了沪哺，對于一個簡單的兩粒子系統(tǒng)沈自，其切割的操作等價于上面得到的這個哈密頓量，那么對于一個較為復(fù)雜的系統(tǒng)情況又是如何呢辜妓？其實是非常簡單的枯途，即很多個二粒子的哈密頓量相加即可：

$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$ 來表示一條邊。這里還需要注意的是上述哈密頓量的含義籍滴，每一個兩粒子哈密頓量表示這兩個粒子在異或操作下的能量本征態(tài)和本征值酪夷，而 $H_{MaxCut}$ 表示的所有兩個粒子分組問題（即異或操作）的總和（整個系統(tǒng)）的能量本征值和本征態(tài)。因此我們可以看出孽惰，這個哈密頓量 $H_{MaxCut}$ 實際上存儲了一個連接圖的結(jié)構(gòu)晚岭。

量子絕熱算法(QAA)基本概念

我們先來看看傳統(tǒng)的量子絕熱定理表達了怎樣的內(nèi)容：

對于一個哈密頓量 $\hat{H}$ 隨時間 $t$ 變化的量子系統(tǒng)，如果這個量子體系在 $t_i$ 時刻處于 $\hat{H}(t_i)$ 的第 $n$ 個本征態(tài)上勋功。而在系統(tǒng)演化過程中坦报，演化速度足夠緩慢，并且能級不發(fā)生交叉狂鞋，則在演化結(jié)束時刻 $t_f$ 片择，系統(tǒng)將相應(yīng)地處于 $\hat{H}(t_i)$ 的第 $n$ 個本征態(tài)上，外加一個相位因子骚揍。

如何來理解這個定理呢字管？首先我們用一個演化算子 $\hat{U}(s,0)$ 來表示系統(tǒng)演化：

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

其中 $s=(t-t_i)/T, T=t_f-t_i$ ，并且 $t$ 表示當(dāng)前時間，因而 $s\in[0,1]$ 是一個表示時間的歸一化因子嘲叔。

對于一個系統(tǒng)演化亡呵，若其開始時刻和結(jié)束時刻的哈密頓量固定，則演化時間 $T$ 越長借跪，其演化的速度就越慢政己，因而就約滿足量子絕熱定理，而當(dāng) $T$ 趨于無窮大時掏愁，系統(tǒng)一定滿足量子絕熱定理歇由，此時有：

$\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$ 個本征態(tài)，而對應(yīng)的特征值是一個相位 $e^{i\alpha_n(s)}$ 果港，其中 $\alpha_n(s)$ 為相位因子沦泌。這個公式說明了什么問題？也就是說在時刻 $s$ 辛掠，演化算符 $\hat{U}_T(s)$ 對初始哈密頓量 $\hat{H}(s)$ 的第 $n$ 個本征態(tài) $|E_n(0)\rangle$ 的操作的效果谢谦，是增加了一個相位，并依然對應(yīng)了現(xiàn)在的哈密頓量 $\hat{H}(s)$ 第 $n$ 個本征態(tài)萝衩。

那么這有什么意義呢回挽？在量子計算上有什么作用？

對于一些不容易直接制備的基態(tài)的目標(biāo)哈密頓量猩谊，我們可以先制備一個較為容易制備的初始哈密頓量千劈，再通過控制參數(shù)，絕熱地將初始哈密頓量調(diào)為目標(biāo)哈密頓量牌捷。

舉個例子墙牌，前面說的MaxCut問題，我們將這個問題的解編碼在了哈密頓量 $H_{MaxCut} =\sum_{ij}\frac{1}{2}(I-\sigma_i^z\sigma_j^z)$ 上暗甥。這個哈密頓量或許非常難以制備喜滨，因此我們需要通過制備一個簡單的初始哈密頓量，然后通過絕熱演化讓這個初始哈密頓量不斷地逼近 $H_{MaxCut}$ 撤防。這實際上也是一種分解的思路嘛虽风，只是這是從時間上進行分解〖赐耄考慮與時間相關(guān)的哈密頓量 $H(t)=(1-t/T)H_B+(t/T)H_C$ 焰情，其中 $H_B$ 是方便制備的初始哈密頓量，而 $H_C$ 是目標(biāo)哈密頓量剥懒。這就是一個絕熱演化過程内舟，類似于線性插值。

在后面的章節(jié)中我們來看看如何利用QAOA絕熱量子算法來解決MaxCut問題初橘。

量子近似優(yōu)化算法(QAOA)

這里的內(nèi)容验游，實質(zhì)上是MaxCut的推廣充岛。

前面我們介紹了MaxCut問題，我們可以對其進行一些簡單的抽象耕蝉。簡單來說一個量子基態(tài)例如 $|0001\rangle$ ? 對應(yīng)了一種分組的方法崔梗，即前三個粒子在組0，第四個粒子在組1垒在。我們可以吧這個基態(tài)看成一個比特傳0001蒜魄，并且其對應(yīng)了一個能量本征值，這里我們用 $C_{\alpha}(0001)$ 表示场躯，這樣谈为，問題就抽象成了字符串到能量的映射函數(shù)：

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

我們的目標(biāo)就是要找到使得能量 $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})$ 表示真實的最優(yōu)解。

前面我已經(jīng)介紹過了如何使用哈密頓量來表示 MaxCut 問題儒搭，在這個抽象的模型中我們也需要使用哈密頓量吧這個映射 $C(\mathbf{z})$ 用哈密頓量來表示吠架，而MaxCut問題的哈密頓量我們已經(jīng)在前面給出了，即 $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的過程到底是如何诵肛？

我們先不問為什么，總之過程很簡單：

首先我們需要制備一個初態(tài)默穴，即一個均勻分布的量子疊加態(tài)：

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

然后我們要在這個態(tài)上執(zhí)行 $H_B=\sum_{j=1}^N\sigma_j^x$ 和 $H_C$ 操作并得到量子 $|\psi_p(\vec{\gamma}, \vec{\beta})\rangle$ ：

這里一共執(zhí)行了$p$ 次變換，區(qū)別在于這里的每次的參數(shù)不一樣褪秀，分別為：

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

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

隨后蓄诽，我們對量子態(tài) $|\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$

這里我們仔細來看看這個平均值表達了什么含義媒吗。從基本的量子力學(xué)的只是可以看出仑氛，算符 $H_C$ 在量子態(tài) $|\varphi\rangle$ 的平均值的定義是：

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

即算符 $H_C$ 的特征值的概率加權(quán)平均值，因此當(dāng)本征值越大的本征態(tài)出現(xiàn)的概率越高時闸英，則平均值 $\langle H_C\rangle$ 越大锯岖。對應(yīng)到我們的QAOA算法中的表述就是，能量本征值越高的那個本征態(tài)出現(xiàn)的概率越高時甫何，則平均值越大出吹；而如果當(dāng)我們制備出的 $| \psi_p(\vec{\gamma}, \vec{\beta}) \rangle$ 正好等于能量本征值越高的那個本征態(tài)時，則平均值達到最大辙喂。

那QAOA算法整個過程的本質(zhì)應(yīng)當(dāng)如何理解呢捶牢？

這個算法通過 $p$ 次 $e^{-i\gamma H_C}e^{-i\beta H_B}$ 操作鸠珠，將初始態(tài) $|s\rangle$ 制備為了一個能讓 $\langle H_C \rangle$ 盡可能最大化的量子態(tài) $\vec{\gamma}, \vec{\beta}$ 使得參數(shù)我們可以制備出這樣的量子態(tài) $|\psi_p(\vec{\gamma}, \vec{\beta}) \rangle$ ，而關(guān)鍵在于找到參數(shù) $\vec{\gamma}, \vec{\beta}$ 使得參數(shù)我們可以制備出這樣的量子態(tài) $|\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})$

其過程如下圖所示：

現(xiàn)在我們對其思路也有了一定的了解秋麸，剩下的問題就是如何優(yōu)化參數(shù)了渐排。但是在學(xué)習(xí)參數(shù)優(yōu)化之前，我們還有一個問題需要解決灸蟆，那就是我們前面介紹了那么久的量子絕熱算法QAA和QAOA到底有什么關(guān)系驯耻？

QAA和QAOA的關(guān)系

事實上，我們可以使用QAA來實現(xiàn)QAOA炒考，還記得我們前面說的初始態(tài) $|s\rangle$ 嗎可缚？之前我們說這個初始態(tài)是一個均勻分布的疊加態(tài)，而若使用絕熱量子算法票腰，我們將 $|s\rangle$ 設(shè)定為初始哈密頓量 $H_B$ 能量本征值最高的本征態(tài)城看，而根據(jù)前面所說的絕熱原理，經(jīng)過足夠長時間的演化杏慰， $|s\rangle$ 將演變?yōu)?img src="https://math.jianshu.com/math?formula=H_C" alt="H_C" mathimg="1">的能量最高的本征態(tài)测柠。而我們這里所說的足夠長的時間，即指的 $p$ 足夠大缘滥。

最后編輯于：2022.10.08 17:05:28

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

禁止轉(zhuǎn)載轰胁，如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者。

人面猴
序言：七十年代末朝扼，一起剝皮案震驚了整個濱河市赃阀，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌擎颖，老刑警劉巖榛斯，帶你破解...
沈念sama閱讀 212,454評論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異搂捧，居然都是意外死亡驮俗，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,553評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門允跑，熙熙樓的掌柜王于貴愁眉苦臉地迎上來王凑，“玉大人，你說我怎么就攤上這事聋丝∷髋耄” “怎么了？”我有些...
開封第一講書人閱讀 157,921評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵弱睦，是天一觀的道長百姓。經(jīng)常有香客問我，道長况木，這世上最難降的妖魔是什么瓣戚？我笑而不...
開封第一講書人閱讀 56,648評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任端圈，我火速辦了婚禮，結(jié)果婚禮上子库，老公的妹妹穿的比我還像新娘舱权。我一直安慰自己，他們只是感情好仑嗅，可當(dāng)我...
茶點故事閱讀 65,770評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布宴倍。她就那樣靜靜地躺著，像睡著了一般仓技。火紅的嫁衣襯著肌膚如雪鸵贬。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,950評論 1贊 291
城市分裂傳說
那天脖捻，我揣著相機與錄音阔逼，去河邊找鬼。笑死地沮，一個胖子當(dāng)著我的面吹牛嗜浮，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播摩疑，決...
沈念sama閱讀 39,090評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼危融，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了雷袋？” 一聲冷哼從身側(cè)響起吉殃，我...
開封第一講書人閱讀 37,817評論 0贊 268
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎楷怒，沒想到半個月后蛋勺，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,275評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡鸠删，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,592評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年迫卢，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片冶共。...
茶點故事閱讀 38,724評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖每界，靈堂內(nèi)的尸體忽然破棺而出捅僵，到底是詐尸還是另有隱情，我是刑警寧澤眨层，帶...
沈念sama閱讀 34,409評論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布庙楚，位于F島的核電站，受9級特大地震影響趴樱，放射性物質(zhì)發(fā)生泄漏馒闷。R本人自食惡果不足惜酪捡，卻給世界環(huán)境...
茶點故事閱讀 40,052評論 3贊 316
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望纳账。院中可真熱鬧逛薇，春花似錦、人聲如沸疏虫。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,815評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽卧秘。三九已至呢袱，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間翅敌，已是汗流浹背羞福。一陣腳步聲響...
開封第一講書人閱讀 32,043評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留蚯涮，地道東北人治专。一個月前我還...
沈念sama閱讀 46,503評論 2贊 361
代替公主和親
正文我出身青樓，卻偏偏與公主長得像恋昼，于是被迫代替她去往敵國和親看靠。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 43,627評論 2贊 350