玻色量子“揭秘”之最大割（Max-Cut）問題與QUBO建模

Max-Cut問題簡單地說，就是求一種分割方法。給定一張無向圖, 將所有頂點(diǎn)分割成兩群, 同時(shí)使得被切斷的邊數(shù)量最大，或邊的權(quán)重最大。

QUBO（Quadratic Unconstrained Binary Optimization）問題即二次無約束二值優(yōu)化問題，將一個(gè)傳統(tǒng)問題轉(zhuǎn)為QUBO問題建模需要重點(diǎn)關(guān)注三部分：

①把建模對(duì)象中的變量映射為binary（0/1或者-1/+1）的變量；

②原模型的約束條件需要“處理”到目標(biāo)函數(shù)中，成為無約束問題；

③模型變量的最高次不超過二次。

我們先從簡單的問題開始說明，讓大家有些直觀感受。Max-Cut問題就是一個(gè)非常簡單，并容易理解的例子。同時(shí)Max-Cut問題無需復(fù)雜的操作，其模型本身就是QUBO問題。

最大割問題是一類NP難問題，它在計(jì)算機(jī)科學(xué)和組合優(yōu)化領(lǐng)域中有著廣泛的應(yīng)用。在量子計(jì)算領(lǐng)域，最大割問題是一個(gè)非常重要的Benchmark，因?yàn)樗橇孔佑?jì)算機(jī)中最具代表性的NP難問題之一，也是許多量子算法的基礎(chǔ)。同時(shí)，最大割問題在實(shí)際應(yīng)用中有著廣泛的應(yīng)用，如社交網(wǎng)絡(luò)分析、電路設(shè)計(jì)、圖像分割等領(lǐng)域。因此，通過研究量子算法解決最大割問題，可以為這些領(lǐng)域提供更高效的解決方案。

在量子計(jì)算行業(yè)中，不同公司往往將Max-Cut問題作為基礎(chǔ)案例進(jìn)行測試，用于算力的對(duì)比測試，而經(jīng)典計(jì)算中的很多代表性企業(yè)等都曾使用Max-Cut來做新品算力的標(biāo)定。如英偉達(dá)公司使用 896 個(gè) GPU 模擬 1688 個(gè)量子比特，能夠處理包含高達(dá) 3375 個(gè)頂點(diǎn)的圖最大割問題，Quantinuum 研究團(tuán)隊(duì)通過在20量子比特的Quantinuum H1-1量子處理器上進(jìn)行實(shí)驗(yàn)，可解決80個(gè)頂點(diǎn)的最大割問題。

2023年5月16日，北京玻色量子科技有限公司（以下簡稱“玻色量子”）的CTO魏海博士在首場新品發(fā)布會(huì)現(xiàn)場，就提出了Max-Cut是實(shí)用量子計(jì)算的“算力標(biāo)準(zhǔn)”。

Max-Cut問題是實(shí)用量子計(jì)算的“算力標(biāo)準(zhǔn)”

魏海博士提到，在實(shí)際問題求解中，玻色量子自研的相干光量子計(jì)算機(jī)真機(jī)——“天工量子大腦”，適用于高效求解組合優(yōu)化問題，其中最具代表性的21個(gè)NP-Complete模型（簡稱“NPC”）在我們的生活中無處不在。這些問題之間可以互相歸約轉(zhuǎn)化，技術(shù)中經(jīng)常用Max-Cut問題來做統(tǒng)一的數(shù)學(xué)表達(dá)，表征計(jì)算復(fù)雜度。因此，為了標(biāo)定量子計(jì)算的算力優(yōu)勢，我們采用在經(jīng)典計(jì)算中和量子計(jì)算中都通用的Max-Cut問題來作為實(shí)用量子計(jì)算的“算力標(biāo)準(zhǔn)”。

那么，為了更清楚的理解最大割問題，并徹底揭開它的“神秘面紗”，下面將通過案例對(duì)該問題在模型層面進(jìn)行全面解讀。

問題描述

最大割問題是NP完備問題。給定一張圖, 求一種分割方法, 將所有頂點(diǎn)分割成兩群, 同時(shí)使得被切斷的邊數(shù)量最大，或邊的權(quán)重最大。

由于二元變量存在（0/1或者-1/+1）表達(dá)形式的區(qū)別，常見模型有兩種建模思路，在這里分別進(jìn)行說明。

建模思路一

在無向圖G（V,E）中，V為網(wǎng)絡(luò)的頂點(diǎn)集合，E為網(wǎng)絡(luò)的邊集，其中點(diǎn)i,j∈V，（i,j）∈E，wij為頂點(diǎn)i,j間的邊的鄰接矩陣，有連邊關(guān)系則取1,無連邊關(guān)系則取0。決策變量σi，σj表示頂點(diǎn)i,j的分類，其可能的取值為{1,-1}，我們將V劃分為A、B兩類。

則在給定的無向圖中，將所有頂點(diǎn)分割成兩群的分割方法所對(duì)應(yīng)割取的邊的個(gè)數(shù)為Z，模型表示為:

式（1）即為Max-Cut最大割問題模型，同時(shí)其也是QUBO模型。

圖1：Max-Cut問題實(shí)例為描述該案例，本文以一個(gè)四節(jié)點(diǎn)實(shí)例說明，如圖1所示，通過觀察我們發(fā)現(xiàn)將1、2分為A類，3、4分為B類的“割”法將得到問題的最優(yōu)解4，如圖2所示，下面我們對(duì)這個(gè)案例進(jìn)行分析。

圖2：Max-Cut問題“割取”示意

通過連邊關(guān)系可知

當(dāng)點(diǎn)1、2為一組，點(diǎn)3、4為一組時(shí)，σ1=σ2=1，σ3=σ4=-1。 則式（3）變?yōu)?/p>

結(jié)合式（1）、（2）和（4）可得

圖1的最大割數(shù)量為4，符合我們的設(shè)想。

當(dāng)然，這個(gè)問題還可以簡化，細(xì)心的朋友發(fā)現(xiàn)wij為系數(shù)矩陣，并不影響模型的計(jì)算，所以模型式（1）可以轉(zhuǎn)換為求解式（6），式（1）與式（6）在解的取值上是等價(jià)的。

同時(shí)，式（6）也被理解為一種Ising模型的表達(dá)方式。

在該建模思路下，式（1）與式（6）均可理解為Max-Cut最大割問題模型，同時(shí)其也是QUBO模型。不同的是，式（1）的目標(biāo)函數(shù)可以表示為割去的邊的個(gè)數(shù)，式（6）的目標(biāo)函數(shù)常用于表示為哈密頓量。

建模思路二

思路1中二元變量通過-1/+1表示，同樣我們可以通過0/1變量構(gòu)建模型，我們用變量xi表示頂點(diǎn)i屬于A,B中的某一類。

則在給定的無向圖中，將所有頂點(diǎn)分割成兩群的分割方法所對(duì)應(yīng)割取的邊的個(gè)數(shù)為Z，模型表示為:

在該建模思路下，式（7）為Max-Cut最大割問題模型，同時(shí)其也是QUBO模型。式（7）與式（1）的目標(biāo)函數(shù)可以表示為割去的邊的個(gè)數(shù)。 我們可以試著用QUBO的矩陣表達(dá)來描述這個(gè)案例。 首先，式（7）等價(jià)于式（8）

QUBO的矩陣表達(dá)式為

其中，線性項(xiàng)決定了矩陣Q的主對(duì)角線上的元素，二次項(xiàng)決定了非對(duì)角線上的元素。

以圖1中的4節(jié)點(diǎn)，6條邊的案例為例

簡化后可得

則Q矩陣表達(dá)為

解決這個(gè)QUBO模型可以得到x={1,1,0,0}。因此頂點(diǎn)1和2在一個(gè)集合中，頂點(diǎn)3和4在另一個(gè)集合中，最大切割值為4。

問題拓展

有一個(gè)更普遍的問題版本稱為加權(quán)Max-Cut。在這個(gè)問題中，每個(gè)邊都有一個(gè)權(quán)重系數(shù)，目標(biāo)函數(shù)由最大化邊的個(gè)數(shù)調(diào)整為邊的總權(quán)重之和。

在上述例子中，問題特征直接自然構(gòu)建了QUBO形式的優(yōu)化問題。但許多其他問題需要“重鑄”來創(chuàng)建所需的QUBO形式。我們將在后面繼續(xù)介紹其他問題的QUBO建模及其求解。