# Max-Cut 問題
為了讓讀者體會量子電腦如何應用在優化問題上，我們將統一用很常見的優化問題來貫穿全文：圖論中的 Maximum Cuts 問題。

## Graphs 與 Cuts

在圖論中，一個圖 graph $G$ 會有兩個元素：頂點（vertices）$V$ 與邊長（edges）$E$：

<div style="text-align: center;margin-top: 20px;">
<img src="https://hackmd.io/_uploads/HJvofkP_el.svg" alt="Max cut 1" width="60%"/>
<br>其中一種 graph
<p>
</p>
</div>

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

<div style="text-align: center;margin-top: 20px;">
<img src="https://hackmd.io/_uploads/ryQGXJvOee.svg" alt="Max cut 2" width="60%"/>
<br>一條曲線貫穿 graph 的五個邊，並將五個頂點分成藍色與綠色兩類
<p>
</p>
</div>

## 轉成數學式

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

<div style="text-align: center;margin-top: 20px;">
<img src="https://hackmd.io/_uploads/B19LmyDugg.svg" alt="Max cut 3" width="60%"/>
<br>藍色點取值 -1，綠色點取值 +1
<p>
</p>
</div>

可以發現，如果兩個頂點之間有曲線通過，那這兩個頂點的乘積會是 $-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}

<div style="text-align: center;margin-top: 20px;">
<img src="https://hackmd.io/_uploads/Hk1JDkPugx.svg" alt="TSP" width="60%"/>
<br>每個邊長都賦予一個權重，要找到一條曲線貫穿越多的邊且加起來的權重最少
<p>
</p>
</div>

到這邊看起來 Max-Cut 問題挺容易的，但那是因為我們舉的範例很簡單，實際上，Max-Cut 是屬於 NP 問題，說明目前還沒有古典演算法能有效率地解決這類問題。