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

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

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

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

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

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

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

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

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

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

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

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

令原始的QUBO問題為：

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

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

其中，二次項為：

一次項為：

常數(shù)項為：

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

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

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

子問題變量集合的選取：

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

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

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

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

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

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

全局優(yōu)化

每次優(yōu)化都只考慮使用同一標(biāo)準(zhǔn)選取的一部分變量，有時候可能會導(dǎo)致算法錯過一些變量。通過禁忌搜索，模擬退火等算法，引入不同的優(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)解的變量。

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

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

總結(jié)

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

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

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

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