---
tags: 大專生研究計畫, quantum
---
# Quantum Approximation Optimization Algorithm 初始化方法之研究

## (一) 摘要

Quantum Approximation Optimization Algorithm (QAOA) 是最有潛力展現量子優越性的演算法之一，然而要展現 QAOA 的效果，需要適當的初始化。

本計畫將主要分成以下兩點進行研究：

1. 探討、分析現有與自創的初始化方式如何影響 QAOA 的效果。
2. 透過 qiskit 實作，整理出因應不同狀況與需求的適當初始化方式，以此來最佳化 QAOA 結果。

最後，我們期望能用適當的初始化方式來處理maximum cut問題，並與傳統的計算方法做比較，分析QAOA的優勢與劣勢。

## (二) 研究動機與研究問題

QAOA 源自量子退火，透過量子電腦並利用傳統電腦的機器學習，能獲得組合問題的近似最佳解。 QAOA 是其中一種可以在現有量子電腦上實踐，並且被認為是現有演算法中最有潛力展示量子電腦優越性的量子演算法。$_{[1]}$ 然而若沒有進行適當的初始化，QAOA 近似的效果有限。

近年來許多文獻探討了 QAOA 如何應用在 maximum cut 問題上，並提出了許多初始化的方法，然而尚沒有人對這些初始化方法進行整理與比較。我們想比較並結合現有的初始化方法，提出新初始化的方法，並且透過 qiskit 的實作與數學方面的知識，找出最有效率的組合。

## (三) 文獻回顧與探討

### QAOA 與 maximum cut (max-cut) 問題

如圖，若我們將圖上的點以黑、白劃分成兩組，那麼連接黑、白兩點的邊數量（紅線部分）即是 5。

圖源：[維基百科](https://commons.wikimedia.org/wiki/File:Max-cut.svg)

Max-cut 問題及是給出如這樣的平面圖，找出一種將所有頂點分成兩組的方法，使得連接兩組的邊數量是最大值。Max-cut問題也有一種變形，即是賦予每邊不同的權重，而要求的最大值成為連接兩組的編之權重總和。在研究 QAOA 時，我們通常使用基礎的 Max-cut 問題做研究，相當於每邊權重為一。

NP 問題是指給出一個解，能在多項式時間內確認的問題，而 P 問題則是在多項式內時間內能找到解的問題。在傳統演算法上，Max-cut 是 NP 完全的問題，若能解出 max-cut 問題即可有效率的解出其他 NP 問題，且依照現有知識，傳統電腦想求解 Max-cut 問題是困難的。Max-cut 問題亦屬於 APX-hard 問題，也就是除非能證明所有 NP 都是 P 問題，我們也無法找到一種在多項式時間內可以達成的傳統近似方法。$_{[2]}$

重新審視 QAOA 時，不難發現 QAOA 的本質就是一種絕熱演化的過程。應用在 max-cut 問題時，我們將 max-cut 問題編碼成哈密頓量 $H$，而索求答案就是哈密頓量的基態 $|\phi>$，並且試圖從一個 $H_0=H^{\otimes n}$ 的哈密頓量逐漸演化成我們要的哈密頓量 $H$，同時 $H_0$ 的基態也逐漸演化成 $|\phi>$ 。 $_{[3]}$

顯然的，我們可以將 QAOA 從 max-cut 問題上推廣。也就是只要該問題得以 encode 成哈密頓量，我們就能透過 QAOA 將問題解出。

### QAOA 的優勢

已有文獻證明，若達到 420~500 位元，傳統演算法要模擬 QAOA 需要一個世紀$_{[6]}$，因此 QAOA 有潛力成為展示量子優越性的一項演算法。而即使深度 1 的 QAOA 演算法即可做出一定的預測$_{[3]}$，要做出準確的預測需要更大的深度$_{[4]}$，而更大的深度代表更複雜的函數，因此需要適當的初始化來得到更準確的結果。$_{[5]}$

### 現有初始化方法

目前常用的 QAOA 初始化方法分為兩種：傳統電腦已使用過的初始化方式，以及專為量子電腦特別設計的初始化方式。以下我們就針對這些初始化方式做一個簡單的介紹：

#### 傳統電腦的初始化方式

1. **隨機初始化。**
這是實作上最常使用的初始化方式之一。在深度較低的狀況下，隨機初始化具有找到全域最佳值的能力$_{[7]}$，然而隨著深度 p 增加，隨機初始化能做出的預測有限。$_{[8]}$
2. **使用 p 深度的結果作為 p+1 深度的初始化。**
隨著p增加，隨機初始化所需次數的中位數隨著 p 指數級增長，才能達到此方法的預測效果。$_{[7]}$
3. **使用相似圖形的結果。$_{[9]}$**
此方法是先找到過去做過的相似圖形，重複過去使用 QAOA 結果得到的參數來當作初始化參數。
$%$
重複使用參數與隨機初始化的比較 $_{[9]}$：

4. **使用 Relaxed problem 的結果**
將問題去除一些條件後執行 QAOA，接著以執行過後的結果。在電路深度低的狀況下，這種方法可以提供良好的預測。$_{[10]}$

#### 專為 QAOA 特別設計的初始化方法

1. **使用機器學習**
使用不同機器學習方法去對 QAOA 結果進行預測，研究顯示此方法可能可以減少執行時間$_{[11]}$，或者提升預測功效$_{[12]}$。
2. **Trotterized Quantum Annelaing (TQA) 初始化**
使用 mixing Hamiltonian 在絕熱量子退火演化的公式 $H(t) = (1 − \frac{t}{T})H_B + \frac{t}{T}H_C$ ，之一階Suzuki-Trotter分解 $$ \gamma_i = \frac{i}{p}\Delta t,\ \beta_i = (1-\frac{i}{p})\Delta t, \ \
\text{ for }\ \Delta t = \frac{T}{p},\ i = 1,...,p$$
執行一次 QAOA 的量子電路，並且找到效果最好的 i 作為初始化參數。
$%$
對於特定平面圖的 Max-cut 問題，一次 TQA 能提供多次隨機初始化的最佳結果。$_{[13]}$

## (四) 研究方法與步驟

隨著 QAOA 的電路深度增加，演算法的 optimization landscape 就越複雜，而若沒有適當的起始化，QAOA 更容易得到不準確的結果$_{[4]}$。因此，本計畫將透過數學與實作驗證，整理出針對不同情況與圖形的適當起始化。

1. **探討不同的初始化方法**

本計畫將會探討與分析不同初始化方法，包括現有的與自創的初始化方式，討論現有數據，並比較它們在現有量子電腦上實踐的潛力。

探討部分，本計畫將計算不同初始化方式之時間複雜度，利用數學工具分析每項初始化方法的準確度，並且分析現有文獻上執行不同初始化方法的結果。

2. **實作 QAOA**

Max-cut 問題是給定一個平面圖，求一種將平面圖所有頂點分成兩組的方法，使得連接埠同組的邊數量是最大值。近年有許多文獻使用 Max-cut 問題來探討 QAOA 的效果，因此我們也將使用 Max-cut 問題來分析不同初始化提升 QAOA 的效果。

本計畫將利用 qiskit 與 SPSA optimizer 在 python 中實作第一步驟中整理出所有的可行初始化方法，並且比較對於 networkx 所生成之不同平面圖，使用這些初始化方法所得到的 Max-cut 之準確度。

產生結果後，本計畫將收集不同初始化方式之執行速度與結果，比較平面圖的複雜度與深度之影響。最後依照以上數據，歸類整理針對不同平面圖、需求下最適合的初始化方法。

預計上，此研究能夠找出適當的初始化，使得 QAOA 演算法所得出的結果，在預測頂點數大於 20 的 networkx regular graph 之 Max-cut 時，也能達成 70% 以上的準確率。

## (五) 預期結果

本計畫預期能做到兩點：

1. 提出新初始化方式，並且整理出針對不同種類的平面圖與不同目標，合適的 QAOA 初始化策略。
2. 透過 qiskit 實作此策略時，在預測頂點數大於 20 的 networkx regular graph 的 Max-cut 時，達成 70% 以上的準確率。

## (六) 參考文獻

1. Qingfeng Wang, Tauqir Abdullah (2018) [An Introduction to Quantum Optimization Approximation Algorithm](https://www.cs.umd.edu/class/fall2018/cmsc657/projects/group_16.pdf)
2. Jansen, Thomas (1998) [Introduction to the Theory of Complexity and Approximation Algorithms](https://doi.org/10.1007/BFb0053011)
3. E. Farhi, J. Goldstone, and S. Gutmann (2014) [A Quantum Approximate Optimization Algorithm](https://arxiv.org/abs/1411.4028)
4. G. E. Crooks (2018) [Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem](https://arxiv.org/abs/1811.08419)
5. Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, Kristel Michielsen (2019) [Benchmarking the Quantum Approximate Optimization Algorithm](https://arxiv.org/abs/1907.02359)
6. Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa (2020) [How many qubits are needed for quantum computational supremacy?](https://quantum-journal.org/papers/q-2020-05-11-264/)
7. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin (2020) [Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices](https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.021067)
8. Jonathan Wurtz, Peter J. Love (2021) [MAXCUT QAOA performance guarantees for p >1](https://arxiv.org/abs/2010.11209)
9. R. Shaydulin, I. Safro, and J. Larson (2019) [Multistart methods for quantum approximate optimization](https://doi.org/10.1109/HPEC.2019.8916288)
10. D. J. Egger, J. Marecek, and S. Woerner (2020) [Warmstarting quantum optimization](https://arxiv.org/abs/2009.10095)
11. M. Alam, A. Ash-Saki, and S. Ghosh (2020) [Accelerating Quantum Approximate Optimization Algorithm using Machine Learning](https://arxiv.org/abs/2002.01089)
12. S. Khairy, R. Shaydulin, L. Cincio, Y. Alexeev, and P. Balaprakash, [Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems](https://arxiv.org/abs/1911.11071)
13. Stefan H. Sack and Maksym Serbyn (2021) [Quantum annealing initialization of the quantum approximate optimization algorithm](https://doi.org/10.22331/q-2021-07-01-491)

## (七) 需要指導教授指導內容

1. 相關文獻收集。
2. 提供數學工具分析不同的初始化方法。
3. 提供 qiskit 實作上的建議。