量子計算入門（下）：量子優化
・第
1
課

優化的起點：算圖

作者：
林昱誠（Yu-Cheng Lin）
閱讀時間：
5
分鐘
# Max-Cut 問題 為了讓讀者體會量子電腦如何應用在優化問題上，我們將統一用很常見的優化問題來貫穿全文：圖論中的 Maximum Cuts 問題。 ## Graphs 與 Cuts 在圖論中，一個圖 graph $G$ 會有兩個元素：頂點（vertices）$V$ 與邊長（edges）$E$：
Max cut 1
其中一種 graph

Max-Cut 問題是想找到一條線貫穿 graph 中的 edges，把 vertices 分成兩類（sets，集合），且被貫穿的 edges 數量越大越好。以此 graph 為例，你可以找到一條曲線貫穿五個 edges，把頂點分成兩類，你找不到其他可以貫穿更多個邊的曲線。
Max cut 2
一條曲線貫穿 graph 的五個邊，並將五個頂點分成藍色與綠色兩類

## 轉成數學式 要讓電腦能解這問題，我們得把圖像轉成數學方程式，電腦才看得懂。首先，對於有 $n-1$ 個頂點的 graph，我們給每個頂點一個記號 $z_i$，$i=0, 1, \cdots, n-1$。當我們畫個曲線把頂點分成兩類，其中一類頂點 $z_i$ 取值 $+1$，另一類則為 $-1$：
Max cut 3
藍色點取值 -1，綠色點取值 +1

可以發現，如果兩個頂點之間有曲線通過，那這兩個頂點的乘積會是 $-1$，沒有則為 $+1$。我們現在的問題就是找到一種組合方式，可以讓所有頂點乘積加總起來會是最小： \begin{align} \text{Minimize} \qquad &\sum_{(i, j)\in E} z_iz_j \\ \text{subject} \qquad &z_i\in\{-1,1\}, i=0,\cdots, n-1 \end{align} 以上圖為例，我們要求的是以下方程式的最小值 \begin{align} z_0z_1+z_0z_2+z_1z_2+z_1z_3+z_2z_4+z_3z_4 \end{align} 當然這圖論問題可以再複雜，我們為每個邊賦予權重 $w_{ij}$，那問題就變成： \begin{align} \text{Minimize} \qquad &\sum_{(i, j)\in E} w_{ij}z_iz_j \\ \text{subject} \qquad &z_i\in\{-1,1\}, i=0,\cdots, n-1 \end{align} 以以下這個 graph 為例就會是： \begin{align} w_{01}z_0z_1+w_{02}z_0z_2+w_{12}z_1z_2+w_{13}z_1z_3+w_{24}z_2z_4+w_{34}z_3z_4 \end{align}
TSP
每個邊長都賦予一個權重，要找到一條曲線貫穿越多的邊且加起來的權重最少

到這邊看起來 Max-Cut 問題挺容易的，但那是因為我們舉的範例很簡單，實際上，Max-Cut 是屬於 NP 問題，說明目前還沒有古典演算法能有效率地解決這類問題。
QAOA 演算法
optim
7
量子退火
optim
6
絕熱量子計算
optim
5
量子優化的統一語言：QUBO
optim
4
從圖論到 Qubits
optim
3
從圖論到 Ising Model
optim
2
優化的起點：算圖
optim
1
保護未來：認識雜湊式加密在量子抗性中的角色
quantum-safe
4
量子計算是否正在終結區塊鏈？
quantum-safe
3
NIST 標準化流程如何運作？
quantum-safe
2
從量子安全中獲利
quantum-safe
1
量子機器學習 (十) - 量子機器學習的未來
qml
10
量子機器學習 (九) - 基於量子訓練的強化學習
qml
9
量子機器學習 (八) - 基於量子訓練的影像辨識
qml
8
量子機器學習 (七) - 更新量子訓練參數
qml
7
量子機器學習 (六) - 量子訓練概觀
qml
6
量子機器學習 (五) - 參數更新方法
qml
5
量子機器學習 (四) - 古典前處理/後處理
qml
4
量子機器學習 (三) - 關於量子電路架構
qml
3
量子機器學習 (二) - 資料編碼
qml
2
量子機器學習 (一) - 概述
qml
1
後量子密碼學 10：簡介編碼密碼學（Code-based Cryptography）
pqc
10
後量子密碼學 09：簡介哈希函數（Hash Function）簽章
pqc
9
後量子密碼學 08：簡介多元二次密碼學
pqc
8
後量子密碼學 07：NTRU II
pqc
7
後量子密碼學 06：NTRU I
pqc
6
後量子密碼學 05：多項式環 II
pqc
5
後量子密碼學 04：多項式環 I
pqc
4
後量子密碼學 03：二維晶格密碼學的正確性
pqc
3
後量子密碼學 02：一個簡易的二維晶格密碼學
pqc
2
後量子密碼學 01：密碼學導論
pqc
1
補充：密度矩陣（Density Matrix）
basic-algorithm
18
量子傅立葉轉換（下）
algorithm
8
量子傅立葉轉換（中）
algorithm
7
量子傅立葉轉換（上）
algorithm
6
以 Pennylane 做測量
pennylane
6
用 Pennylane 建立量子邏輯閘
pennylane
5
用 Pennylane 建立量子電路
pennylane
4
Colab 與 Jupyter 介面介紹
pennylane
3
安裝 Pennylane
pennylane
2
Deutsch-Jozsa 演算法（下）
algorithm
5
Deutsch-Jozsa 演算法（上）
algorithm
4
量子演算法總覽
algorithm
1
Deutsch 演算法（下）
algorithm
3
Deutsch 演算法（上）
algorithm
2
量子計算概覽：當電腦遇上量子世界
basic-algorithm
1
自學資源與路線：入門量子計算的第一步
basic-algorithm
2
量子電路：量子邏輯閘的實踐
basic-algorithm
17
測量：讀取計算結果
basic-algorithm
16
量子邏輯閘（下）：量子邏輯閘的特性
basic-algorithm
15
量子邏輯閘（中）：多個量子位元的操作
basic-algorithm
14
量子位元 （下）：量子糾纏
basic-algorithm
13
量子位元（中）：多個量子位元
basic-algorithm
12
布洛赫球面 （下）：解讀量子邏輯閘的運作
basic-algorithm
11
布洛赫球面（上）：量子位元可視化
basic-algorithm
10
量子邏輯閘（上）：單一量子位元操作
basic-algorithm
9
量子位元（上）：量子計算的基本單位
basic-algorithm
8
重視經典電腦：過渡到量子電腦
basic-algorithm
7
Pennylane 簡介
pennylane
1
演算法複雜度
basic-algorithm
6
經典邏輯閘（下）：邏輯閘的特性
basic-algorithm
5
經典邏輯閘（上）：電腦運算的基礎
basic-algorithm
4
電腦的世界只有 0 與 1：二進位表示法
basic-algorithm
3
量子硬體總覽
hardware-general
1
第三題：Many-Body Quantum Dynamics
ibm-2023-spring
3
第二題：Quantum Random Walks and Localization
ibm-2023-spring
2
第一題：Trotterization
ibm-2023-spring
1
如何綜合評估量子電腦的表現
hardware-general
10
Qubit 狀態的壽命（相干時間）：T2
hardware-general
9
Qubit 狀態的壽命（相干時間）：T1
hardware-general
8
保真度（Fidelity)：衡量量子邏輯閘的指標
hardware-general
7
附錄 C：絕熱通道
hardware-general
13
如何操作 Qubit：絕熱通道（Adiabetic passage）
hardware-general
6
附錄 B：拉比震盪
hardware-general
12
如何操作 Qubit：拉比震盪（Rabi Oscillation）
hardware-general
5
附錄 A：雙態系統
hardware-general
11
Deutsch 演算法
basic-algorithm
18
雙態系統（Two Level System）：Qubit 的基礎
hardware-general
4
DiVincenzo Criteria：量子電腦的五大標準
hardware-general
3
自學資源與路線：入門量子電腦硬體的第一步
hardware-general
2
課程撰寫中
s
1
特徵向量和特徵值(eigenvector and eigenvalue)
linear-algebra
9
量子計算中的特殊矩陣
linear-algebra
8
張量積(Tensor product)
linear-algebra
7
Orthonormal Bases
linear-algebra
6
正交（Orthogonality）
linear-algebra
5
基(Basis)
linear-algebra
4
數學基礎：量子計算的起點
linear-algebra
2
量子計算的數學之鑰：線性代數入門
linear-algebra
1
什麼是量子電腦？
quantum-computer-basics
1
量子電腦如何改變世界
quantum-computer-basics
2
如何實現量子電腦
quantum-computer-basics
7
電腦怎麼做計算
quantum-computer-basics
3
疊加態
quantum-computer-basics
5
量子糾纏
quantum-computer-basics
6
進入量子世界
quantum-computer-basics
4
自學資源與路線
quantum-computer-basics
8
狄拉克(Dirac)表示法
linear-algebra
3
量子電腦現況與未來
quantum-computer-basics
9
上ㄧ課
#上一課課程名稱
下ㄧ課
#下一課課程名稱
課程目錄
特別感謝
Copyright © 2024 Entangle Tech. All Rights Reserved.
特別感謝
Copyright © 2024 Entangle Tech. All Rights Reserved.
特別感謝
Copyright © 2024 Entangle Tech. All Rights Reserved.