一文了解如何應(yīng)用QUBO模型來建模

Ising模型與QUBO模型

1.伊辛模型(Ising Model)

相干伊辛機(jī)(Coherent Ising Machine, 簡稱CIM), 是目前玻色量子重點(diǎn)研發(fā)的一項(xiàng)光量子計(jì)算機(jī)技術(shù)，CIM是一種基于簡并光學(xué)參量振蕩器(DOPO)的光量子計(jì)算機(jī)，在數(shù)學(xué)實(shí)踐中, 我們可以將其抽象為優(yōu)化Ising模型的專用計(jì)算機(jī)。

Ising模型是一類描述物質(zhì)相變的隨機(jī)過程模型。抽象為數(shù)學(xué)形式為：

其中σ為待求自旋變量, 取值為{+1，-1}，H為哈密頓量，J和μ分別為二次項(xiàng)系數(shù)、線性項(xiàng)系數(shù), 是已知量。

2.區(qū)分

QUBO模型更便于建模，Ising模型可以用于CIM求解器直接求解。同時(shí)，QUBO模型和Ising模型之間可以互相轉(zhuǎn)化。

1）變量代換

2）創(chuàng)建輔助變量完成一次項(xiàng)轉(zhuǎn)化

QUBO模型建模秘籍

一、什么是組合優(yōu)化問題？

組合優(yōu)化(Combinatorial Optimization, CO)領(lǐng)域是優(yōu)化領(lǐng)域中最重要的領(lǐng)域之一，它也是運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和分析學(xué)研究團(tuán)體所追求的最活躍的研究領(lǐng)域之一。

組合優(yōu)化是在一個(gè)有限的對(duì)象集中找出最優(yōu)對(duì)象的一類問題。組合優(yōu)化的問題特征是可行解的集是離散或者可以簡化到離散的，目標(biāo)是找到最優(yōu)解。常見的例子有數(shù)字劃分問題、旅行商問題等。

一般來說，這些問題涉及在必須做出大量是/否決策的情況下做出明智的選擇，并且每一組決策都會(huì)產(chǎn)生相應(yīng)的目標(biāo)函數(shù)值，例如成本或利潤值。然而在這些環(huán)境中找到好的解決方案是極其困難的。

而QUBO建模方式可以包含在工業(yè)、科學(xué)和政府中發(fā)現(xiàn)的各種重要CO問題，借助QUBO求解器的求解能力可以有效地幫助解決許多重要問題。

二、什么是QUBO模型？

QUBO（QuadraticUnconstrained Binary Optimizatoin），無約束二次二進(jìn)制優(yōu)化模型是現(xiàn)在量子計(jì)算中應(yīng)用最廣泛的優(yōu)化模型，它統(tǒng)一了豐富多樣的組合優(yōu)化問題。

隨著問題規(guī)模的增加，利用傳統(tǒng)方法求解該問題，求解時(shí)間會(huì)變得不可接受，但利用QUBO模型可以通過量子計(jì)算機(jī)加速，高效求解組合優(yōu)化問題。同時(shí)，QUBO模型可以表達(dá)位運(yùn)算，進(jìn)而表達(dá)各種邏輯，操作簡便，具體形式如下。

1.基礎(chǔ)QUBO形式：minimize/maximize

Q為QUBO矩陣，x為二進(jìn)制變量組成的向量，每個(gè)變量取值均為{0,1}，QUBO目標(biāo)為找到使得y最小或最大的x

其中，Q矩陣的形式有2種：

1）對(duì)稱形式

2）上三角形式

舉例：

2.位運(yùn)算

與 同時(shí)為1，結(jié)果才為1；

或 同時(shí)為0，結(jié)果才為0；

非0變成1，1變成0；

異或 兩位相同為0，相異為1

位運(yùn)算表達(dá)

3.添加約束條件

舉例1：

通過添加約束項(xiàng)，并設(shè)置較大的系數(shù)P保證約束內(nèi)容的優(yōu)先級(jí)。

舉例2：

約束條件舉例

? ? ?

4.整數(shù)表達(dá)

通過二進(jìn)制表達(dá)整數(shù)，使用d個(gè)變量可以表達(dá)0到2^d ?1 的數(shù)字。

舉例：

5.不等式約束

不等式約束可以轉(zhuǎn)化為等式約束，通過松弛變量y表示出不等式兩邊的差。

其中y為通過二進(jìn)制表達(dá)的整數(shù)，構(gòu)造約束項(xiàng)：

（注意點(diǎn)：這樣做會(huì)引入新的變量，增加問題規(guī)模）

6.擴(kuò)展思考

HOBO問題（High Order Binary Optimization），是指用二次多項(xiàng)式難以表達(dá)的高次問題。對(duì)于高次的問題，可以將x1x2替換為y，并添加約束項(xiàng)使得x1x2=y，從而將高次的問題轉(zhuǎn)化為二次優(yōu)化問題。

約束項(xiàng)：Rosenberg多項(xiàng)式

滿足：

（注意點(diǎn)：這樣做會(huì)引入新的變量，增加問題規(guī)模）

三、QUBO可以解決哪些問題？

最大獨(dú)立集問題

不對(duì)稱分配問題

對(duì)稱分配問題

邊約束分配問題

二次背包問題

最大團(tuán)問題

最大割問題

整數(shù)劃分問題

旅行商問題

舉例1：整數(shù)劃分問題

1）整數(shù)劃分問題（The Number Partitioning Problem），NP-complete將包含n個(gè)非負(fù)整數(shù)的數(shù)集劃分為兩個(gè)子集，使這兩個(gè)子集的和盡可能接近

設(shè)數(shù)集為

選兩個(gè)子集滿足，使得下值最小

舉例S= {1，2，3，4，8}，一組最有解為S1= {1,8} S2={2,3,4}是一組最優(yōu)解，兩者的和均為9

2）整數(shù)劃分問題建模思路

1. 定義決策變量，決定每個(gè)整數(shù)被分到哪一個(gè)集合

2. 使用決策變量表達(dá)出兩個(gè)集合整數(shù)和的差值

3. 通過CIM優(yōu)化目標(biāo)函數(shù)，得到最小值對(duì)應(yīng)的解

3）整數(shù)劃分問題建模過程

定義決策變量xi，xi=1表示 Si∈S1，xi=0表示Si∈S2

兩個(gè)子集求和的差值：

目標(biāo)函數(shù)：

其中，

舉例2：旅行商問題

1）旅行商問題（Traveling Salesman Problem）NP-Complete，商人想要在地圖上走完所有城市，每個(gè)城市只經(jīng)過一次，最后回到最初的城市，求路程最短的走法。

給定帶權(quán)圖G(V,E)，V為點(diǎn)集，E為邊集，要求遍歷所有點(diǎn)再回到初始點(diǎn)，求路程最短的走法。哈密頓回路：遍歷所有點(diǎn)再回到初始點(diǎn)。

舉例：

2）旅行商問題建模思路1.0

以下圖為例，定義決策變量xi,u，表示“經(jīng)過的第i個(gè)節(jié)點(diǎn)為u”是否為真，通過決策變量表達(dá)出距離，再通過添加約束條件使得求解方案能夠成立，構(gòu)造得到表達(dá)式通過CIM進(jìn)行優(yōu)化。

目標(biāo)包括：

1. 路程最小

2. 路線為環(huán)（約束自然滿足）

3. 同時(shí)只能經(jīng)過一個(gè)節(jié)點(diǎn)（約束）

4. 每個(gè)點(diǎn)經(jīng)過次數(shù)為1（約束）

5. 不能走不存在的連接（約束）

3）旅行商問題建模過程

設(shè)有n個(gè)節(jié)點(diǎn)，wu,v從u到v的邊的邊權(quán)，定義決策變量xi,u，表示“經(jīng)過的第i個(gè)節(jié)點(diǎn)為u”是否為真，路程為環(huán)可以根據(jù)決策變量的定義自然滿足，則經(jīng)過的路程可以表達(dá)為：

4）旅行商問題約束條件

為使得xi,u符合實(shí)際情況，需要如下約束：

第i個(gè)節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)

節(jié)點(diǎn)u只在路線中出現(xiàn)一次

可以根據(jù)以上兩個(gè)條件構(gòu)造約束

為了保證不存在的邊不出現(xiàn)在方案中設(shè)置約束項(xiàng)

P為懲罰項(xiàng)系數(shù)，取值需要顯著大于其他邊權(quán)，最終的約束項(xiàng)：

目標(biāo)函數(shù)包括回路總長和約束兩部分：

2）旅行商問題建模思路2.0

定義決策變量xu,v，表示“使用u到v的邊”，通過決策變量表達(dá)出距離，再通過添加約束條件使得求解方案能夠成立，構(gòu)造得到表達(dá)式通過CIM進(jìn)行優(yōu)化。

目標(biāo)包括：

1. 路程最小

2. 每個(gè)點(diǎn)出發(fā)一次（約束）

3. 到達(dá)每個(gè)點(diǎn)一次（約束）

4. 不能走不存在的連接（約束）

由于相干光量子計(jì)算最擅長攻克組合優(yōu)化問題，可應(yīng)用賦能場景廣泛，如金融業(yè)的投資組合優(yōu)化、資本風(fēng)險(xiǎn)分析建模；生物制藥業(yè)的蛋白質(zhì)折疊、小分子組合和DNA重組；

交通物流行業(yè)路徑優(yōu)化等，這些都是在實(shí)際工作中經(jīng)常遇見的復(fù)雜度很高且計(jì)算量巨大的常規(guī)問題，所以該技術(shù)路線高度貼合市場需求，普適率高。

審核編輯：劉清