# QAOA 演算法
QAOA(Quantum Approximate Optimization Algorithm)演算法是由 Farhi, Goldstone 與 Gutmann 開發的混合演算法

## 要解決什麼問題
QAOA 可以應用在許多問題上，其中比較經典的問題為 MaxCut 問題，所以我們會從 MaxCut 問題中切入 QAOA。

給定一張圖，這張圖（稱作 Graph, 簡寫 G）由邊（edge, E）與頂點（vertices, V）組成，比方說下圖為一個由五個頂點與六個邊組成的圖

接著我們要找到一條線穿過圖中的邊，將頂點分成兩個群

MaxCut 的目標是將一個圖$G = (V, E)$的頂點分割為兩個不同的集合，最大化被分割的邊的權重總和 $\text{MaxCut}(S)$ 。對於給定的圖 $G$，MaxCut 問題可以表示為以下優化問題：
( G 代表圖（graph）; V 代表頂點集合（vertices）; E 代表邊集合（edges）)

$$
\text{MaxCut}(S) = \sum_{(i,j) \in E} w_{ij} \cdot \frac{1 - s_i s_j}{2}
$$

其中：
- $s_i \in \{-1, 1\}$表示頂點$i$ 所屬的集合（即 $s_i$ = **-1**或 **1**）
- $w_{ij}$ 是連接頂點$i$ 和$j$的邊的權重

考慮邊 $(i,j)$，它連接頂點 $i$ 和$j$ 。兩個頂點的標記 $s_i \in \{-1, 1\}$ 可以用來判斷它們是否屬於不同的子集，可以用以下方式來表達：

$$
\frac{1 - s_i s_j}{2}
$$

- 當 $s_i = s_j$，即兩個頂點在同一個集合時，$1 - s_i s_j = 0$，這條邊不計入 MaxCut。
- 當 $s_i \neq s_j$，即兩個頂點在不同集合時，$1 - s_i s_j = 2$，這條邊應該被計入 MaxCut。

#### 舉例:
假設上圖中分割線左側的頂點$(1,2,4)$在同一個集合中，並且$s \in \{1\}$；分割線右側的頂點$(0,3)$在另一個集合中，並且$s \in \{-1\}$。
- 頂點1,2連起來的邊: $\frac{1 - s_1 s_2}{2}$= $\frac{1 - 1*1}{2} = 0$ 不列入MaxCut的計算
- 而頂點1,0連起來的邊: $\frac{1 - s_1 s_0}{2}$= $\frac{1 - 1*(-1)}{2} = 1$ 列入MaxCut的計算

圖形劃分的目標是使得權重和 $\text{MaxCut}(S)$ 最大化。

### QUBO Problems
QUBO（Quadratic Unconstrained Binary Optimization）是一種二次優化問題，它的變數都是二元變數（即 **0 或 1**），並且問題無約束條件。目標是最小化（或最大化）一個二次形式的目標函數。可以表示為以下二次優化形式的組合優化問題：

$$
\text{minimize} \quad x^T Q x + c^T x
$$

其中：

- $x$ 是一個由二元變量（0 或 1）組成的向量，$x \in {0,1}^n$。
- $Q$ 是一個對稱矩陣，表示二次項的係數，$Q \in \mathbb{R}^{n \times n}$。
- $c$ 是一次項的係數向量，$c \in \mathbb{R}^n$。
- T 轉置矩陣(請參考: )

舉例 :

假設我們有三個二元變數 $x_1, x_2, x_3 \in \{0,1\}$，並且我們的目標是最小化以下二次目標函數：

$$
f(x) = -2x_1 + 3x_2 + 4x_3 + 5x_1x_2 - 3x_1x_3 + 2x_2x_3
$$

#### 一般作法求解

對於這個 QUBO 問題，因為變量 $x_1, x_2, x_3 \in \{0,1\}$，我們可以通過列舉所有可能的二進制組合來求得目標函數的最小值。變量的可能組合有 $2^3 = 8$ 種，分別是：

<center>

| $x_1$ | $x_2$ | $x_3$ | $f(x)$ |
|-------|-------|-------|--------|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 4 |
| 0 | 1 | 0 | 3 |
| 0 | 1 | 1 | 9 |
| 1 | 0 | 0 | -2 |
| 1 | 0 | 1 | 2 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 14 |

</center>

從結果可以看出，當 $x_1 = 1, x_2 = 0, x_3 = 0$ 時，目標函數達最小值。因此，最佳解是 $x_1 = 1，x_2 = x_3 = 0$，最小值為 $f(x) = -2$。

#### 優化演算法求解
- $x$ 是一個由二元變量（0 或 1）組成的向量：
$$
x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}
$$

- $x^T$ 是 $x$ 的轉置向量：
$$
x^T = \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix}
$$

- $Q$ 是一個對稱矩陣，表示二次項的係數：
$$
Q = \begin{bmatrix}
0 & 2.5 & -1.5 \\
2.5 & 0 & 1 \\
-1.5 & 1 & 0
\end{bmatrix}
$$

- $c$ 是一次項的係數向量：
$$
c = \begin{bmatrix} -2 \\ 3 \\ 4 \end{bmatrix}
$$

- $c^T$ 是 $c$ 的轉置向量：
$$
c^T = \begin{bmatrix} -2 & 3 & 4 \end{bmatrix}
$$

#### 完整的目標函數表示

將所有元素代入，我們的 QUBO 形式目標函數可以寫成：

$$
f(x) = \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix} \begin{bmatrix}
0 & 2.5 & -1.5 \\
2.5 & 0 & 1 \\
-1.5 & 1 & 0
\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} + \begin{bmatrix} -2 & 3 & 4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}
$$

QUBO問題也可以用優化演算法來解決，以下介紹的QAOA即為一種可以用來解決QUBO問題的演算法。

### MaxCut to QUBO
MaxCut 問題的cost function可以表示為：

$$
\sum_{(i,j) \in E} w_{ij} \cdot \frac{1 - s_i s_j}{2}
$$

這可以進一步轉化為 QUBO 的形式:
$$\sum_{i,j=1}^{n} W_{ij} x_i (1 - x_j)$$
<center>
<img src="https://hackmd.io/_uploads/rkgu7ZqnR.png" alt="圖片描述" width="500">
</center>

- 值得注意的是，一般MaxCut問題的$s_i \in \{-1, 1\}$，而QUBO問題的$x \in \{0,1\}$，因此在將MaxCut轉換成QUBO時Cost Function從原本的$\sum_{(i,j) \in E} W_{ij} \cdot \frac{1 - s_i s_j}{2}$ 轉換成$\sum_{i,j=1}^{n} W_{ij} x_i (1 - x_j)$

### Classical Algorithms for MaxCut

MaxCut 問題是一個 **NP-hard 問題**，因此使用精確算法求解在大多數情況下是不可行的。

#### MaxCut經典算法的限制

- 透過簡單的轉換，MaxCut 等價於一般的 QUBO 問題
- 要達到比 $\alpha \sim 0.941$ 更好的近似比率是 NP-hard 的問題
- 根據 **獨特遊戲猜想** (Unique Games Conjecture)，最佳的經典近似比率為 $\alpha \sim 0.878$
- 此比率由 **Goemans-Williamson** 算法達成

## QAOA
### 簡介
- 由 Farhi、Goldstone 和 Gutmann 於 2014 年提出
- 混合量子-經典變分算法
- 尋找 QUBO 問題的近似解
- 可以被視為 VQE 的特殊情況
- 將優化問題的成本函數編碼為問題的哈密頓量 $H_C$
- 盡可能接近最佳解，而非尋找最佳解

### 電路
<center>
<img src="https://hackmd.io/_uploads/BJ87I8jhA.png" alt="圖片描述" width="500">
</center>

### step 1: 定義成本哈密頓量（Cost Hamiltonian）
我們首先將 QUBO 的目標函數轉換為一個對應的成本哈密頓量。這個哈密頓量 $H_C$ 是基於 QUBO 的二次形式構建的，它會告訴我們系統的能量狀態。具體來說，對於 QUBO 形式的問題：

<center>
<img src="https://hackmd.io/_uploads/Sye9IUj30.png" alt="圖片描述" width="400">
</center>

- **$R_Z$ 閘** 處理 QUBO 中的**一次項**（變數自身的影響）。
- **$R_{ZZ}$ 閘** 處理 QUBO 中的**二次項**（變數之間的交互項）。

$$
H_C = \sum_{i,j=1}^n \frac{1}{4} Q_{ij} Z_i Z_j - \sum_{i=1}^n \frac{1}{2} \left( c_i + \sum_{j=1}^n Q_{ij} \right) Z_i
$$

$$
時間演化算符e^{-i\gamma H_C} = \prod_{i,j=1}^n R_{Z_i Z_j} \left( \frac{1}{4} Q_{ij} \gamma \right) \prod_{i=1}^n R_{Z_i} \left( \frac{1}{2} \left( c_i + \sum_{j=1}^n Q_{ij} \right) \gamma \right)
$$

---

舉例:

假設我們有一個三變數的 QUBO 問題，目標函數為：

$$
f(x_1, x_2, x_3) = 2x_1 + 3x_2 + x_3 + 4x_1x_2 + 2x_1x_3 + x_2x_3
$$

在這個問題中：

- 一次項係數（變數自身的影響）為：
- $c_1 = 2$ ； $c_2 = 3$ ; $c_3 = 1$

- 二次項係數（變數之間的交互影響）為：
- $Q_{12} = 4$ （$x_1$ 和 $x_2$ 之間的交互影響）
- $Q_{13} = 2$ （$x_1$ 和 $x_3$ 之間的交互影響）
- $Q_{23} = 1$ （$x_2$ 和 $x_3$ 之間的交互影響）

我們將這個 QUBO 問題轉換成量子哈密頓量 $H_C$ 的形式。

### 1. 二次項的處理

哈密頓量的第一部分處理的是二次項，即變量之間的交互影響。對於這個三變量的問題，我們有以下的二次項：

$$
\sum_{i,j=1}^{n} \frac{1}{4} Q_{ij} Z_i Z_j
$$

計算如下：

- $Q_{12} Z_1 Z_2$：

$$
\frac{1}{4} \times 4 \times Z_1 Z_2 = Z_1 Z_2
$$

- $Q_{13} Z_1 Z_3$：

$$
\frac{1}{4} \times 2 \times Z_1 Z_3 = \frac{1}{2} Z_1 Z_3
$$

- $Q_{23} Z_2 Z_3$：

$$
\frac{1}{4} \times 1 \times Z_2 Z_3 = \frac{1}{4} Z_2 Z_3
$$

因此，二次項的哈密頓量部分為：

$$
Z_1 Z_2 + \frac{1}{2} Z_1 Z_3 + \frac{1}{4} Z_2 Z_3
$$

### 2. 一次項的處理

哈密頓量的第二部分處理的是一次項（變量自身的影響），具體公式為：

$$
\sum_{i=1}^{n} \frac{1}{2} \left( c_i + \sum_{j=1}^{n} Q_{ij} \right) Z_i
$$

這部分需要計算每個變量的權重以及它與其他變量的交互總和。

#### **計算 $x_1$ 的一次項**

$$
\frac{1}{2} \left( c_1 + Q_{12} + Q_{13} \right) Z_1 = - \frac{1}{2} \left( 2 + 4 + 2 \right) Z_1 = - 4 Z_1
$$

#### **計算 $x_2$ 的一次項**

$$
\frac{1}{2} \left( c_2 + Q_{12} + Q_{23} \right) Z_2 = - \frac{1}{2} \left( 3 + 4 + 1 \right) Z_2 = - 4 Z_2
$$

#### **計算 $x_3$ 的一次項**

$$
\frac{1}{2} \left( c_3 + Q_{13} + Q_{23} \right) Z_3 = - \frac{1}{2} \left( 1 + 2 + 1 \right) Z_3 = - 2 Z_3
$$

因此，這部分的一次項哈密頓量為：

$$
4 Z_1 - 4 Z_2 - 2 Z_3
$$

### 3. 整合哈密頓量

我們將二次項和一次項整合在一起，得到最終的哈密頓量：

$$
H_C = Z_1 Z_2 + \frac{1}{2} Z_1 Z_3 + \frac{1}{4} Z_2 Z_3 - 4 Z_1 - 4 Z_2 - 2 Z_3
$$

這就是我們從原始的 QUBO 問題轉換得到的量子哈密頓量。這個哈密頓量 $H_C$ 可以用在 QAOA 演算法的量子電路中，通過演化和優化找到這個 QUBO 問題的最優解。

### 4. 總結

- **二次項部分 $\sum_{i,j=1}^{n} \frac{1}{4} Q_{ij} Z_i Z_j$** 處理變量之間的交互影響。
- **一次項部分 $\sum_{i=1}^{n} \frac{1}{2} \left( c_i + \sum_{j=1}^{n} Q_{ij} \right) Z_i$** 處理每個變數自身的影響，同時考慮其與其他變數的交互影響。

這個哈密頓量反映了我們在 QUBO 問題中的所有變量及其交互。使用這個哈密頓量，量子系統可以根據它進行演化，最終找到一組解 $x_1, x_2, x_3$ 使得目標函數$f(x_1, x_2, x_3)$ 最小化。

---

### step 2：定義混合哈密頓量（Mixing Hamiltonian）
接下來，我們需要引入一個混合哈密頓量 $H_M$，它的作用是促使量子比特的狀態變化。通常，混合哈密頓量是 Pauli-X 算符：
<center>
<img src="https://hackmd.io/_uploads/S111DUihR.png" alt="圖片描述" width="200">
</center>

$$
H_M = \sum_{i=1}^n X_i
$$

$$
X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}
$$
混合哈密頓量 $H_M$ 引入隨機性，使得系統能夠探索更多可能的解空間。
$$
e^{-i \beta H_M} = \prod_{i=1}^n R_X(2\beta)
$$

### step 3：初始化量子態
$| s \rangle = H| 0 \rangle^{\otimes n} = | + \rangle^{\otimes n}$，其中 $| + \rangle$ 是 Pauli-X 基態。

### step 4：構建 QAOA 量子態
$$|\psi_p(\gamma, \beta)\rangle = \prod_{j=1}^{p} U_B(\beta_j) U_C(\gamma_j) | s \rangle$$ 其中：
$$
U_C(\gamma_j) = e^{-i\gamma_j H_C}, \quad U_M(\beta_j) = e^{-i\beta_j H_M}
$$生成Wave function
$$
|\psi_p(\vec{\gamma}, \vec{\beta})\rangle = e^{-i \beta_p H_M} e^{-i \gamma_p H_C} \cdots e^{-i \beta_1 H_M} e^{-i \gamma_1 H_C} |+\rangle^{\otimes N}
$$

其中參數 $\beta, \gamma$ 為可學習的，並將其視為一個 operator。QAOA 透過參數 $\gamma$ 和 $\beta$ 來控制哈密頓量的演化過程。QAOA 依次應用**成本哈密頓量**和**混合哈密頓量**：

首先對成本哈密頓量 $H_C$ 進行參數化時間演化：$e^{-i \gamma H_C}$

然後對混合哈密頓量 $H_M$ 進行參數化時間演化：$e^{-i \beta H_M}$

這樣的操作會在量子態上逐漸逼近最優解。此過程可重複多次，即層數 $p$，以提高優化的精度。

### step 5：通過經典優化器來最大化期望值：
定義$F$為$H_C$的期望值
$$ F_p(\gamma, \beta) = \langle \psi_p(\gamma, \beta) | H_C | \psi_p(\gamma, \beta) \rangle $$ 令β*,γ*為使F最大值的參數
$$(\vec{\gamma}^*, \vec{\beta}^*) = \arg \max_{\vec{\gamma}, \vec{\beta}} F_p(\vec{\gamma}, \vec{\beta})$$ 而衡量量近似程度的標準為

$$
r = \frac{F_p(\vec{\gamma}^*, \vec{\beta}^*)}{C_{\text{max}}}
$$ 其中 $C_{\text{max}}$ 則是最佳解

### step 6：反覆調整參數$\gamma$和$\beta$，直至收斂。
最後，通過測量量子態來獲取二進制解 $x$，並使用經典優化方法來調整參數 $\gamma$ 和 $\beta$，使得測量結果接近問題的最優解。

---

#### 數學補充:矩陣指數運算 (Matrix Exponentiation)

對於矩陣 \( M \)，矩陣指數 \( e^M \) 定義為幂級數：

$$
e^M = \sum_{k=0}^{\infty} \frac{1}{k!} M^k
$$

#### Pauli 矩陣 (Pauli matrices)

$$
X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad
Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad
Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}
$$

#### 指數矩陣與旋轉

$$
e^{-i \theta X} = R_X(2\theta) = \begin{pmatrix} \cos(\theta) & -i \sin(\theta) \\ -i \sin(\theta) & \cos(\theta) \end{pmatrix}
$$

$$
e^{-i \theta Y} = R_Y(2\theta) = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix}
$$

$$
e^{-i \theta Z} = R_Z(2\theta) = \begin{pmatrix} e^{-i\theta} & 0 \\ 0 & e^{i\theta} \end{pmatrix}
$$

---

### Reference:
1.The Qiskit Global Summer School 2021
2.Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv. https://arxiv.org/abs/1411.4028
3.Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024). A review on Quantum Approximate Optimization Algorithm and its variants. *Physics Reports, 1068, 1–66.* https://doi.org/10.1016/j.physrep.2024.03.002
4.https://medium.com/@chs.li.work/qaoa-quantum-approximate-optimization-algorithm-1cf6dabdd581