從圖論到 Qubits | EntangleTech 量子教育平台

# Mapping to Qubit 前面兩篇文章，我們從人類看得懂的圖論問題變成電腦看得懂的數學方程式： \begin{align} \sum w_{ij} z_i z_j \end{align} 然而量子電腦看不懂這條方程式，為了能讓量子電腦求解 Max-Cut 問題，我們接著要把這條方程式以量子計算的語言書寫。 ## 位元到 Qubits 為了簡單起見，我們以下圖這種結構簡單的 graph 且 $w_{ij}=1$ 做為範例：

你應該可以很輕鬆地寫下它的 Max-Cut 方程： \begin{align}\tag{1} z_0z_1+z_0z_2 \end{align} 要讓量子電腦看得懂，現在每個頂點都是一個個 qubits，它可以是 $|0\rangle$ 也可以是 $|1\rangle$。以下圖為例，曲線貫穿其中一個邊，因此其 "量子態" $\psi$ 可以寫成 $|010\rangle$：

要讓量子電腦夠輸出這系統的能量值，我們把（1）式改成算符（operator）（在這邊就是 [$Z$](https://www.entangletech.tw/lesson/basic-algorithm-08) 矩陣），即： \begin{align}\tag{2} z_0z_1+z_0z_2 \rightarrow Z_0Z_1+Z_0Z_2 \end{align} 所以量子電腦的輸出就會是在這個狀態下以 $Z$ 作為[觀測量時的期望值](https://www.entangletech.tw/lesson/basic-algorithm-17-2)： \begin{align}\tag{3} \langle\psi|Z_0Z_1+Z_0Z_2|\psi\rangle \end{align} 先不要怕，我們一步一步看這式子怎麼算，問題暫且簡化到 $|\psi\rangle=|0\rangle$ 時，期望值是多少： \begin{align} \langle 0|Z|0\rangle&= \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix}=1 \end{align} 同樣地，當 $|\psi\rangle=|1\rangle$ 時： \begin{align} \langle 1|Z|1\rangle&= \begin{bmatrix} 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix}=-1 \end{align} 回到（3）式，我們可以把它拆成兩項： \begin{align} \langle\psi|Z_0Z_1+Z_0Z_2|\psi\rangle&= \langle\psi|Z_0Z_1|\psi\rangle+\langle\psi|Z_0Z_2|\psi\rangle\\ &=\langle\psi|Z\otimes Z\otimes I|\psi\rangle+\langle\psi|Z\otimes I\otimes Z|\psi\rangle\tag{4} \end{align} 我們先看（4）式中的第一項： \begin{align} \langle 010|Z\otimes Z\otimes I|010\rangle&=\langle 010| \bigg( Z|0\rangle\otimes Z|1\rangle\otimes I|0\rangle \bigg) \\ &=\langle 0|Z|0\rangle \langle 1|Z|1\rangle \langle 0|I|0\rangle \\ &= 1(-1)1 =-1 \end{align} 同樣地： \begin{align} \langle 010|Z\otimes I\otimes Z|010\rangle&= \langle 0|Z|0\rangle\langle 1|I|1\rangle \langle 0|Z|0\rangle \\ &=1 \end{align} 所以 \begin{align} \langle\psi|Z_0Z_1+Z_0Z_2|\psi\rangle&=0 \end{align} 對於量子電腦而言，就是找到一組 $|\psi\rangle$ 使得上述這期望值最小。 ## Ising Model 回到上一節提到得 [Ising model](https://www.entangletech.tw/lesson/optim-01)： \begin{align} H=-\sum_i h_i z_i - \sum_{ij} J_{ij}z_iz_j \end{align} 如果今天我們要求這系統在 $|\psi\rangle$ 這狀態下的能量值，即 \begin{align} \langle\psi|H|\psi\rangle=-\sum_i h_i \langle\psi|z_i|\psi\rangle - \sum_{ij} J_{ij} \langle\psi|z_iz_j|\psi\rangle \end{align} 是不是跟上面圖論的例子很像呢～（只是 $h_i=0, J_{ij}=w_{ij}$） \begin{align} \langle\psi| Z_iZ_j|\psi\rangle \end{align} 然後一樣都是想辦法找到一組 $|\psi\rangle$ 使得能量最小，怎麼尋找到這樣的 $|\psi\rangle$ 會在後面提及。