組合優(yōu)化問(wèn)題，在應(yīng)用數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)領(lǐng)域，指的是在一個(gè)有限的對(duì)象里集中找出最優(yōu)對(duì)象的一類(lèi)課題。這類(lèi)問(wèn)題特征是可行解的集是離散或者可以簡(jiǎn)化到離散結(jié)果，并且目標(biāo)是要找到最優(yōu)解。當(dāng)前，常見(jiàn)的組合優(yōu)化問(wèn)題通用版上包括旅行商問(wèn)題和最小生成樹(shù)，行業(yè)場(chǎng)景領(lǐng)域上涉及極大規(guī)模的集成電路設(shè)計(jì)、藥物設(shè)計(jì)和財(cái)務(wù)組合管理等問(wèn)題。

?

顯然，無(wú)論是金融、制藥或是財(cái)務(wù)等領(lǐng)域，組合優(yōu)化問(wèn)題都是最貼近科技賦能日常生活與工作的實(shí)用問(wèn)題之一，一旦有效解決這類(lèi)問(wèn)題，將會(huì)迅速提高我們的日常效率，而同時(shí)經(jīng)過(guò)了實(shí)驗(yàn)和市場(chǎng)論證的最優(yōu)解算工具就是“退火算法”。

組合優(yōu)化問(wèn)題的挑戰(zhàn)與解算方案

當(dāng)前，因?yàn)樵诮M合優(yōu)化問(wèn)題的解算中，窮舉搜索和枚舉法并不可行。其核心問(wèn)題主要在于理論分析中涉及了拓?fù)浞治?，所以在不同的拓?fù)湫螒B(tài)下，不同部分的約束關(guān)系就不同，算法也需要隨時(shí)調(diào)整。如果給定一個(gè)拓?fù)湫螒B(tài)，組合優(yōu)化往往就退化成一個(gè)整數(shù)優(yōu)化的問(wèn)題了，這樣有些問(wèn)題就可以比較簡(jiǎn)單的推理和解算了。

?

以組合優(yōu)化問(wèn)題之一的旅行商問(wèn)題（TSP）為例，最早的旅行商問(wèn)題的數(shù)學(xué)規(guī)劃是在1959年由Dantzig等人提出，它是最基本的最短路徑問(wèn)題，這也屬于組合優(yōu)化中的一個(gè)NP困難問(wèn)題。

?

具體的問(wèn)題描述為旅行商要到若干個(gè)城市旅行，各城市之間的費(fèi)用是已知的，為了節(jié)省費(fèi)用，旅行商決定從所在城市出發(fā)，到每個(gè)城市旅行一次后返回初始城市，那么他應(yīng)選擇什么樣的路線才能使所走的總費(fèi)用最短？當(dāng)城市數(shù)量增加時(shí)，問(wèn)題的復(fù)雜度會(huì)迅速的呈指數(shù)增加，如當(dāng)有30個(gè)城市時(shí)，用現(xiàn)在最快的超級(jí)計(jì)算機(jī)將所有可能的路線都嘗試一遍，也需要花幾十萬(wàn)年的時(shí)間。

此外，這類(lèi)問(wèn)題的衍生還可涉及到物流中的配送問(wèn)題，比如將n個(gè)客戶的訂貨沿最短路線全部送到，如何確定最短路線？一個(gè)廠房中n個(gè)不同工序之間如何排布？電路板上不同器件之間如何排列？諸如此類(lèi)都是組合優(yōu)化問(wèn)題中的實(shí)際問(wèn)題。

量子退火VS模擬退火

如上文所提，對(duì)于旅行商類(lèi)問(wèn)題的最優(yōu)化算法，目前常用的算法就是退火算法，分為模擬退火和量子退火兩種，模擬退火的方法已經(jīng)可以解決其中的很多問(wèn)題，只不過(guò)量子退火更勝一籌。

?

不過(guò)想要了解“模擬退火”“量子退火”，首先要知道什么是“退火”？“退火”本質(zhì)上是一種將金屬緩慢加熱到一定溫度并保持足夠時(shí)間，然后以適宜速度冷卻的金屬熱處理工藝。目的是對(duì)金屬材料和非金屬材料降低硬度，改善切削加工性，也可穩(wěn)定尺寸、減少變形與裂紋傾向以及消除組織缺陷。

?

拿半導(dǎo)體芯片來(lái)看，在經(jīng)過(guò)離子注入以后就需要退火，因?yàn)橥雽?dǎo)體中注入雜質(zhì)離子時(shí)，高能量的入射離子會(huì)與半導(dǎo)體晶格上的原子碰撞，使一些晶格原子發(fā)生位移，結(jié)果造成大量的空位，這會(huì)使得注入?yún)^(qū)中的原子排列混亂或者變成非晶區(qū)，所以在離子注入以后必須把半導(dǎo)體放在一定的溫度下進(jìn)行退火，以恢復(fù)晶體的結(jié)構(gòu)和消除缺陷。

?

顯然，“退火”解決的是材料在研制過(guò)程中的硬件工藝不穩(wěn)定問(wèn)題，而“模擬退火”“量子退火”則是解決組合優(yōu)化等數(shù)學(xué)計(jì)算中的非優(yōu)解問(wèn)題。

?

在20世紀(jì)80年代中期，貝爾實(shí)驗(yàn)室的研究人員斯柯特·柯克帕特里克(Scott Kirkpatrick)等人就開(kāi)發(fā)了模擬退火算法。它最初是為了通過(guò)模擬退火過(guò)程來(lái)更好地優(yōu)化集成電路芯片的設(shè)計(jì)而開(kāi)發(fā)，原理上可類(lèi)比“退火”，是一種通用概率算法，只不過(guò)是將熱力學(xué)理論套用到統(tǒng)計(jì)學(xué)上，常用來(lái)在一定時(shí)間內(nèi)尋找在一個(gè)搜尋空間中的近似最優(yōu)解。

?

量子退火就是通過(guò)超導(dǎo)電路、相干量子計(jì)算（CIM）實(shí)施激光脈沖等方式、以及基于模擬退火（SA）的相干量子計(jì)算，與數(shù)字電路，如現(xiàn)場(chǎng)可編程門(mén)陣列（FPGA）等一起實(shí)現(xiàn)的量子算法。

?

量子退火先從權(quán)重相同的所有可能狀態(tài)（候選狀態(tài)）的物理系統(tǒng)的量子疊加態(tài)開(kāi)始運(yùn)行，按照含時(shí)薛定諤方程開(kāi)始量子演化。根據(jù)橫向場(chǎng)的時(shí)間依賴(lài)強(qiáng)度，在不同的狀態(tài)之間產(chǎn)生量子穿隧，使得所有候選狀態(tài)不斷改變，實(shí)現(xiàn)量子并行性。當(dāng)橫向場(chǎng)最終被關(guān)閉的時(shí)候，預(yù)期系統(tǒng)就已得到原優(yōu)化問(wèn)題的解，也就是到達(dá)相對(duì)應(yīng)的經(jīng)典伊辛模型(Ising Model)基態(tài)。這就是量子退火機(jī)的應(yīng)用原理。

與模擬退火相比，在量子退火中，橫向場(chǎng)的強(qiáng)度決定了改變所有并行狀態(tài)量子幅的量子力學(xué)幾率，依據(jù)實(shí)驗(yàn)分析和數(shù)據(jù)結(jié)果，可以表明量子退火在某些條件下優(yōu)于模擬退火，但并不是完全替代和絕對(duì)碾壓。

?

顯然，與在傳統(tǒng)計(jì)算機(jī)上運(yùn)行的模擬退火算法不同，量子退火基于伊辛模型的算法以高度并行的方式進(jìn)行計(jì)算，并且對(duì)于大型問(wèn)題具有更好的可擴(kuò)展性。因?yàn)槟M退火運(yùn)行時(shí)間的長(zhǎng)短在很大程度上取決于組合優(yōu)化問(wèn)題的規(guī)模，但在基于伊辛模型進(jìn)行計(jì)算的情況下，計(jì)算時(shí)間基本保持不變，硬件大小根據(jù)問(wèn)題呈線性或二次方增長(zhǎng)。

?

因此，在組合優(yōu)化類(lèi)NP問(wèn)題的求解中，量子退火算法的一般結(jié)構(gòu)，更適用于求解max-SAT和最小multicut這類(lèi)問(wèn)題。

量子退火的應(yīng)用情況

提到量子退火的商業(yè)應(yīng)用——量子退火機(jī)，就不得不提到加拿大的一家量子計(jì)算機(jī)公司D-Wave。D-Wave商業(yè)銷(xiāo)售的量子計(jì)算機(jī)原理是用金屬鈮制成的微小電流環(huán)形成量子比特，直接實(shí)現(xiàn)量子退火現(xiàn)象，可以模仿量子計(jì)算中單一比特存儲(chǔ)大量數(shù)值的效果。值得注意的是，在商業(yè)應(yīng)用落地上，量子退火方法可以通過(guò)使用疊加狀態(tài)搜索各種可能性來(lái)有效地解決優(yōu)化問(wèn)題，有效滿足各大企業(yè)對(duì)于實(shí)際工作方案的提效與加速需求。

?

截至目前，D-Wave已在物流、人工智能、材料科學(xué)、藥物發(fā)現(xiàn)、網(wǎng)絡(luò)安全、故障檢測(cè)和財(cái)務(wù)建模等各個(gè)領(lǐng)域，構(gòu)建了250多款早期應(yīng)用程序。

具體應(yīng)用案例上，以早期采用 D-Wave 技術(shù)的大眾汽車(chē)公司為例，其使用量子混合求解器服務(wù)擴(kuò)展了量子用例，構(gòu)建了涂裝車(chē)間的調(diào)度應(yīng)用程序。相關(guān)算法旨在優(yōu)化汽車(chē)涂漆的順序，通過(guò)使用混合求解器服務(wù)，產(chǎn)線可顯著減少顏色切換的次數(shù)，以減少浪費(fèi)并提高產(chǎn)能。

?

2020年3月，D-Wave還開(kāi)放訪問(wèn)了旗下的量子云服務(wù)Leap，實(shí)現(xiàn)了實(shí)時(shí)量子計(jì)算的訪問(wèn)公開(kāi)化，以便合作伙伴隨時(shí)隨地能通過(guò)任何筆記本電腦來(lái)訪問(wèn)它的最強(qiáng)功能。例如Sigma-I正在創(chuàng)建現(xiàn)實(shí)世界的實(shí)際應(yīng)用程序，以面對(duì)醫(yī)療資源分配、員工調(diào)度、以及化解商業(yè)設(shè)施（比如電影院）擁堵等棘手挑戰(zhàn)；Menten AI率先用它來(lái)確定從頭開(kāi)始設(shè)計(jì)的蛋白質(zhì)結(jié)構(gòu)，并且針對(duì) COVID-19 的活病毒測(cè)試進(jìn)行了開(kāi)發(fā)。

?

雖然此前有人質(zhì)疑這家公司的產(chǎn)品不是真的量子計(jì)算機(jī)，但現(xiàn)在的D-Wave的量子退火機(jī)接受了市場(chǎng)的檢驗(yàn)并受到了社會(huì)對(duì)于其商業(yè)價(jià)值的大力肯定。

?

當(dāng)下，通用量子計(jì)算機(jī)的研發(fā)落地還處于上升期，而量子退火類(lèi)的專(zhuān)用量子計(jì)算機(jī)商業(yè)落地僅僅是一個(gè)開(kāi)始。例如，不同于D-Wave利用超導(dǎo)器件研發(fā)的量子退火機(jī)，由全球量子科技領(lǐng)域奠基人山本喜久教授主導(dǎo)，聯(lián)合日本電信電話株式會(huì)社和日本國(guó)立情報(bào)學(xué)研究所利用光學(xué)器件研發(fā)的量子計(jì)算設(shè)備，其可控的量子位數(shù)目已達(dá)5萬(wàn)個(gè)。而師承山本喜久教授的文凱博士，也是相干量子計(jì)算（CIM）方案的首位博士，現(xiàn)已回國(guó)創(chuàng)辦了量子計(jì)算科技公司玻色量子，并搭建了在通用量子計(jì)算機(jī)、專(zhuān)用量子計(jì)算機(jī)之外的第三種混合計(jì)算架構(gòu)：經(jīng)典計(jì)算機(jī)+量子AI架構(gòu)。

?

在量子計(jì)算產(chǎn)業(yè)落地上，正呈現(xiàn)著專(zhuān)用量子計(jì)算“一超多前”的商用態(tài)勢(shì)。隨著“量子信息”在我國(guó)國(guó)務(wù)院政府工作報(bào)告中的多次提出與強(qiáng)調(diào)，未來(lái)，國(guó)內(nèi)量子計(jì)算的商用落地也會(huì)未來(lái)可期。

文：慕一

編輯：王珩