從圖論到 Ising Model

作者:
林昱誠(Yu-Cheng Lin)
閱讀時間:
5
分鐘
# Ising Model 在我們繼續 Max-Cut 問題之前,我們要先介紹 Ising model。Ising model 是統計物理裡很有名的模型,可以解釋很多物理現象,像是物質的磁性性質。
Ising model
Ising model 示意圖

Picture comes from Wiki

Ising model 是由一個一個自旋(spin)組成,如果你還沒學過 spin 概念,就先粗淺地想像成磁鐵,箭頭指向代表北極方向。每個 spin 都以記號 $z_i$ 代表,當箭頭向上(spin up),$z_i=+1$,反之,spin down 就是 $z_i=-1$,有沒有看起來很熟悉。 這樣的系統,他的總能量(Hamiltonian)可以寫作: \begin{align} H=-\sum_i h_i z_i - \sum_{ij} J_{ij}z_iz_j \end{align} 其中 $h_i$ 是 spin $i$ 與外加磁場交互作用貢獻的能量,$J_{ij}$ 是 spin $i$ 與 spin $j$ 的交互作用(interaction)。Ising model 問題是要透過不斷翻轉每個 spin,使得能量 $H$ 達到最低點。 當你把 $h_i$ 設為 $0$,$J_{ij}$ 改成記號 $w_{ij}$(負號吸收進去),整個問題的公式就跟上一節的 [Max-Cut](https://www.entangletech.tw/lesson/optim-00) 一模一樣,我們將在下一節看得更清楚: \begin{align} H=\sum_{ij} w_{ij}z_iz_j \end{align} ## D-Wave D-Wave 的量子退火(quantum annealer)架構就是基於 Ising model,每個 spin 就是一個 qubit,然後對這些 qubit 施加外加磁場來決定 $h_i$,透過兩個 qubits 之間的耦合強度來決定 $J_{ij}$,那要如何利用 Ising model 做計算,我們將會在絕熱量子計算中提到。
Ising model
每一個白色圈圈是一個超導 qubit,8 個這樣的 qubit 組成這樣一個棱形圖樣(拓樸)就是 Ising model 裡的一個箭頭(因為量子電腦容易出錯,需要用數個 qubits 代表一個品質比較好的 qubit)

Picture comes from D-Wave

課程目錄