量子優化的統一語言：QUBO | EntangleTech 量子教育平台

# 量子優化的統一語言：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）。

TSP 範例

我們可以把這問題簡單地畫成 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} ## 總結在前面這幾個章節，我們很著重在如何把問題寫成數學式子，讓電腦能理解我們要解什麼樣的問題，從下章開始，我們將會介紹如何用量子電腦解這些問題。