2000 年，由美國克雷數(shù)學研究所提出、7 個“千禧年大獎難題”一一擺在了我們的面前：NP 完全問題、霍奇猜想、龐加萊猜想、黎曼猜想、楊-米爾斯存在性和質(zhì)量缺口、納衛(wèi)爾-斯托克方程和 BSD 猜想。

  隨著人類正式進入 21 世紀 20 年代，這份來自千禧之年的“數(shù)學大禮包”，是否有更多的可能被層層拆開？

  NP 完全問題排在百萬美元大獎的首位，足見其顯赫地位和無窮魅力。

  至少，一項出自麻省理工學院的成果展示了更好解決該問題的技術方案：在這項發(fā)表在 1 月Nature Communications 的研究中，麻省理工學院團隊開辟了用光子學解決 NP 完全問題的途徑。他們發(fā)明了一種新的算法，專門用于基于光子硬件探索 NP 完全問題。

圖丨此次論文（來源：Nature Communications）

  進入量子計算的“領地”

  從生物學研究到藥物發(fā)現(xiàn)再到路線優(yōu)化，大量科學工程學中遇到的優(yōu)化問題都可以簡化為 NP 完全問題。

  NP 完全問題是一類難度非常大的問題。但這類問題的神奇之處在于，問題之間是可以相互轉(zhuǎn)換的。即，如果你能解答一個問題，那你就能解出其它所有問題。

  例如，旅行商問題（TSP 問題，Travelling Salesman Problem）就是一個經(jīng)典的 NP 完全問題：假設一位旅行商人要拜訪 N 個城市，每個城市只能拜訪一次，最終還要回到出發(fā)城市，且路程為所有路徑之中的最小值。當 N=3，這是一個可以快速解答的問題，但是，如果 N 是一個上億的數(shù)字，無論對人腦還是機器而言，這個計算量都是相當之大。

  而如果能解 TSP 問題，相應的，你還可以同時解背包問題等 NP 完全問題。蛋白質(zhì)折疊、路徑優(yōu)化、數(shù)獨等，都屬于 NP 完全問題。

針對 NP 完全問題，目前尚無有效的最優(yōu)解法。從直覺上講，NP 完全問題“很難解決”，因為，解決問題所執(zhí)行的計算量與問題的范圍大小成指數(shù)關系。

圖丨證實或者證偽NP 完全問題 （來源：wiki）

  而在這項最新工作中，麻省理工學院的切入問題是 NP 完全伊辛問題（Ising problem）。

  “NP 完全問題有一系列問題，理論認為，任何兩個 NP 完全問題都是可以相互映射的。而伊辛問題本身也是一個 NP 完全問題。從理論上來說，我們求解伊辛問題的方式也可以被拿來嘗試求解很多其他的 Np complete 問題?！痹擁椦芯客ㄓ嵶髡?、曾在麻省理工學院從事博士研究的沈亦晨告訴 DeepTech。

  伊辛問題即對伊辛模型進行求解。伊辛模型最初是針對磁性系統(tǒng)建模而提出的，描述了電子指向向上或向下的自旋狀態(tài)，后被擴展為用以描述廣泛豐富的物理現(xiàn)象甚至社會經(jīng)濟活動，例如連續(xù)的量子相變、基本粒子的超弦理論、動力學臨界行為等。

  隨著伊辛模型從二維走向三維，如何更快更精準地對其進行求解成為了學術界的重大問題。量子退火比經(jīng)典計算更適合計算伊辛問題， 這個問題的長期存在也促進了這種新型計算（例如 D-Wave 的光學退火和量子退火機）和特殊算法（例如 “模擬退火” 之類的算法）的不斷創(chuàng)新。伊辛模型同樣也是量子計算領域的重要測試基準。

  事實上，設計新的光學計算機器也被認為是可行方法，即基于光信號對問題的解決方案進行編碼。不過，很長一段時間里，可用的小型化光子計算硬件、可充分展示光子計算硬件優(yōu)勢的專用算法都未能問世。

  但現(xiàn)在，麻省理工團隊不但針對伊辛問題成功開發(fā)基于光子硬件的算法，同時也做了相應的硬件驗證，用光束代替電子，利用光的信號強弱模擬電子的兩個自旋態(tài)。

  研究團隊表示，光子對于復雜問題優(yōu)化解決的效率要遠高于現(xiàn)有已經(jīng)實現(xiàn)的量子解決方案。

（來源：D-wave）

  “伊辛問題是一個通用的物理問題。幾百年前學者們已經(jīng)定義了它，目前相當一部分量子計算領域研究一直用它來展示量子計算的優(yōu)勢。

  此前的經(jīng)典計算和量子計算都可以去解決伊辛問題，但是沒有人針對光子計算機去開發(fā)解決伊辛問題的算法和硬件。我們發(fā)現(xiàn)，光子計算機在某些問題上或許是比量子計算和經(jīng)典電子計算更好的解決方案。

  新的算法利用了光學計算的全部優(yōu)勢——高頻率，低損耗、并行處理、低延時以及制造工藝所帶來的強大可伸縮性，并且規(guī)避了光學芯片的主要劣勢——單個計算精度不如數(shù)字電路高?！鄙蛞喑拷忉尩?，“更有趣的是，有些光計算的劣勢，比如天然的動態(tài)噪聲，反而在這類計算上幫助了我們更快地找到問題的答案”。

  光子這種求解伊辛問題的更優(yōu)能力，未來或可以幫助到生物技術公司或者共享出行公司。

  “作為 7 大數(shù)學難題之一的 NP 完全問題，是要證明（或者證偽）P=NP，既在 polynomial time limit 里解決 NP 完全問題，我們的光計算并沒有解決 P=NP 的問題，但是我們確實可以拿來更好得解決 NP complete 問題”，沈亦晨說。

  光學計算不應該局限在 AI 上

  近年來，純粹使用光子物理現(xiàn)象的光學計算架構(gòu)已成為諸多計算架構(gòu)創(chuàng)新中最具潛力候選者之一。

  此前業(yè)界對于光學芯片的關注，多源于其可能是最優(yōu) AI 計算硬件架構(gòu)——光的特性先天適合線性計算（AI 計算里最重要的部分），其中包含高維度的并行計算。過去幾年來，不少科技巨頭投資光學芯片創(chuàng)企，主要原因也在于此。

  但對于很多從事光學計算的研究者來說，他們可能并不希望將光學計算的場景局限在 AI 上。

  這次針對 NP 伊辛問題提出的光學算法創(chuàng)新，正是團隊希望擴展光學計算場景的一次嘗試。

  “一般來說，運行單獨的矩陣乘法，光學芯片可以比普通的電子芯片效果好成百上千倍，而在做卷積神經(jīng)網(wǎng)絡或者 AI 計算時，受于很多其他算子和內(nèi)存讀取方面的限制，這時全系統(tǒng)的優(yōu)勢可能只有十到幾十倍。但在伊辛問題上，光學芯片基本可以完全達到成百上千倍的優(yōu)勢，因為這類算法不需要太多的非線性的部分以及頻繁的內(nèi)存讀取。而且在論文中我們發(fā)現(xiàn)，噪聲在這類 Markov Chain Monte Carlo (MCMC)的算法里的必要性反而剛好利用了光作為模擬運算的劣勢。我們擴大了光學計算的應用場景”，他說。

（來源：Lightelligence）

  參與此次研究的沈亦晨，還是光學芯片公司 Lightelligence 的創(chuàng)始人、《麻省理工科技評論》于 2017 年評選出來的中國 “35 歲以下科技創(chuàng)新 35 人” 之一。Lightelligence 目前在沈亦晨的帶領之下全力研發(fā)光學芯片的相關技術，包含芯片設計、核心算法、傳輸、周邊應用等，欲打造一個完整的光學計算生態(tài)。用來求解伊辛問題的新算法，就可以跑在 Lightelligence 此前開發(fā)出的光學芯片原型板卡上。

  隨著研究的發(fā)表，新算法開發(fā)者之一、麻省理工學院的 Marin Soljai 教授也表示：“光學計算是一個非常古老的研究領域。因此，我們必須確定光子芯片在哪些方向可以施展拳腳。換句話說，我們必須確定當代光子學的研究價值取向?！?/span>

  研究生 Charles Roques-Carmes 補充道：“我們確定的是：（1）光學計算用于執(zhí)行快速且低成本的固定矩陣乘法；（2）用于執(zhí)行容許噪聲的計算。這兩個要素是我們工作的基石?！?/span>

  值得一提的是，在開發(fā)該算法并針對各種問題進行基準測試的過程中，研究人員發(fā)現(xiàn)了多種相關算法也可以在光子計算中實現(xiàn)，并且可以更快地找到解決方案。由此，沈亦晨也對光學計算的前景同樣充滿期待：“目前，利用集成光子技術提高計算能力正在蓬勃發(fā)展，我們相信這次的工作也會是諸多推動工作中的一部分。”

  目前，麻省理工學院的這支研究小組正在與其他研究者合作，以進行更多的光學算法概念驗證實驗并對基準測試。當然，這些新的嘗試還將繼續(xù)跑在光子而非電子上。

網(wǎng)站鏈接：https://mbd.baidu.com/newspage/data/landingsuper?context=%7B%22nid%22%3A%22news_8675381054904132145%22%7D&n_type=1&p_from=4

延伸閱讀：《千禧年大獎難題》（資料來源于百度百科）

千禧年大獎難題(Millennium Prize Problems), 又稱世界七大數(shù)學難題， 是七個由美國克雷數(shù)學研究所(Clay Mathematics Institute,CMI) 于2000年5月24日公布的數(shù)學猜想。根據(jù)克雷數(shù)學研究所訂定的規(guī)則，任何一個猜想的解答，只要發(fā)表在數(shù)學期刊上，并經(jīng)過兩年的驗證期，解決者就會被頒發(fā)一百萬美元獎金。

目錄：

1.P/NP問題

2.霍奇猜想

3.龐加萊猜想（俄羅斯數(shù)學家佩雷爾曼已解決，2010年）

4.黎曼假設

5.楊-米爾斯規(guī)范場存在性和質(zhì)量間隔假設

6.NS方程解的存在性與光滑性

7.貝赫和斯維訥通-戴爾猜想

P=NP?（P/NP問題）

  P是否等于NP的問題，即能用多項式時間驗證解的問題是否能在多項式時間內(nèi)找出解，是計算機與算法方面的重大問題，它是斯蒂文·考克（StephenCook）于1971年陳述的。

免責聲明：

網(wǎng)站內(nèi)容來源于互聯(lián)網(wǎng)，由網(wǎng)絡編輯負責審查，目的在于傳遞信息，提供專業(yè)服務，不代表本網(wǎng)站平臺贊同其觀點和對其真實性負責。如因內(nèi)容、版權問題存在異議的，請與我們?nèi)〉寐?lián)系，聯(lián)系方式：ahos@aiofm.ac.cn 。網(wǎng)站平臺將加強監(jiān)控與審核，一旦發(fā)現(xiàn)違反規(guī)定的內(nèi)容，按國家法規(guī)處理，處理時間不超過24小時。