---
# System prepended metadata

title: 02 Mapping to Qubit
tags: [量子演算法（下下）]

---

# Mapping to Qubit

前面兩篇文章，我們從人類看得懂的圖論問題變成電腦看得懂的數學方程式：

\begin{align}
\sum w_{ij} z_i z_j
\end{align}

然而量子電腦看不懂這條方程式，為了能讓量子電腦求解 Max-Cut 問題，我們接著要把這條方程式以量子計算的語言書寫。

## 位元到 Qubits
為了簡單起見，我們以下圖這種結構簡單的 graph 且 $w_{ij}=1$ 做為範例：

<div style="text-align: center;margin-top: 20px;">
    <img src="https://hackmd.io/_uploads/SJG_YJDuxx.svg" alt="cut to qubit" width="40%"/>
    <br>
    <p>
    </p>
</div>

你應該可以很輕鬆地寫下它的 Max-Cut 方程：

\begin{align}\tag{1}
z_0z_1+z_0z_2
\end{align}

要讓量子電腦看得懂，現在每個頂點都是一個個 qubits，它可以是 $|0\rangle$ 也可以是 $|1\rangle$。以下圖為例，曲線貫穿其中一個邊，因此其 "量子態" $\psi$ 可以寫成 $|010\rangle$：

<div style="text-align: center;margin-top: 20px;">
    <img src="https://hackmd.io/_uploads/Bk4sKJDugg.svg" alt="cut to qubit" width="40%"/>
    <br>
    <p>
    </p>
</div>

要讓量子電腦夠輸出這系統的能量值，我們把（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$ 會在後面提及。

<!---
## 通式

對於這問題，今天量子電腦的目的就是要找到一組 $|\psi\rangle$ 來讓這個期望值（4）達到最小值

\begin{align}\tag{5}
\langle \psi|Z_jZ_k|\psi\rangle
\end{align}

其中 $|\psi\rangle$ 可以寫成：

\begin{align}
|\psi\rangle=\sum_x c_x |x\rangle
\end{align}

其中 $|x\rangle$ 是這三個 qubits 各種可能的狀態（像是 $|000\rangle, |010\rangle\cdots$ 等等），因此（5）式可以寫成：

\begin{align}
\langle \psi|Z_jZ_k|\psi\rangle&=\bigg(\sum_y c_y^* \langle y| \bigg)Z_jZ_k \bigg(\sum_x c_x |x\rangle \bigg)\\
&=\sum_y\sum_x c_y^*c_x \langle y|Z_jZ_k|x\rangle \tag{6}\\
\end{align}

我們先來看其中一項 $Z_jZ_k|x\rangle$，從前面的範例我們知道 

\begin{align}
Z_jZ_k|x\rangle&=+1|x\rangle \text{ 或}\\
Z_jZ_k|x\rangle&=-1|x\rangle 
\end{align}

所以

\begin{align}
\langle y|Z_jZ_k|x\rangle&=\pm \langle y|x\rangle=0 \text{ 如果 } y\neq x
\end{align}

回到（6）式

\begin{align}
\langle \psi|Z_jZ_k|\psi\rangle&=\sum_y\sum_x c_y^*c_x \langle y|Z_jZ_k|x\rangle\\
&=\sum_x |c_x|^2 \langle x|Z_jZ_k|x\rangle
\end{align}