QAOA 演算法 | EntangleTech 量子教育平台

## QAOA 演算法在前面我們介紹了 adiabatic 與 quantum annealer，然而 quantum annealer 只能在特定硬體像是 D-Wave 的機器上執行，如果今天你有已經寫成 QUBO 的問題，但你只有像是 IBM 的 gate-based 量子電腦，我們能用這台電腦解 QUBO 問題嗎？當然可以，就如同前面提及的，adiabatic 與 gate-based 是等價的，前者就像是連續化，後者是離散化，因此我們只要把 adiabatic 的式子離散化，就會變成 gate 版本的 adiabatic，稱作 Quantum Approximate Optimization Algorithm (QAOA)。 ## 離散化 Adiabatic 這邊的離散化是指將能量值從 $0$ 到 $T$ 的變化變成一個一個微小時間 $\Delta t$ 變化的組合，類似於微積分裡極限的概念，或是你也可以這樣想，將一個單位圓旋轉 180 度，可以把它離散化成每次旋轉 1 度，旋轉 180 次，這種離散化我們稱作 “trotterization”。在量子力學中，我們知道當時間間隔 $\Delta t$ 非常非常小時，能量的變化為： \begin{align} e^{iH\Delta t }=e^{i\Delta t \bigg[A(t_m)H_0+B(t_m)H_1\bigg] } \end{align} 如果我們今天把時間從 $t=0$ 到 $T$ 分割成 $m$ 個部分，那上式裡的 $t_m=m\frac{\Delta t}{T}$，所以完整的變化可以寫成： \begin{align}\tag{1} H(t)|\psi_0\rangle=\bigg\{\prod_{m=0}^{p=\frac{T}{\Delta T}}e^{i\Delta t \bigg[A(t_m)H_0+B(t_m)H_1\bigg] }\bigg\} |\psi_0\rangle \end{align} 其中 $\prod$ 是相乘（如同 $\sum$ 的概念，相加），如果今天 $\Delta t$ 夠小，也就是說切得更細，理應上式等號會成立（或起碼近似於），為了能繼續下面的推演，我們得引入一個數學近似，稱作 Lie-Trotter formula，有興趣的讀者可以去深入查詢，這邊就不做推演： \begin{align} e^{i\Delta t \bigg[A(t_m)H_0+B(t_m)H_1\bigg] } \approx e^{i\Delta t A(t_m)H_0} e^{i\Delta t B(t_m)H_1} \end{align} 就類似 $e^{a+b}=e^a e^b$，因此（1）式可以近似成： \begin{align}\tag{2} \prod_{m=0}^{p=\frac{T}{\Delta T}}e^{i\Delta t A(t_m)H_0} e^{i\Delta t B(t_m)H_1} |\psi_0\rangle \end{align} ## QAOA 演算法為了方便書寫，接著我們把 $\Delta tA(t_m)$ 簡寫成 $\alpha$．$\Delta tB(t_m)$ 簡寫成 $\beta$，所以（2）式展開起來長這副德性： \begin{align}\tag{3} e^{i\alpha_p H_0} e^{i\beta_p H_1}\cdots e^{i\alpha_2 H_0} e^{i\beta_2 H_1}e^{i\alpha_1 H_0} e^{i\beta_1 H_1}|\psi_0\rangle \end{align} 在 quantum annealer 中，$A(t)$ 與 $B(t)$ 的設定取決於我們對硬體的參數設定，設定要怎麼做退火，然而在 gate-based 裡我們可以將 $\alpha$ 和 $\beta$ 當作一種如同機器學習或深度學習在訓練的「參數」，所以 QAOA 如同機器學習一樣，要找到一個適合的參數組合 $[\alpha, \beta]$，使得 $H$ 的期望值（這時候又稱作 "cost"）是最低，如同下圖：

QAOA 流程圖。左邊那一大塊就是 QAOA 的量子電路，詳情後文會解釋，測量電路後得到的量子態與當下的參數（對，我故意把 gamma 改成 beta，beta 改成 alpha）傳給右邊的古典電腦，計算期望值與梯度，根據梯度提供新的參數到量子電路中，如此循環

Picture comes from 10.48550/arXiv.2306.16701

如上圖所示，經典電腦先猜一個初始參數 $[\alpha, \beta]$ 給量子電腦，經過量子電路後測量得到量子態，將這組參數與測量得到的量子態給經典電腦計算期望值，以及計算[梯度](https://www.entangletech.tw/lesson/qml-04)，接著也是透過經典電腦（正確來說是 optimizer 優化器，像是著名的 SGD, ADAM 等等，機器學習也常用）給出下一個參數給量子電腦，如此循環直到期望值不再改變（我們稱作收斂），可以看出 QAOA 演算法結合經典電腦與量子電腦．因此它是一種 hybrid classical-quantum algorithm。 ## QAOA 演算法的電路現在，我們來看 QAOA 的電路圖長什麼樣子，也就是上圖左邊綠色和藍色方塊。

這部分有一點點難度，如果第一次看不懂不用灰心，就記得結果就好，然後跳到期望值的部分

我們先從（2）式中的第一個指數開始，我們在前一節知道 $H_0=-\sum_{i=0}^{N-1} X_i$，因此： \begin{align} e^{i\alpha_k H_0}=e^{-i\alpha_k \sum_{i=0}^{N-1} X_i}=\prod_{i=0}^{N-1}e^{-i\alpha_k X_i} \end{align} 如果你把 $\alpha$ 看成角度 $\theta$，上述就如同我們在[基礎量子計算](https://www.entangletech.tw/lesson/basic-algorithm-10)中提到的 $R_X$ gate： \begin{align} R_X(\theta)=e^{-i\frac{\theta}{2} X} \end{align} 因此 $e^{-i\alpha_k X_i}$ 就是 $R_X(2\alpha_k)$ gate：

接著我們看第二項，同理： \begin{align} e^{i\beta_k H_1}&=e^{-i\beta_k(\sum_i h_i z_i + \sum_{ij} J_{ij}z_iz_j)} \\ &=\prod_{i}e^{-i\beta_k h_iz_i} \prod_{i,j} e^{-i\beta_k J_{ij}z_iz_j} \tag{4} \end{align} （4）式中的第一項．如同 $H_0$ 的情況，對應到 $R_Z(2\beta_k)$：

接著看（4）式中第二項 $e^{-i\beta_k J_{ij}z_iz_j}$，為方便書寫，我們暫且把 $\beta_k J_{ij}$ 寫作 $c$。如果今天 qubit $i$ 與 qubit $j$ 的資訊一樣，$Z_i$ 與 $Z_j$ 都是 $+1$ 或 $-1$（看不懂這段敘述的話可以回去複習[第二篇文章](https://www.entangletech.tw/lesson/optim-02)），相乘起來都是 $+1$，因此： \begin{align} e^{-ic Z_iZ_j} |x\rangle=e^{-ic}|x\rangle \end{align} 反之．如果不一樣，$Z_iZ_j=-1$： \begin{align} e^{-ic Z_iZ_j} |x\rangle=e^{+ic}|x\rangle \end{align} 這在說明如果兩個 qubits 狀態相同，就給一個相位 $e^{-ic}$，狀態不同就給相位 $e^{ic}$，在你學過的 qubit 中可以只調整相位不動量子態的就是 $RZ$ gate，這動作相當於下面這的電路：

如果看不太懂，可以每個 qubit 代 0 或 1 進去看看。如果今天你要求解的問題寫成 Ising model 是 $3Z_0Z_2-Z_1Z_2+2Z_0$，當 $p=1$ 時，其電路圖如下：

QAOA 電路（層數 p = 1）

$2Z_0$ 對應到圖中的 $RZ(4\beta_1)$，相當於（4）式中的第一項；$-Z_1Z_2$ 對應到連接 qubit 1 和 2的 CNOT 與 $RZ(-2\beta_1)$，相當於（4）式中的第二項，$3Z_0Z_2$ 對應到連接 qubit 0 和 2的 CNOT 與 $RZ(6\beta_1)$，最後的 $RX$ 對應到（2）式中的第一項。當今天 $p$ 不只 $1$ 層時，就會像（3）式那樣，我們將含有 $\alpha$ 的項取名叫 mixer Hamiltonian, $H_M$，含有 $\beta$ 的項取名叫 cost Hamiltonian, $H_C$，畫出來就長這樣：

多層數 QAOA 電路

## 計算期望值與優化經過這一串 quantum gate 後並做測量，測量的結果是 qubits 的量子態，但這不是我們所關心的，我們關心的是 $H$ 是多少數字，所以最後我們要的結果是 $H$ 的期望值 $\langle \psi|H|\psi\rangle$，這部分可以輕易地用古典電腦做計算。以前面舉個例子來看，假設在某個 $\alpha$ 與 $\beta$ 參數下，量子電路輸出的量子態為 $|101\rangle$，那其期望值為： \begin{align} \langle 101|H|101\rangle&=3\langle101|Z_0Z_2|101\rangle-\langle101|Z_1Z_2|101\rangle+2\langle 101|Z_0|101\rangle \\ &= 3+1-2\\ &=4 \end{align} 再透過這期望值與當下的參數計算梯度，傳給 optimizer 提供下一個參數，直到收斂。

這就是一個 QAOA 優化的軌跡與 landscape 圖，背景是某個 graph 在不同參數組合下的 cost，黑色叉叉連起來的線就是 QAOA-ADAM 不斷循環，逐步找到最低點的軌跡（紅色虛線與橘色線別在意，那是作者在做的研究內容）

現在，我們把剛剛說的變得更數學一點，經過 QAOA 電路輸出的量子態，記做： \begin{align} |\psi\rangle = \sum_n c_n |x\rangle \end{align} $|x\rangle$ 是 $|0\rangle$ 或是 $|1\rangle$，上式必須滿足 $\sum_n |c_n|^2=1$，這個讀者應該很熟悉了，那期望值會是： \begin{align} \langle \psi|H|\psi\rangle &= \bigg(\sum_y c_y^*\langle y|\bigg) H \bigg(\sum_y c_x |x\rangle\bigg) \\ &= \sum_y \sum_x c_y^* c_x \langle y|H|x\rangle \\ \end{align} 為了做出區別，上式把 $c_n$ 改成 $c_x$ 與 $c_y$。在第二行，因為今天不管是圖論還是 QAOA 問題都相對單純，$H$ 會是[對角化](https://www.entangletech.tw/lesson/math-08#toc-4)的矩陣，又因為 [eigenvector 與 eigenstate](https://www.entangletech.tw/lesson/math-08)，$H|x\rangle=E|x\rangle$ 且 eigenstate 互相正交，$E$ 是一個數字，如果這時 $y\neq x$，那 $\langle y|H|x\rangle=\langle y|E|x\rangle=E\langle y|x\rangle=0$，因此上式最後會等於： \begin{align} =\sum_x |c_x|^2 \langle x|H|x\rangle \end{align} 這個就是完整期望值的算法，其中後面那項 $\langle x|H|x\rangle$ 可以輕易地透過經典電腦計算，而前面這項 $|c_x|^2$ 就是透過量子電腦多次測量後統計出來每個量子態下出現的機率，即： \begin{align} |c_x|^2\sim\frac{m_x}{M} \end{align} $M$ 是同一個電路總共執行（或說測量）了幾次（shots），$m_x$ 是其中 $x$ 出現的次數，相除就是（近似於）$x$ 出現的機率。 ## 延伸閱讀再下一章，我們為把 QAOA 這種特定的演算法更 general 化，就是知名的 VQE 演算法，其實 QAOA 就是 VQE 的一種特別形式，本質上都是 VQE。 - [透過 pennylane 實作 QAOA](https://pennylane.ai/qml/demos/tutorial_qaoa_intro)