要解決棘手的最優(yōu)化問題，只需增加激光器

2017年12月，美國航空公司乘務(wù)排班系統(tǒng)出現(xiàn)了一個(gè)小故障，險(xiǎn)些擾亂了節(jié)日期間的幾千架航班。在沒有替補(bǔ)機(jī)長的情況下，這一錯(cuò)誤導(dǎo)致機(jī)組人員只能停飛航班，波及多達(dá)1.5萬架次航班。雖然航空公司發(fā)現(xiàn)了這一問題，并安排了航班乘務(wù)人員，但這一混亂提醒我們，我們有多么依賴計(jì)算機(jī)來安排許多與社會息息相關(guān)的服務(wù)和功能。

例如，所有主要的航空公司都使用復(fù)雜的調(diào)度優(yōu)化算法來分配機(jī)組人員。雖然美國航空公司事件的直接原因不是某個(gè)算法出現(xiàn)故障，但最終的結(jié)果是一樣的。在航空公司尋求解決方案時(shí)，這樣的錯(cuò)誤可能會導(dǎo)致數(shù)十萬人滯留或?qū)е聡?yán)重不便。

解決眾多復(fù)雜的最優(yōu)化問題，比如交通、物流和調(diào)度等，應(yīng)當(dāng)說是算法學(xué)和摩爾定律的勝利。沒有這些算法，現(xiàn)代世界將陷入嚴(yán)重癱瘓，比方說5萬艘貨船、2.5億億瓦時(shí)的發(fā)電量、每年1澤字節(jié)的互聯(lián)網(wǎng)流量等，它們的效率將大大降低。然而，由于時(shí)間緊張、計(jì)算資源不足，很多組織架構(gòu)沒有采用最優(yōu)方案。更重要的是，我們用于解決大量優(yōu)化問題的方法仍有很大的改進(jìn)空間。

考慮到最優(yōu)化的重要性，而計(jì)算機(jī)處理器性能穩(wěn)步大幅提高的時(shí)代似乎即將結(jié)束，研究人員已經(jīng)開始探索如何利用專用的最優(yōu)化設(shè)備來顯著提高解決復(fù)雜問題的能力。

一種很有前景的方法是開發(fā)光學(xué)最優(yōu)化設(shè)備。7年前，山本喜久（Yoshihisa Yamamoto）帶領(lǐng)斯坦福大學(xué)的一個(gè)團(tuán)隊(duì)（作者為成員之一）開始了此項(xiàng)研究?，F(xiàn)在，多個(gè)學(xué)術(shù)團(tuán)隊(duì)和惠普實(shí)驗(yàn)室、NTT基礎(chǔ)研究實(shí)驗(yàn)室（NTT Basic Research Laboratories）的研究人員還在繼續(xù)研究。經(jīng)過多年的工作，我們有理由相信，未來至少有一支團(tuán)隊(duì)能夠制造出一臺設(shè)備，解決現(xiàn)代工業(yè)面對的極其復(fù)雜的最優(yōu)化問題。

讓我們回顧一下“旅行推銷員”這一經(jīng)典問題：推銷員在不同城市之間旅行，推銷自己的商品，他不希望浪費(fèi)時(shí)間或是花費(fèi)不必要的錢購買汽油。這就是一個(gè)最優(yōu)化問題，目標(biāo)是為推銷員找到最短的路線，條件是，每座城市僅經(jīng)過一次，而且旅程結(jié)束時(shí)能夠回到他出發(fā)的城市。

如果只有5個(gè)城市，情況就比較簡單。只需考慮全部12條路徑，便可以解決問題。但是，如果我們勤勞的推銷員計(jì)劃去50個(gè)城市，這種蠻力的方法就不可行了，因?yàn)槁窂綌?shù)量將超過10的60次冪——也就是1后面有60個(gè)0。

利用各種捷徑和合理近似值的算法能夠?yàn)檫@個(gè)問題提供可用的解決方法。但即使是最好的算法，也可能拖垮一臺強(qiáng)大的計(jì)算機(jī)。最近的一個(gè)例子是，加拿大滑鐵盧大學(xué)嘗試找到《美國國家史跡名錄》（National Register of Historic Places）上近5萬個(gè)景點(diǎn)之間的最短路徑，并要證明答案正確，為此，310臺強(qiáng)大的處理器日夜不停地運(yùn)轉(zhuǎn)了9個(gè)月。

最優(yōu)化遠(yuǎn)不止旅行推銷員的問題，還有一個(gè)難題是安排競賽場次。例如，美國橄欖球聯(lián)盟（NFL）每年都要安排數(shù)百場比賽，同時(shí)還要遵守?cái)?shù)千條規(guī)則，比如其中一條規(guī)則是，球隊(duì)不得連續(xù)打3場以上的客場比賽。2017年，為解決這一問題，美國橄欖球聯(lián)盟使用了將近400臺計(jì)算機(jī)。

另外，工廠企業(yè)要安排設(shè)備維護(hù)，大學(xué)要按教室排課表，郵政服務(wù)要規(guī)劃送貨路線，大城市（如北京和東京）希望有效疏導(dǎo)上下班高峰期大街上的數(shù)百萬輛汽車。這些問題都涉及幾百甚至幾千個(gè)事件的安排。由于需要很多時(shí)間和計(jì)算機(jī)資源，在很多情況下，很難尋找到可行的方案。

━━━━

多年來，研究人員一直嘗試制造專用的設(shè)備來解決最優(yōu)化問題。20世紀(jì)80年代中期，阿里雷扎?馬蘭迪（Alireza Marandi）在美國電話電報(bào)公司貝爾實(shí)驗(yàn)室工作，約翰?霍普菲爾德（John hopfield）同時(shí)在貝爾實(shí)驗(yàn)室和加州理工學(xué)院工作，二人提出用模擬電子電路表示神經(jīng)網(wǎng)絡(luò)，解決旅行推銷員之類的最優(yōu)化問題。他們的論文引發(fā)了該領(lǐng)域長達(dá)十年的研究。其后在1994年，南加州大學(xué)的倫納德?阿德曼（Leonard Adleman）發(fā)現(xiàn)，理論上可以使用DNA解決這類問題。他的看法也引發(fā)了一陣研究潮。但是，所有這些工作都沒有找到解決最優(yōu)化問題的全新且有效的替代方法，迄今為止傳統(tǒng)計(jì)算機(jī)和技術(shù)仍是主流。

在斯坦福大學(xué)等地，制造專門的光學(xué)設(shè)備來解決最優(yōu)化問題的工作都圍繞著“伊辛最優(yōu)化”（Ising optimization）這一特定問題展開。這是以已故物理學(xué)家厄恩斯特?伊辛（Ernst Ising）命名的。伊辛最著名的工作是研究了一種磁矩模型，用來解釋不同磁狀態(tài)之間的切換。事實(shí)證明，人們發(fā)現(xiàn)很多常見的最優(yōu)化問題，包括調(diào)度和路徑尋找問題，都可以輕松轉(zhuǎn)化成伊辛最優(yōu)化問題。

要理解伊辛模型和最優(yōu)化之間的關(guān)聯(lián)，首先需要理解物理學(xué)家是怎樣使用這種模型理解磁性的。以條形磁鐵為例，在伊辛模型中，可以把條形磁鐵想象成一個(gè)三維原子格柵，其中每個(gè)原子都可以看成一個(gè)微型條形磁鐵。每個(gè)原子中的電子都有“自旋”屬性。根據(jù)慣例，價(jià)電子（即最外層電子）的自旋方向可分為向上或向下，它們的自旋方向決定了物質(zhì)是否已被磁化。如果所有的自旋都向上，則物質(zhì)已被磁化。如果所有的自旋都向下，物質(zhì)也已被磁化，但是極性相反。如果自旋有的向上、有的向下，則物質(zhì)沒有被磁化。

這些自旋之間也會發(fā)生相互作用。在條形磁鐵中，兩個(gè)相鄰電子會有一個(gè)總體“合并能量”；當(dāng)自旋方向一致，即都向上或都向下時(shí)，總能量較低；如果自旋方向相反，則總能量較高。

在伊辛模型中，將原子集合中每一對自旋電子之間的相互作用產(chǎn)生的能量相加。由于能量取決于自旋方向是否一致，所以該集合的總能量取決于系統(tǒng)中每個(gè)自旋的方向。所以，一般伊辛最優(yōu)化問題就是確認(rèn)自旋應(yīng)該處在哪種狀態(tài)，能夠使系統(tǒng)總能量最低。

在簡單模型中，僅認(rèn)為相鄰的自旋之間會相互作用。但在廣義的伊辛問題中，任何一個(gè)自旋都可能與其他自旋相互作用，不論二者之間相距多遠(yuǎn)，而且這一相互作用的跡象和強(qiáng)度可能是唯一的。問題到了這種程度時(shí)，就很難找到解決方案了，如同要為訪問上萬個(gè)潛在買家的推銷員尋找路線一樣。如果我們能夠找到快速解決伊辛最優(yōu)化問題的方法，并且能以考慮伊辛問題的方式思考旅行推銷員等問題，或許就能夠更快地解決這類問題。伊辛問題中的最低能狀態(tài)將能夠表示各城市之間的最快路徑、安排貨輪運(yùn)輸?shù)淖罴逊桨?，以及我們需要的其他最?yōu)化方案。

━━━━

那么實(shí)踐中如何把旅行推銷員路線轉(zhuǎn)化成自旋呢？關(guān)鍵在于映射：我們要將最優(yōu)化問題轉(zhuǎn)化為專用設(shè)備可以解決的伊辛最優(yōu)化問題。首先要做的就是，將原始的最優(yōu)化問題（比如吸塵器推銷員尋找路線的問題）通過映射表示為一組自旋，并定義自旋之間如何相互影響。感謝計(jì)算機(jī)科學(xué)家和運(yùn)籌學(xué)家在過去數(shù)十年間所做的研究，多種優(yōu)化問題對伊辛形式的映射已經(jīng)完成。

但是，單個(gè)原子和電子自旋很難共事，所以我們的工作重點(diǎn)在于制造一臺能夠以光脈沖代替電子自旋實(shí)現(xiàn)伊辛模型的設(shè)備。這樣，伊辛問題便映射為脈沖和脈沖之間的相互作用。我們依據(jù)問題的總能量來評估結(jié)果，最低能狀態(tài)為最佳方案。然后，將這一結(jié)果轉(zhuǎn)化成原始問題的含義，比如我們勤勞推銷員的最短路線。

我們的系統(tǒng)原型機(jī)之所以能將自旋映射為光脈沖，關(guān)鍵在于光參量振蕩器（OPO），一種類似于激光器的設(shè)備。與傳統(tǒng)的激光器不同，OPO產(chǎn)生的光與參考光恰好同相或反相。這正是我們需要來表示的二元自旋態(tài)（上或下）。我們可以以O(shè)PO產(chǎn)生的光與參考光同相表示“上旋”，以反相表示“下旋”。

使用OPO制造伊辛機(jī)的方式不止一種。NTT、加州理工學(xué)院、康奈爾大學(xué)、哥倫比亞大學(xué)等機(jī)構(gòu)的團(tuán)隊(duì)都在探索不同的途徑。而我們沿用的則是阿里雷扎?馬蘭迪（現(xiàn)在加州理工學(xué)院）在斯坦福大學(xué)領(lǐng)導(dǎo)的實(shí)驗(yàn)中首次演示的伊辛原型機(jī)所使用的技術(shù)：光耦合時(shí)分多路復(fù)用OPO。

這名字讀起來有點(diǎn)拗口，我們來拆解一下。從脈沖激光源開始。激光源向兩個(gè)方向同步發(fā)出皮秒光脈沖。第一個(gè)將成為參考脈沖，自身分成獨(dú)立的兩支；這在我們后續(xù)的說明中非常重要。

第二個(gè)作為OPO的能量源，激發(fā)OPO晶體發(fā)射光子脈沖。每個(gè)OPO脈沖都被注入纏繞的光纖環(huán)路中，光纖一般至少幾百米長，具體取決于需要的脈沖數(shù)量?？梢韵虼斯饫w環(huán)路中注入成百上千個(gè)脈沖，一個(gè)追一個(gè)，一次又一次地穿過晶體。

這些OPO脈沖的相位代表伊辛模型中的自旋。但在它們在產(chǎn)生之初，在環(huán)路中多次傳輸之前，強(qiáng)度太弱，其相位不易判別。所以我們迫使這些脈沖相互作用，最終產(chǎn)生它們的終極相位和伊辛問題的答案。

還記得前面說的參考光嗎？在環(huán)路的某個(gè)點(diǎn)上，一個(gè)光纖分支器取出每個(gè)脈沖的一小部分，在檢波器中將這一小部分與參考脈沖比較。檢波器會輸出一個(gè)電壓，其中包含了脈沖的相位和振幅。這一信號轉(zhuǎn)化成數(shù)字之后，輸入到現(xiàn)場可編程門陣列（FPGA）中。這里就出現(xiàn)了伊辛問題。

前面說過，解決伊辛問題就是尋找一組自旋的最低能狀態(tài)；這種狀態(tài)下，自旋之間的相互作用各有不同，這些相互作用對系統(tǒng)總能量做出的貢獻(xiàn)也有所不同。在OPO中，每個(gè)脈沖都代表一個(gè)自旋。所以FPGA依據(jù)伊辛問題對每個(gè)自旋——我們在設(shè)置中使用了100個(gè)自旋——進(jìn)行了計(jì)算，計(jì)算包括對目標(biāo)自旋產(chǎn)生影響的所有脈沖的測量記錄。然后，處理器將計(jì)算結(jié)果調(diào)節(jié)強(qiáng)度調(diào)制器和相位調(diào)制器，二者皆位于參考脈沖經(jīng)過的一條分支上。此后，將新修改的參考脈沖輸入OPO脈沖快速經(jīng)過的光纖環(huán)路中。

時(shí)機(jī)非常重要——我們希望確保修改后的參考脈沖能與正確的OPO脈沖結(jié)合。如果能做到，兩者就會混合。根據(jù)兩個(gè)脈沖是否同相，在輸入脈沖的驅(qū)動下，OPO脈沖可表示電子的上旋或下旋。

我們對環(huán)中的每個(gè)OPO脈沖重復(fù)整個(gè)過程；或許要沿環(huán)路走幾十或幾百次才能使所有的脈沖都達(dá)到最終相位狀態(tài)。在這之后，用單獨(dú)一臺計(jì)算機(jī)讀取這組相位，解讀成伊辛問題中的上旋或下旋電子，然后翻譯成一個(gè)所希望解決的原始問題方案。

━━━━

我們在實(shí)驗(yàn)中先后制作了4自旋和16自旋的時(shí)分多路復(fù)用OPO系統(tǒng)。這些系統(tǒng)大都采用了硬連線的方式，將問題解碼為一組特定長度的光纖分支。我們在這些實(shí)驗(yàn)中成功找到了最低能狀態(tài)，受此激勵，又對此方法展開了進(jìn)一步研究。2016年，我們制作了一臺具備FPGA反饋的設(shè)備，可以解決含有100個(gè)自旋的伊辛問題。對比其他專用系統(tǒng)，比如NASA的“量子退火爐”，我們相信，OPO伊辛機(jī)很可能會成為有效的優(yōu)化器。實(shí)驗(yàn)結(jié)果令人鼓舞，但我們還有很多東西要學(xué)，現(xiàn)在還不能斷言這種光學(xué)方式一定能夠超越傳統(tǒng)的處理器來實(shí)際解決最優(yōu)化問題。利用光量子態(tài)或許可以提高這種設(shè)備解決問題的能力，但是光量子態(tài)很難模擬。我們才剛開始著手解決許多問題，希望在未來的幾年中，隨著這種新型計(jì)算機(jī)器的開發(fā)，我們還將探索理論和實(shí)驗(yàn)之間令人興奮的相互作用。