在各行業(yè)應(yīng)用場(chǎng)景的數(shù)學(xué)模型構(gòu)建中，經(jīng)常會(huì)遇到實(shí)際問題的計(jì)算規(guī)模巨大，模型所包含的變量數(shù)超出現(xiàn)有量子計(jì)算機(jī)比特?cái)?shù)的情況，導(dǎo)致無法直接使用量子計(jì)算機(jī)進(jìn)行求解，而是先要對(duì)原問題進(jìn)行拆分，這時(shí)就需要一種稱為“subQUBO算法”的幫助。

subQUBO算法是一種將大規(guī)模組合優(yōu)化問題分解為若干個(gè)小規(guī)模問題以便能在當(dāng)前中小規(guī)模量子計(jì)算機(jī)上實(shí)現(xiàn)求解的方法。它的核心思想是通過軟件手段將原問題拆解，并融合經(jīng)典和量子兩種模型，重構(gòu)成一種“量子計(jì)算+經(jīng)典計(jì)算”混合架構(gòu)的全新數(shù)學(xué)模型，從而使得現(xiàn)有的光量子計(jì)算機(jī)能夠直接處理，同時(shí)，該算法可以確保被分解后的小問題集合在求解質(zhì)量上，仍舊與原有大問題是完全一致的。這項(xiàng)非常實(shí)用的模型預(yù)處理功能，也是玻色量子發(fā)布的開物SDK強(qiáng)大能力之一。

subQUBO算法的應(yīng)用場(chǎng)景主要集中在解決大規(guī)模優(yōu)化問題中，尤其是在受到當(dāng)前量子計(jì)算機(jī)比特?cái)?shù)限制而難以直接求解的問題上。例如，生物制藥領(lǐng)域的藥物發(fā)現(xiàn)和網(wǎng)絡(luò)科學(xué)領(lǐng)域的社區(qū)發(fā)現(xiàn)兩大典型場(chǎng)景案例。

藥物發(fā)現(xiàn)場(chǎng)景

藥物發(fā)現(xiàn)作為生物制藥領(lǐng)域的核心環(huán)節(jié)，致力于尋找對(duì)特定疾病具有療效的潛在藥物分子，包括了靶標(biāo)鑒定、藥物設(shè)計(jì)，合成、評(píng)價(jià)等多個(gè)步驟。其中，分子對(duì)接作為藥物發(fā)現(xiàn)早期虛擬篩選、藥物設(shè)計(jì)的重要技術(shù)手段之一，多被用于預(yù)測(cè)和分析配體（小分子化合物）與受體（蛋白質(zhì)或核酸）之間的結(jié)合過程。

通過計(jì)算配體受體之間的空間互補(bǔ)以及能量匹配來尋找其最佳的復(fù)合物模式。我們將分子對(duì)接過程中的構(gòu)象采樣問題轉(zhuǎn)化為配體原子和受體結(jié)合口袋的空間格點(diǎn)匹配問題，通過構(gòu)建QUBO模型可以在相干光量子計(jì)算機(jī)上實(shí)現(xiàn)求解，再將求得的解轉(zhuǎn)換為空間位置以最終獲得復(fù)合物pose信息，從而加速了分子對(duì)接的計(jì)算過程，并且還能有效的提高分子對(duì)接的規(guī)模和質(zhì)量。

但是，當(dāng)配體和受體的分子量較大時(shí)，或是可選的受體結(jié)合口袋較多時(shí)，原有的QUBO模型所包含的變量數(shù)也會(huì)隨之增加，這就對(duì)量子計(jì)算機(jī)的比特規(guī)模提出了更高的要求。這時(shí)我們通過subQUBO方法就可以從原QUBO問題中抽取出部分變量形成若干子問題，并通過迭代更新來優(yōu)化求解過程，使得分解后的問題求解結(jié)果能夠不斷逼近最優(yōu)解。

社區(qū)發(fā)現(xiàn)場(chǎng)景

網(wǎng)絡(luò)科學(xué)是利用數(shù)學(xué)理論研究數(shù)據(jù)網(wǎng)絡(luò)的學(xué)科，重點(diǎn)在于分析和表征網(wǎng)絡(luò)行為?，F(xiàn)實(shí)世界網(wǎng)絡(luò)的一個(gè)重要特征是它們具有社區(qū)結(jié)構(gòu)，這可以通過圖方法來實(shí)現(xiàn)建模。識(shí)別社區(qū)結(jié)構(gòu)是理解不同網(wǎng)絡(luò)結(jié)構(gòu)的重要手段，在社交網(wǎng)絡(luò)、金融風(fēng)控、生命科學(xué)等領(lǐng)域都有巨大應(yīng)用價(jià)值。

尤其在大規(guī)模網(wǎng)絡(luò)中，檢測(cè)社區(qū)結(jié)構(gòu)更加有價(jià)值，有許多應(yīng)用產(chǎn)品都是使用社區(qū)檢測(cè)算法來揭示網(wǎng)絡(luò)中的隱藏信息。例如，在社交網(wǎng)絡(luò)中找到具有相似行為的用戶，通過他們的購(gòu)物習(xí)慣對(duì)電子商務(wù)中的客戶進(jìn)行分類能夠有效提升營(yíng)銷成功率。同樣，社區(qū)檢測(cè)在設(shè)計(jì)延遲容忍網(wǎng)絡(luò)中的網(wǎng)絡(luò)協(xié)議和在線社交網(wǎng)絡(luò)中的蠕蟲遏制中能夠發(fā)揮重要作用。在數(shù)據(jù)網(wǎng)絡(luò)中，識(shí)別惡意用戶社區(qū)是很有幫助的。在智能營(yíng)銷中社區(qū)發(fā)現(xiàn)具有一些有趣的應(yīng)用，例如增強(qiáng)在線購(gòu)物者、產(chǎn)品推薦和定向廣告。在大型購(gòu)物網(wǎng)絡(luò)中，社區(qū)檢測(cè)可以用于分類客戶并根據(jù)他們的購(gòu)買歷史提供未來購(gòu)買的建議。

社區(qū)檢測(cè)算法的性能在很大程度上取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)可以是靜態(tài)的或動(dòng)態(tài)的。模塊度最大化和譜聚類分別被認(rèn)為是靜態(tài)網(wǎng)絡(luò)中社區(qū)識(shí)別的主要方法。我們將傳統(tǒng)的基于模塊度的社區(qū)發(fā)現(xiàn)模型轉(zhuǎn)化為QUBO形式，并使用玻色量子的相干光量子計(jì)算機(jī)實(shí)現(xiàn)了求解。而往往在實(shí)際場(chǎng)景中，在線網(wǎng)絡(luò)用戶數(shù)或者生命科學(xué)領(lǐng)域的細(xì)胞數(shù)量非常龐大，所涉及的計(jì)算規(guī)模都會(huì)超過現(xiàn)有量子比特?cái)?shù)量的限制，那么我們就可以借助subQUBO算法算法，進(jìn)行問題拆分，最終完成求解。

QUBO問題的分解 一個(gè)較大的QUBO優(yōu)化問題，在固定一部分變量的取值后，可以形成一個(gè)更小的QUBO優(yōu)化問題。

令原始的QUBO問題為：

令可活動(dòng)變量下標(biāo)集合為Sf。令固定的變量下標(biāo)集合為Sc=SSf，取值為

如此，原始的QUBO問題可改寫為以xi∈Sf為變量的問題：

其中，二次項(xiàng)為：

一次項(xiàng)為：

常數(shù)項(xiàng)為：

忽略常數(shù)項(xiàng)，則有：

相干光量子計(jì)算機(jī)直接求解的Ising模型和QUBO模型是等價(jià)的，在實(shí)現(xiàn)時(shí)直接對(duì)Ising模型抽取子問題也可以達(dá)到同樣的作用。優(yōu)化過程：

如偽代碼所示，通過subqubo優(yōu)化時(shí)，首先要確定初始解向量，之后的求解過程不斷更新解向量。之后的迭代過程中，需要執(zhí)行的操作包括子問題變量集合的選取，子問題的求解與更新答案，全局優(yōu)化。

子問題變量集合的選取：

變量集合的選取有很多不同的策略，策略的選取取決于實(shí)際問題。選取的策略包括：

（1）將QUBO問題看成一張圖，根據(jù)圖的連通性選擇子問題

（2）有限選擇重要的或者當(dāng)前不確定程度更高的變量

（3）根據(jù)實(shí)際問題的結(jié)構(gòu)選擇，如選擇在實(shí)際問題中相關(guān)的變量

子問題的求解與更新答案：

參考前一節(jié)問題的分解，我們?cè)谶x取變量集合之后就可以用原問題和當(dāng)前的解生成新的子問題。子問題的變量就是我們所選的變量集合。求解子問題之后，將變量的改變?cè)谠瓎栴}的解中做相應(yīng)的更新。有時(shí)subQUBO算法會(huì)維護(hù)一個(gè)解集合，這只需將新產(chǎn)生的解加入到解集合中并對(duì)維護(hù)的解集作相應(yīng)更新。

全局優(yōu)化

每次優(yōu)化都只考慮使用同一標(biāo)準(zhǔn)選取的一部分變量，有時(shí)候可能會(huì)導(dǎo)致算法錯(cuò)過一些變量。通過禁忌搜索，模擬退火等算法，引入不同的優(yōu)化方式，可以幫助跳出局部最優(yōu)。

子問題如何選??？

本節(jié)以選擇不確定程度更高的變量為例，講解子問題的選取過程。

當(dāng)被固定的變量都已經(jīng)得到最優(yōu)解，那么subQUBO表達(dá)式的最優(yōu)解與QUBO表達(dá)式的最優(yōu)解相同。因此，合理的方式應(yīng)該是將有更高概率已經(jīng)獲得正確解的變量固定，subQUBO表達(dá)式選取難以確定最優(yōu)解的變量。

于是，該方法通過之前求解時(shí)獲得的解來判斷每個(gè)變量當(dāng)前的解有多大信心為正確解，結(jié)果多數(shù)為1則為1，多數(shù)為0則為0，1和0的次數(shù)差不多說明難以確定。具體操作為通過 |解為1的次數(shù)-求解次數(shù)/2| 來判斷。

當(dāng)該值較大時(shí)，變量有較高信心為1或0的某一個(gè)值，反之則說明難以判斷該變量的值應(yīng)該為1或0，應(yīng)該優(yōu)先加入subQUBO。

總結(jié)

現(xiàn)實(shí)中的問題普遍存在大規(guī)模求解的情況，subQUBO算法為用戶提供了一種全新的解決思路，并證明其是一種用于解決大規(guī)模QUBO問題的有效方法。它通過將原始問題分解為多個(gè)子問題，并在迭代過程中優(yōu)化這些子問題的求解效果，從而逐步逼近全局最優(yōu)解。

在藥物發(fā)現(xiàn)和社區(qū)發(fā)現(xiàn)等實(shí)際應(yīng)用中，subQUBO算法能夠處理超出量子計(jì)算機(jī)比特?cái)?shù)限制的問題，提高了量子計(jì)算能夠覆蓋到的問題規(guī)模。并且子問題的選取策略也是多樣的，可根據(jù)實(shí)際問題特點(diǎn)選擇合適的變量集合。

顯然，通過結(jié)合經(jīng)典算法和量子計(jì)算，subQUBO算法為解決復(fù)雜優(yōu)化問題提供了新的思路和方法。基于玻色量子自研的開物SDK，用戶只需關(guān)注建立與場(chǎng)景所對(duì)應(yīng)的數(shù)學(xué)模型，SDK提供的方法可以自動(dòng)完成問題分解，用戶無需擔(dān)心其背后的復(fù)雜度，這將極大的降低用戶使用相干光量子計(jì)算機(jī)求解實(shí)際問題的難度。

文章來源 ：玻色量子 在此特別鳴謝！