Efficient Quadratic Ising Hamiltonian Generation with Qubit Reduction——論文欣賞

Automatic generation of Ising Hamiltonians 優化問題有一下特征：

1. 多項式的(Polynomial)目标函數
2. 等式和不等式多項式限制
3. 整數變量在連續(contiguous)和非連續有限集

qubit reduction 的步驟：

4. 把問題casting為二次僞布爾優化問題

5. 使用roof duality 和 extended roof duality 得到變量子集的最優值——這樣就減少了優化問題中變量的數量

6. 這就得到了一個自動化的、問題執行個體依賴的量子比特縮減的過程

7. 這在短期内對拟合近期量子計算機上的優化問題是有用的

在現實世界中整數優化問題包括等式限制和不等式限制

例如

旅行商(Traveling sales man)問題：包括等式和不等式限制，是一個離散優化問題

作業工廠中的房間排程問題(Job shop scheduling)背包問題(knapsack problem)子集合加總問題(subset sum problem)也是包括等式和不等式限制和變量為整數的優化問題

動機

constraints and special kinds of integer varibles

在一些問題中，一些整數變量在非連續的整數集上取值

例如

半連續整數變量：這些變量可以取值為0，也可以取上下界之間的值，這樣的變量有些變量常常在變量不被使用或者被使用就必須在一個特定的區間裡的場合使用

一個特殊的場景：一個航空公司想決定是否要飛行一個線路或者不。他們可能飛一次航班，乘客的最少數量是10，飛機的最大乘客數量是100，飛機所收取的收入會是0（如果飛機沒有起飛）或者是票價×N，其中N是10-100的整數

Pseudo-boolean optimaztion

在計算機視覺中，很多問題是包括二值的馬爾科夫随機場(binary Markov random fields)

MRFs（在離散優化文獻中也稱為僞布爾函數）也被用于解決如下的計算機視覺問題：

圖像分割(Image segmentation)，紋理識别(Texture recognition)超分辨率/視圖合成(Super resolution/view synthesis)

在每個case中，都需要求解MRFs的最小值

一般來說，MRFs有很多限制，比如隻有pairwise interactions，這會導緻quadratic pseudo-boolean optimazation problems（除了triple interactions被考慮）

[原文：Historically a restricted class of MRFs were considered, for e.g. pairwise interactions only, which lead to quadratic pseudo-boolean optimazation problems(with some exception where triple interactions were considered)]

很難最小化高階僞布爾函數（即使是二次型的情況也很難）高階問題的二次約化(Quadratic reductions of higher order problems)也在一般情況下被避免，因為這種約化常常導緻非子模優化(non-submodular optimization)

但是自然場景太豐富了，很難通過 nearest neighbor interactions 捕捉到

是以優化這樣高階的MRFs的能力有潛力在計算機視覺的應用中

方法總結

Problem statement

對于一下這種優化問題，我們用公式表示了一種有效的 Ising Hamiltonians 方法， 和可以被quantum optimization algorithms 解決的 automated qubit reduction produre

m i n i m i z e f ( x 1 , . . . , x p ) s u b j e c t    t o x i ∈ I i ⊂ Z , i = 1 , . . . , p c j ( x i , . . . , x p ) = 0 , j = 1 , . . . , m d k ( x 1 , . . . , x p ) ≤ 0 , k = 1 , . . . , n minimize \quad f(x_1, ..., x_p)\\ subject\;to \quad x_i\in I_i \subset \mathbb Z, \qquad i=1, ..., p\\ c_j(x_i, ..., x_p)=0,\qquad j=1, ..., m\\ d_k(x_1, ..., x_p)\le0,\qquad k=1, ..., n minimizef(x1​,...,xp​)subjecttoxi​∈Ii​⊂Z,i=1,...,pcj​(xi​,...,xp​)=0,j=1,...,mdk​(x1​,...,xp​)≤0,k=1,...,n

函數 f , c j , d j f, c_j, d_j f,cj​,dj​是多項式 over Z \mathbb Z Z in the integer valued variables x 1 , . . . , x p x_1, ..., x_p x1​,...,xp​

I j I_j Ij​是有限整數的子集，這些子集可能不是連續的整數，比如， x 1 ∈ { 0 , 1 , 2 } ∪ { 5 , 6 , 7 , 8 } x_1\in \{0, 1, 2\} \cup \{5, 6, 7, 8\} x1​∈{0,1,2}∪{5,6,7,8}

Outline of method

Step 1：将每個整數變量表示為二進制變量的線性和。根據表示形式的不同，最終可能會引入額外的等式限制

原文：Represent each integer variable as linear sums of binary variables. Depending on the representation, one may end up introducing additional equality constraints

Step 2：引入額外的松弛(slack)變量，将所有不等式限制更改為相等限制。松弛變量是整數變量，使用步驟1中使用的相同技術表示。根據所使用的方法，整數變量的表示可能會引入額外的等式限制

原文：Introduce additional slack variables to change all inequality constraints to equality constraints. The slack varibles are integer varables, that are represented using the same techniques used in Step 1. Depending on the method used, the representation of the interger variables may introduce additional equality constraints

Step 3：通過平方建立一個無限制的僞布爾優化問題，并且使用大權重講等式限制加到目标函數中

原文：Create an unconstrained pseudo-boolean optimization problem, by squaring and adding all the quality constriants, with a large weight to the objective function

Step 4：正交化僞布爾優化問題，減少additional variables的數量。這得到了一個等價的 quadratic pseudo-boolean function (QPBF) 。這是 a qubit reduction step。

原文：Quadratize the pseudo-boolean optimization problem, using the best known current techniques that minimize the number of additional variables used. This gives an equivalent quadratic pseudo-boolean function (QPBF) to optimize. This is a qubit reduction step.

Step 5：通過使用roof duality 和 extended roof duality (which have polynomial runtime) 減少QPBF變量的數量。這決定了布爾變量子集的值。是以，我們得到了一個新的QPBF，它具有較少的布爾變量。這是a qubit reduction step。

原文：Reduce the number of variables in the QPBF using roof duality and extended roof duality techniques (which have polynomial runtime). This determines the values of a subset of the boolean variables. We thus obtain a new QPBF with fewer number of boolean variables. This is a qubit reduction step.

步驟5的輸出是最終的QPBF，可以用 a quantum optimization algorithm 解決。

Note: 步驟5可以使用任何 quadratic Ising Hamiltonian(使用者希望使用quantum optimization algorithms，比如QAOA和VQE)

方法細節

Representing integer variables

整數變量有一下兩種類型

連續集

比如 x 1 ∈ { 5 , 6 , 7 , 8 } x_1\in \{5, 6, 7, 8\} x1​∈{5,6,7,8}

非連續集

比如 x 1 ∈ { 0 , 1 , 2 } ∪ { 5 , 6 , 7 , 8 } x_1\in \{0, 1, 2\} \cup \{5, 6, 7, 8\} x1​∈{0,1,2}∪{5,6,7,8}

假設是有限集

整數變量編碼方法

整數集	非整數集
Log encoding	One hot encoding
One hot encoding	Efficient encoding scheme
Discrete slack method
Greedy decomposition

以上方法将在我未來的部落格中依次介紹

Discrete slack method, Greedy decomposition and Efficient encoding scheme introduced in patent application draft 95762203(Matsuo), 2019.

步驟1後，所有的整數變量都被替換成了二值變量，但是新的限制條件也被添加進來了

m i n i m i z e f ( x 1 , . . . , x p ′ ) s u b j e c t    t o x i ∈ { 0 , 1 } , i = 1 , . . . , p ′ c j ( x i , . . . , x p ′ ) = 0 , j = 1 , . . . , m ′ d k ( x 1 , . . . , x p ′ ) ≤ 0 , k = 1 , . . . , n ′ \begin{aligned} &minimize \quad f(x_1, ..., x_{p^\prime})\\ &\begin{aligned} subject\;to \quad &x_i\in \{0, 1\}, \qquad i=1, ..., p^\prime\\ &c_j(x_i, ..., x_{p^\prime})=0,\qquad j=1, ..., m^\prime\\ &d_k(x_1, ..., x_{p^\prime})\le0,\qquad k=1, ..., n^\prime \end{aligned} \end{aligned} ​minimizef(x1​,...,xp′​)subjectto​xi​∈{0,1},i=1,...,p′cj​(xi​,...,xp′​)=0,j=1,...,m′dk​(x1​,...,xp′​)≤0,k=1,...,n′​​

函數 f , c j , d j f, c_j, d_j f,cj​,dj​是多項式 in the integer valued variables x 1 , . . . , x p ′ x_1, ..., x_{p^\prime} x1​,...,xp′​

Transforming inequality constraints to equality constraints

因為我們不可以用不等式限制直接寫出 Ising Hamiltonians，我們需要把不等式限制轉換為等式限制。認為在有限精度下，總是可以講不等式限制轉換為等式限制用額外的整數變量，并不失去普遍性。

f ( x ) ≤ c → f ( x ) + s = c f ( x ) = ∑ i a i x i + ∑ i b i y i f ‾ ≤ f ( x ) ≤ f ‾ \begin{aligned} &f(x)\le c \rightarrow f(x)+s=c\\ &f(x)=\sum_ia_ix_i+\sum_ib_iy_i\\ &\underline{f}\le f(x) \le\overline{f} \end{aligned} ​f(x)≤c→f(x)+s=cf(x)=i∑​ai​xi​+i∑​bi​yi​f​≤f(x)≤f​​

x i ： x_i： xi​：二值變量

y i ： y_i： yi​：整數變量

a i , b i ： a_i, b_i： ai​,bi​：系數

c ： c： c：常數

s ： s： s：連續集 [ 0 , c − f ‾ ] [0, c-\underline{f}] [0,c−f​]取值的整數變量

同樣的： f ( x ) ≥ c → f ( x ) − s = c f(x)\ge c\rightarrow f(x)-s=c f(x)≥c→f(x)−s=c

s ： s： s：連續集 [ 0 , c − f ‾ ] [0, c-\overline{f}] [0,c−f​]取值的整數變量

通過以上方法引入附加整數變量 s s s，我們可以将非等式限制轉換為等式限制通過更少的的附加二值變量相比與現存的方法的整數變量 s s s

步驟2後等同的問題：

在步驟2後，所有的非等式限制被轉化為等式限制，新的二值變量被加入到問題中

m i n i m i z e f ( x 1 , . . . , x p ′ ′ ) s u b j e c t    t o x i ∈ { 0 , 1 } , i = 1 , . . . , p ′ ′ c j ( x i , . . . , x p ′ ′ ) = 0 , j = 1 , . . . , m ′ ′ \begin{aligned} &minimize \quad f(x_1, ..., x_{p^{\prime\prime}})\\ &\begin{aligned} subject\;to \quad &x_i\in \{0, 1\}, \qquad i=1, ..., p^{\prime\prime}\\ &c_j(x_i, ..., x_{p^{\prime\prime}})=0,\qquad j=1, ..., m^{\prime\prime}\\ \end{aligned} \end{aligned} ​minimizef(x1​,...,xp′′​)subjectto​xi​∈{0,1},i=1,...,p′′cj​(xi​,...,xp′′​)=0,j=1,...,m′′​​

f , c j f,c_j f,cj​是多項式函數in the binary variables x i , . . . x p ′ ′ x_i, ... x_{p^{\prime\prime}} xi​,...xp′′​。這樣的多項是也被稱為僞布爾函數(PBF)

Create an unconstrained optimization problem

下一步是将優化問題轉化為無限制優化問題

1. 平方等式限制
2. 用一個很大的權重 λ \lambda λ 将平方的等式限制加到目标函數當中
3. 這樣的參數 λ \lambda λ 總是存在的
4. 沒有其他的變量加到問題中

一個新的目标函數得到了

g ( x 1 , . . . , x p ′ ′ ) = f ( x 1 , . . . , x p ′ ′ ) + λ ∑ j = 1 m ′ ′ ( c j ( x 1 , . . . , x p ′ ′ ) ) 2 g(x_1, ..., x_{p^{\prime\prime}})=f(x_1, ..., x_{p^{\prime\prime}})+\lambda \sum_{j=1}^{m^{\prime\prime}}(c_j(x_1, ..., x_{p^{\prime\prime}}))^2 g(x1​,...,xp′′​)=f(x1​,...,xp′′​)+λj=1∑m′′​(cj​(x1​,...,xp′′​))2

在步驟3後，我們就得到了一個無限制僞布爾函數優化問題

m i n i m i z e g ( x 1 , . . . , x p ′ ′ ) s u b j e c t   t o x i ∈ { 0 , 1 } i = 1 , . . . , p ′ ′ \begin{aligned} &minimize\qquad g(x_1, ..., x_{p^{\prime\prime}})\\ &subject\,to\qquad x_i \in \{0, 1\}\qquad i=1, ..., p^{\prime\prime} \end{aligned} ​minimizeg(x1​,...,xp′′​)subjecttoxi​∈{0,1}i=1,...,p′′​

函數 g g g是一個僞布爾函數

Quadratization of the pseudo-boolean function

下一步是二次化。實作了如下

1. 得到了一個equivalent quadratic pseudo-boolean function(QPBF)
2. 引入了新的二值變量

二次化

對于僞布爾函數 g ( x 1 , . . . , x p ′ ′ ) g(x_1, ..., x_{p^{\prime\prime}}) g(x1​,...,xp′′​)，它的二次化是一個新的quadratic pseudo-boolean function h ( x 1 , . . . , x p ′ ′ , w 1 , . . . , w s ) h(x_1, ..., x_{p^{\prime\prime}}, w_1, ..., w_s) h(x1​,...,xp′′​,w1​,...,ws​)

g ( x 1 , . . . , x p ′ ′ ) = m i n w 1 , . . . , w s h ( x 1 , . . . , x p ′ ′ , w 1 , . . . , w s ) g(x_1, ..., x_{p^{\prime\prime}})=min_{w_1, ..., w_s}h(x_1, ..., x_{p^{\prime\prime}}, w_1, ..., w_s) g(x1​,...,xp′′​)=minw1​,...,ws​​h(x1​,...,xp′′​,w1​,...,ws​)

是以 g ( x 1 , . . . , x p ′ ′ ) g(x_1, ..., x_{p^{\prime\prime}}) g(x1​,...,xp′′​) 在 x 1 , . . . , x p ′ ′ x_1, ..., x_p^{\prime\prime} x1​,...,xp′′​ 的最小化和 h ( x 1 , . . . , x p ′ ′ , w 1 , . . . , w s ) h(x_1, ..., x_{p^{\prime\prime}}, w_1, ..., w_s) h(x1​,...,xp′′​,w1​,...,ws​) 在 x 1 , . . . , x p ′ ′ x_1, ..., x_p^{\prime\prime} x1​,...,xp′′​， w 1 , . . . , w p ′ ′ w_1, ..., w_p^{\prime\prime} w1​,...,wp′′​ 的最小化是等同的

正交化的政策是如下term-by-term quadratization

1. 每一個僞布爾函數的單項(monomial term)是正交分離的(quadratized separated)
2. 使用一個不同的新二值變量集去二次化每一個單項
3. 将所有的單項二次相加，得到原僞布爾函數的二次

原文：add all the monomial quadratizations to get the quadratization of the original pseudo-boolean function

1. 引入到問題中的新的二值變量的總數是為了使每個單項項二次化而引入的二進制變量的個數之和

原文：The total number of new binary variables introduced into the problem is the sum of the number of binary variables introduced to quadratize each monomial term

沒看懂？

沒關系，來個例子

• 假設我們想要二次化的函數是： g ( x 1 , x 2 , x 3 , x 4 ) = x 1 + 2 x 2 x 3 − x 1 x 2 x 3 − 3 x 1 x 2 x 3 x 4 g(x_1, x_2, x_3, x_4)=x_1+2x_2x_3-x_1x_2x_3-3x_1x_2x_3x_4 g(x1​,x2​,x3​,x4​)=x1​+2x2​x3​−x1​x2​x3​−3x1​x2​x3​x4​
• 頭兩項 x 1 x_1 x1​ 和 2 x 2 x 3 2x_2x_3 2x2​x3​ 已經quadratized
• 使 u ( x 1 , x 2 , x 3 , w 1 ) u(x_1, x_2, x_3, w_1) u(x1​,x2​,x3​,w1​) 為 − x 1 x 2 x 3 -x_1x_2x_3 −x1​x2​x3​ 的quadratization(隻有一個二值變量被需要)
• 使 v ( x 1 , x 2 , x 3 , x 4 , w 2 ) v(x_1, x_2, x_3, x_4, w_2) v(x1​,x2​,x3​,x4​,w2​) 為 − x 1 x 2 x 3 x 4 -x_1x_2x_3x_4 −x1​x2​x3​x4​ 的 quadratization(隻有一個二值變量被需要)
• 然後 g(x_1, x_2, x_3, x_4) 的 quadratization 就得到了通過二次僞布爾函數 h ( x 1 , x 2 , x 3 , x 4 , w 1 , w 2 ) = x 1 + 2 x 2 x 3 + u ( x 1 , x 2 , x 3 , w 1 ) + v ( x 1 , x 2 , x 3 , x 4 , w 2 ) h(x_1, x_2, x_3, x_4, w_1, w_2)=x_1+2x_2x_3+u(x_1, x_2, x_3, w_1)+v(x_1, x_2, x_3, x_4, w_2) h(x1​,x2​,x3​,x4​,w1​,w2​)=x1​+2x2​x3​+u(x1​,x2​,x3​,w1​)+v(x1​,x2​,x3​,x4​,w2​)

我們使用現在最知名的 quadratization schemes 去 quadratize 每一個單項

負單項

假設我們需要 quadratize 的負單項 − x 1 . . . x n -x_1 ... x_n −x1​...xn​，我們定義集合 S = { x 1 , . . . , x n } S=\{ x_1, ..., x_n\} S={x1​,...,xn​} 。 這樣一個就得到了單項的quadratization

− x 1 . . . x n = m i n w ∈ { 0 , 1 } ( ∣ S ∣ − 1 − ∑ x i ∈ S x i ) w -x_1...x_n=min_{w\in \{0, 1\}}(\mid S\mid-1-\sum_{x_i\in S}x_i)w −x1​...xn​=minw∈{0,1}​(∣S∣−1−xi​∈S∑​xi​)w

這個quadratization schemes添加了一個二值變量給每個負單項

正單項

假設我們需要 quadratize 的正單項。我們首先定義函數

G 1 = ∑ i = 1 n x 1 , G 2 = G 1 ( G 1 − 1 ) / 2 = ∑ i , j = 1 , j > i x i x j G_1=\sum_{i=1}^{n}{x_1, G_2}=G_1(G_1-1)/2=\sum_{i, j=1, j>i}{x_ix_j} G1​=i=1∑n​x1​,G2​=G1​(G1​−1)/2=i,j=1,j>i∑​xi​xj​

然後單項的 quadratization 為如下

x 1 . . . x n = G 2 + ( m i n w 1 , . . . , w k ∈ { 0 , 1 } ∑ i = 1 k w i ( c i , n ( − G 1 + 2 i ) − 1 ) ) x_1...x_n=G_2+(min_{w_1, ..., w_k\in \{0, 1\}}\sum_{i=1}^kw_i(c_{i, n}(-G_1+2i)-1)) x1​...xn​=G2​+(minw1​,...,wk​∈{0,1}​i=1∑k​wi​(ci,n​(−G1​+2i)−1))

其中 k = f l o o r ( n − 1 2 ) , a n d    c i , j = { 1 i f n i s o d d , a n d i = k 2 o t h e r w i s e k=floor(\frac{n-1}{2}), and\; c_{i, j}=\left\{ \begin{aligned} &1\quad if n is odd, and i=k\\ &2\quad otherwise \\ \end{aligned} \right. k=floor(2n−1​),andci,j​={​1ifnisodd,andi=k2otherwise​

這個quadratization schemes添加了新的二值變量。額外的變量大約為最初正單項數量的 1 2 \frac{1}{2} 21​

在步驟4之後，我們得到了一個無限制的僞布爾優化問題

m i n i m i z e h ( x 1 , . . . , x p ′ ′ , w 1 , . . . , w s ) s u b j e c t   t o x i ∈ { 0 , 1 } i = 1 , . . . , p ′ ′ w j ∈ { 0 , 1 } j = 1 , . . . , s \begin{aligned} &minimize\quad h(x_1, ..., x_{p^{\prime\prime}}, w_1, ..., w_s)\\ &\begin{aligned} subject\,to\quad &x_i\in \{0, 1\}\qquad i=1, ..., p^{\prime\prime}\\ &w_j\in\{0, 1\}\qquad j=1, ..., s \end{aligned} \end{aligned} ​minimizeh(x1​,...,xp′′​,w1​,...,ws​)subjectto​xi​∈{0,1}i=1,...,p′′wj​∈{0,1}j=1,...,s​​

這個函數 h h h是一個quadratic pseudo-boolean function (QPBF)

Determination of optimal values for subset of variables

最後一步是運作 a polynomial time algorithm 來尋找變量子集的最優值

1. 用的方法是roof duality and extended roof duality
2. 這個過程不會增加任何新的變量

在步驟5中

Step 5a：使用 roof duality 找到變量子集的最優值

• 運作 quadratic pseudo-boolean optimization(QPBO) algorithm
• This involves solving a flow optimzation problem on a graph

Step 5b：找到一些更多在 step 5a 中不能确定的變量的最優值。減少變量的數量通過知道那些變量有同樣的值在優化方案中

• Probing

Roof duality

• The quadratic pseudo-boolean optimization problem can be put in one-to-one corrrespondence with a capacitative network, where the capacities of the edges are related to the coefficients of the QPBF
• A max flow problem is solved using this capacitive network
• The solution of this max flow problem gives rise to cut, or partition of the nodes of the capacitative network
• This cut is used to infer which varibles have been fixed to their optimal values using the roof duality technique

(未完待續…)