---
# System prepended metadata

title: 03 QUBO
tags: [量子演算法（下下）]

---

# 量子優化的統一語言：QUBO
## QUBO 簡介
數學裡有一種問題稱作 subset problem，請你從一串整數 $S$ 裡挑出數字，使得這些數字相加起來等於 $T$。比方說 $S=\{1, 4, -2\}$，從中挑數字使得相加起來等於 $T=2$，那聰明的你，應該可以很快找到答案，就是 $4-2$。

那對於電腦而言，電腦該怎麼解這問題。首先我們定義一串二進位變數 $x_0,\cdots, x_m$，他們可以是 $0$ 也可以是 $1$，來代表要不要選這數字，然後將這串二進位變數分派給 $S$ 裡面的每個數字，即：

\begin{align}
1x_0 +4x_1 -2x_2 
\end{align}

然後減去 $T$ 後做平方：

\begin{align}
&(1x_0 +4x_1 -2x_2 -2)^2\\
=&x_0^2+8x_0x_1-4x_0x_2-4x_0+16x_1^2-16x_1x_2-\\
&16x_1^2-16x_1x_2-16x_1+4x_2^2+8x_2+4 \tag{1}\\
=&x_0+8x_0x_1-4x_0x_2-4x_0+16x_1-16x_1x_2-\\
&16x_1-16x_1x_2-16x_1+4x_2+8x_2+4 
\end{align}

最後一行用到 $x_i^2=x_i$（因為 $0^2=0, 1^2=1$）。對於電腦而言，就是要找到一個 $\{x_i\}$ 組合使得（1）式越來越接近 $0$，以這個例子，電腦找到的最佳解應為 $x_1=x_2=1, x_0=0$。不過，真的在優化過程中，常數項 $4$ 也可以直接丟掉，就變成：

\begin{align}
x_0+8x_0x_1-4x_0x_2-4x_0+16x_1-16x_1x_2-
16x_1-16x_1x_2-16x_1+4x_2+8x_2
\end{align}

一樣找到一個組合使得上式越小越好，最後再把常數 $4$ 加回去。

對於形式像（1）式的問題統稱為 Quadratic Unconstrained Binary Optimization (QUBO)：

\begin{align}
\text{Minimize} \space &\sum_i^m \sum_j^m c_{i,j}x_i x_j \\
\text{subject to} \space &x_i\in\{0,1\},\space i,j=0,\cdots,m
\end{align}

因為變數最大會是二元（$x_0^2$ 或是 $x_0x_1$），所以稱為 quadratic，且每個變數 $x_i$ 都是二進位 binary，另外我們並沒有限制說哪個 $x_i$ 得是 $0$ 還是 $1$，所以是 unconstrain。

有趣地，QUBO 可以很輕易地轉換成 Ising model：

\begin{align}
H=-\sum_i h_i z_i - \sum_{ij} J_{ij}z_iz_j
\end{align}

這邊 $z_i$ 的取值是 $1$ 或 $-1$，而前面的 $x_i$ 取值 $0$ 或 $1$，只要簡單地套用 $x_i=\frac{1-z_i}{2}$；要反過來的話，就套用 $z_i=2x_i-1$。

## QUBO 與 Ising model 轉換
我們這邊舉個簡單的範例，比方說下式：

\begin{align}
x_0^2+2x_0x_1-3
\end{align}

我們想把這 QUBO 轉成 Ising model，我們簡單地套用 $x_i=\frac{1-z_i}{2}$ 將上式變成：

\begin{align}
&(\frac{1-z_0}{2})^2+2\frac{1-z_0}{2}\frac{1-z_1}{2}-3\\
=& \frac{z_0^2}{4}+\frac{z_0z_1}{2}-z_0-\frac{z_1}{2}-\frac{9}{4}\\
=& \frac{1}{4}+\frac{z_0z_1}{2}-z_0-\frac{z_1}{2}-\frac{9}{4}
\end{align}

最後一項我們要到 $z_i^2=1$（因為 $z_i$ 只能取值 $1$ 或是 $-1$），最後我們可以把常數項 $-2$ 去掉，等電腦找到最優解之後再加回來，因此電腦要解的部分是：

\begin{align}
\text{minimize} &\frac{1}{2}Z_0Z_1-Z_0-\frac{1}{2}Z_1\\
\text{subject to }\space &Z_i\in\{1,-1\},\space i=0,1,2
\end{align}

接下來我們來看幾個經典的優化問題，看如何把這問題以 QUBO 的形式表達。

## Binary Linear Programming
其實跟前面的 subset problem 很相似，但加上限制項（constraints），比方說我們額外加上條件 $2x_0+x_1\leq1$，那上面的問題就變成：

\begin{align}
\text{Minimize} \space &x_0 +4x_1 -2x_2-2 \\
\text{subject to} \space &2x_0+x_1\leq1\\ 
&3x_0-x_1+3x_2 \leq 4\\
&x_i\in\{0,1\}
\end{align}

要將上式轉成 QUBO 形式，我們得做些轉換，我們先聚焦在第一個 constraints 項 $2x_0+x_1\leq1$，然後引入新的變數 $y$ 將這不等式改寫成等式：

\begin{align}
2x_0+x_1+y=1
\end{align}

可以看到上式只有當 $2x_0+x_1\leq1$ 才會成立．當 $x_0=x_1=0$ 時，$y=1$；當 $x_0=0,x_1=1$ 時，$y=0$。

第二個 constraints 項 $3x_0-x_1+3x_2 \leq 4$，就稍微棘手，我們一樣需要引入二進位變數，然後這些新變數加總起等於 $4$，像是：

\begin{align}
3x_0-x_1+3x_2+y_0+2y_1+4y_2=4
\end{align}

如此才能確保只有當 $3x_0-x_1+3x_2 \leq 4$ 上式才會成立。當然這不是唯一的解法，眼尖的讀者能發現，當 $y_0=y_1=y_2=1$ 時，這三個變數加起來會到 $7$，遠超過 $4$，如果你擔心這問題，那也可以嘗試下式這種寫法：

\begin{align}
3x_0-x_1+3x_2+y_0+2y_1+2y_2=4
\end{align}

如此原本的問題就變成：

\begin{align}
\text{Minimize} \space &x_0 +4x_1 -2x_2-2 \\
\text{subject to} \space &2x_0+x_1+y=1\\
&3x_0-x_1+3x_2+y_0+2y_1+2y_2=4\\
&x_i\in\{0,1\} \\
&y_i\in\{0,1\}
\end{align}


最後，我們將這兩個 constraints 當作 penalty terms （懲罰項）併進 QUBO，亦即在前面加進懲罰項 $A, B$，這就跟機器學習裡的 cost function 類似，數字越大，懲罰效果越大（但不一定代表優化效果越好）來告訴電腦你往錯誤的方向找答案，意即：

\begin{align}
\text{Minimize} \space &(x_0 +4x_1 -2x_2-2)^2+A(2x_0+x_1+y-1)^2+B(3x_0-x_1+3x_2+y_0+2y_1+2y_2-4)^2\\
\text{subject to} \space &x_i\in\{0,1\} \\
&y_i\in\{0,1\}
\end{align}

上面就是一個 QUBO 形式，其中 $A, B$ 要自己透過實驗和經驗找到最適合的數字。

## 旅行推銷員問題

有很多知名的優化問題都能寫成 QUBO，比方說旅行推銷員問題。假設你是推銷員，你要從公司出發到一個鄉鎮挨家挨戶推銷你的產品，而你跟筆者一樣很厭倦上班，你想找到一條可以遍歷每戶家且不重複後回到公司，距離又最短的路，這問題就是 travelling salesman problem（TSP）。

<div style="text-align: center;margin-top: 20px;">
    <img src="https://hackmd.io/_uploads/rkquEMvdee.svg" alt="TSP" width="40%"/>
    <br>TSP 範例
    <p>
    </p>
</div>

我們可以把這問題簡單地畫成 graph，如上圖。每個頂點 $i$ 代表一戶家，頂點 $i$ 與 $j$ 之間的數字可以代表兩戶家之間的距離，或是通勤時間，記做 $w_{ij}$。

我們定義 $x_{il}$ 代表今天第 $l$ 個行程是拜訪第 $i$ 個城市，因為每個城市都只能拜訪一次，不能同個城市拜訪兩次以上，因此：

\begin{align}
\sum_{l=0}^m x_{il}=1
\end{align}

另外，每次探訪只能拜訪一戶家，不能同時拜訪兩戶家，因此：

\begin{align}
\sum_{i=0}^m x_{il}=1
\end{align}

以上兩項稱作限制項，接著總拜訪距離或是總通勤時間是：

\begin{align}
\sum_{l=0}^{m-1}\sum_{i=0}^m\sum_{j=0}^m w_{ij}x_{il}x_{jl+1}
\end{align}

結合限制項，完整式子如下：

\begin{align}
\text{minimize} &\sum_{l=0}^{m-1}\sum_{i=0}^m\sum_{j=0}^m w_{ij}x_{il}x_{jl+1}+A(\sum_{l=0}^m x_{il}-1)^2+B(\sum_{i=0}^m x_{il}-1)^2 \\
\text{subject to }\space &x_{il}\in\{0,1\}, i,l=0,\cdots,m
\end{align}

## 總結
在前面這幾個章節，我們很著重在如何把問題寫成數學式子，讓電腦能理解我們要解什麼樣的問題，從下章開始，我們將會介紹如何用量子電腦解這些問題。