要解決棘手的最優化問題，只需增加激光器

2017年12月，美國航空公司乘務排班系統出現了一個小故障，險些擾亂了節日期間的幾千架航班。在沒有替補機長的情況下，這一錯誤導致機組人員只能停飛航班，波及多達1.5萬架次航班。雖然航空公司發現了這一問題，并安排了航班乘務人員，但這一混亂提醒我們，我們有多么依賴計算機來安排許多與社會息息相關的服務和功能。

例如，所有主要的航空公司都使用復雜的調度優化算法來分配機組人員。雖然美國航空公司事件的直接原因不是某個算法出現故障，但最終的結果是一樣的。在航空公司尋求解決方案時，這樣的錯誤可能會導致數十萬人滯留或導致嚴重不便。

解決眾多復雜的最優化問題，比如交通、物流和調度等，應當說是算法學和摩爾定律的勝利。沒有這些算法，現代世界將陷入嚴重癱瘓，比方說5萬艘貨船、2.5億億瓦時的發電量、每年1澤字節的互聯網流量等，它們的效率將大大降低。然而，由于時間緊張、計算資源不足，很多組織架構沒有采用最優方案。更重要的是，我們用于解決大量優化問題的方法仍有很大的改進空間。

考慮到最優化的重要性，而計算機處理器性能穩步大幅提高的時代似乎即將結束，研究人員已經開始探索如何利用專用的最優化設備來顯著提高解決復雜問題的能力。

一種很有前景的方法是開發光學最優化設備。7年前，山本喜久（Yoshihisa Yamamoto）帶領斯坦福大學的一個團隊（作者為成員之一）開始了此項研究?，F在，多個學術團隊和惠普實驗室、NTT基礎研究實驗室（NTT Basic Research Laboratories）的研究人員還在繼續研究。經過多年的工作，我們有理由相信，未來至少有一支團隊能夠制造出一臺設備，解決現代工業面對的極其復雜的最優化問題。

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

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

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

最優化遠不止旅行推銷員的問題，還有一個難題是安排競賽場次。例如，美國橄欖球聯盟（NFL）每年都要安排數百場比賽，同時還要遵守數千條規則，比如其中一條規則是，球隊不得連續打3場以上的客場比賽。2017年，為解決這一問題，美國橄欖球聯盟使用了將近400臺計算機。

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

━━━━

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

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

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

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

在伊辛模型中，將原子集合中每一對自旋電子之間的相互作用產生的能量相加。由于能量取決于自旋方向是否一致，所以該集合的總能量取決于系統中每個自旋的方向。所以，一般伊辛最優化問題就是確認自旋應該處在哪種狀態，能夠使系統總能量最低。

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

━━━━

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

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

我們的系統原型機之所以能將自旋映射為光脈沖，關鍵在于光參量振蕩器（OPO），一種類似于激光器的設備。與傳統的激光器不同，OPO產生的光與參考光恰好同相或反相。這正是我們需要來表示的二元自旋態（上或下）。我們可以以OPO產生的光與參考光同相表示“上旋”，以反相表示“下旋”。

使用OPO制造伊辛機的方式不止一種。NTT、加州理工學院、康奈爾大學、哥倫比亞大學等機構的團隊都在探索不同的途徑。而我們沿用的則是阿里雷扎?馬蘭迪（現在加州理工學院）在斯坦福大學領導的實驗中首次演示的伊辛原型機所使用的技術：光耦合時分多路復用OPO。

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

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

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

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

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

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

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

━━━━

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