量子退火 (Quantum Annealing)

做緊 optimization 嘅 project 時接觸到 quantum annealing,覺得呢個技術幾實用,所以整理咗啲 notes 分享下。

咩係 Quantum Annealing?

簡單嚟講,quantum annealing 係一種專門用嚟解優化問題 (Optimization Problems) 嘅量子計算技術。當你有好多可能嘅解決方案,要搵出「最好」或者「成本最低」嗰個,quantum annealing 就幫到手。

傳統退火 (Classical Annealing)

名稱嚟自冶金學嘅「退火」工藝:

1. 將金屬加熱到好高溫 (原子可以自由移動)
2. 慢慢冷卻
3. 原子會排列到最低能量嘅穩定狀態

喺計算上面,模擬退火 (Simulated Annealing) 用類似嘅概念:

• 一開始「溫度」好高,演算法可以隨意跳到唔同解決方案
• 慢慢降低「溫度」,減少隨機性
• 最後希望搵到最低能量狀態 (最優解)

能量地景 (Energy Landscape)

要理解 quantum annealing,可以想像一個充滿山峰同山谷嘅地景:

• 山谷:可能嘅解決方案
• 最低嘅山谷 (Global Minimum):最佳解
• 山峰:能量障壁

問題:局部最小值 (Local Minimum)

傳統演算法容易卡喺局部最小值——一個山谷唔係最低,但係周圍都係山峰,演算法以為自己已經搵到最佳解。

例子:想像你矇住眼喺山區行,想搵最低點:

• 你一路向低行,去到一個山谷
• 周圍都係斜坡,你以為呢度就係最低
• 但係其實隔離個山後面仲有個更低嘅山谷
• 因為你要爬山先去到,所以你永遠唔會發現

Quantum Tunneling (量子穿隧)

呢個就係 quantum annealing 嘅 killer feature!

傳統方法 (Thermal Hopping):

• 靠熱能「跳過」山峰
• 如果山峰太高,就過唔到
• 容易卡喺局部最小值

量子方法 (Quantum Tunneling):

• 利用量子力學,可以直接「穿過」山峰
• 唔需要爬上去
• 更容易搵到全域最小值

數學描述

Quantum annealing 嘅 Hamiltonian 可以寫成:

• $H_{text{initial}}$:初始 Hamiltonian (容易準備嘅量子態)
• $H_{text{problem}}$:問題 Hamiltonian (編碼咗你要解嘅問題)
• $A(t)$ 同 $B(t)$:時間相關嘅係數

過程:

1. 開始時:$A(t)$ 大,$B(t)$ 細 → 系統處於 $H_{\text{initial}}$ 嘅基態
2. 慢慢變化:$A(t)$ 減少,$B(t)$ 增加
3. 結束時:$A(t) = 0$,$B(t)$ 大 → 系統(hopefully)處於 $H_{\text{problem}}$ 嘅基態 = 問題嘅最優解

Quantum Tunneling vs Thermal Hopping 比較

實際應用

1. 旅行推銷員問題 (TSP)

問題:一個推銷員要去 $n$ 個城市,每個城市去一次,點樣搵最短路線?

複雜度:$n!$ 種可能 (例如 20 個城市 = 2,432,902,008,176,640,000 種可能)

用 Quantum Annealing:

• 將問題轉化成 Ising model 或 QUBO (Quadratic Unconstrained Binary Optimization)
• D-Wave 量子電腦可以處理呢類問題

2. 投資組合優化

問題:有 $n$ 隻股票,每隻有唔同嘅預期回報同風險,點樣配置資金令到回報最高而風險可控?

數學表達:

• $w_i$:投資喺股票 $i$ 嘅比例
• $r_i$:股票 $i$ 嘅預期回報
• $sigma_{ij}$:股票 $i$ 同 $j$ 嘅協方差 (風險)
• $lambda$:風險厭惡參數

3. 蛋白質摺疊 (Protein Folding)

問題:一條氨基酸鏈點樣摺疊成 3D 結構先可以達到最低能量?

呢個問題對藥物研發好重要,因為蛋白質嘅功能由佢嘅 3D 結構決定。

4. 交通優化

例子:香港有幾百個交通燈,點樣協調佢哋嘅時間令到整體交通流量最佳?

我之前睇過有研究用 quantum annealing 優化北京嘅交通燈系統,話可以減少 20% 擁堵。

D-Wave:第一部商業化 Quantum Annealer

D-Wave Systems 係目前最出名嘅 quantum annealing 公司:

• D-Wave Advantage:5000+ qubit
• 唔係通用量子電腦:只能做 quantum annealing
• 用超導 qubit:需要 ~15 millikelvin (-273.135°C)

實際效能

有啲爭議:某啲問題 quantum annealing 快好多,但係某啲問題傳統優化演算法都唔慢。重點係:

• Quantum annealing 對特定類型嘅問題有優勢
• 唔係所有 optimization 問題都啱用

Quantum Annealing vs Gate-Based 量子計算

我嘅睇法

Quantum annealing 係一個幾實際嘅技術,雖然佢唔係萬能,但係對於某啲 NP-hard optimization 問題,佢確實可以提供價值。

優點:

• 依家已經可以用 (D-Wave cloud)
• Qubit 數量多
• 對特定問題有明確優勢

缺點:

• 只能做 optimization,唔係通用量子電腦
• 唔係所有問題都有 speedup
• 同 classical optimizer 比,advantage 有時唔明顯

如果你做 logistics、finance 或者 drug discovery,值得試下 quantum annealing。不過要小心將問題正確咁 formulate 成 QUBO/Ising model——呢個本身就係一個 art。

參考資料

• Quantum Annealing - Wikipedia
• D-Wave Documentation
• Quantum Annealing vs Gate-Based Quantum Computing
• Introduction to Quantum Annealing (Tutorial)