MIT 開發光子演算法,試圖解決世界 7 大數學難題的「NP 完全問題」

示意圖,非文中 MIT 所使用的光學運算元件。

2000 年 5 月,美國克雷數學研究所(Clay Mathematics Institute,CMI)提出 7 個數學難題,稱為「千禧年大獎難題」,挑戰者每解出 1 道題目,若通過兩年驗證期和專家小組審核,就可以獲得 100 萬美元(約新台幣 3050 萬元)的獎金。

其中,P/NP 問題 是當中的一道難題,而「NP 完全問題」是 P/NP 問題裡的一道關鍵題。近期,麻省理工學院(MIT)的研究團隊在 Nature Communications 發表解決這道難題的技術方案。他們開發新的光子運算演算法,使用光子運算的硬體設備,試圖解決 NP 完全問題。

優化類型的問題可簡化為 NP 完全問題,但人類目前沒有最佳解答方法

P/NP 問題是理論電腦科學中的重要難題,這道問題包含了複雜度類別 P 與 NP 的關係;1971 年,Stephen A. Cook 和 Leonid Levin 提出了這道問題:

複雜度類別 P 和 NP 是否恆等?(P = NP?)

但要解決 P 是否恆等於 NP 的問題,會用到 NP 完全的概念,但 NP 完全問題也是一道「難題」。NP 完全問題的範圍很廣,不管是路徑優化還是藥物開發,只要是與優化相關的問題,都可簡化為 NP 完全問題。

TSP 問題(Travelling Salesman Problem,旅行推銷員問題)是 NP 完全問題裡的一道經典題。TSP 問題是這樣的:假設有一個商人要拜訪 N 個城市,每個城市只能拜訪一次,而且最後要回到出發的城市,那麼他應該以怎樣的順序拜訪這 N 個城市,才能夠讓總路程最小?如果只有 3 個城市,我們可以很快找到答案;但如果有 1 萬個城市,就需要相當龐大的運算。

從以上的案例可以看到,問題範圍愈大,解決問題所需的運算量也會增加,而且是指數等級的爆量。人類目前並沒有解答 NP 完全問題的最佳方法。

MIT 開發光子運算的演算法,試圖解決 NP 完全問題

而 MIT 從 NP 完全問題裡的易辛問題(Ising Problem)切入,開發光子運算的演算法。 易辛模型(Ising Model)最初是針對磁性系統建立的模型,後來拓展到更多物理現象的描述,是一個通用的物理問題。

目前易辛模型被應用於量子運算的測試基準,但 MIT 團隊認為,光子對於複雜問題的解決效率高於現有的量子解決方案。MIT 團隊針對易辛問題,開發了光子運算的演算法,用光子代替電子,透過光的信號強弱,模擬電子的兩個自旋態。

光學運算有高頻率、低損耗、並行處理、低延遲等優勢

目前傳統演算法和量子演算法都能解決易辛問題,但 MIT 是首個開發解決易辛問題的光子運算演算法的團隊。根據中國媒體《DeepTech 深科技》的 報導 ,光學運算具有高頻率、低損耗、並行處理、低延遲等優勢,而 MIT 的演算法則規避了光學晶片的主要缺點:計算精度不如電子電路。

目前光子運算架構是眾多創新演算架構的候選。光的物理特性適合用於線性運算,其中包含高維度的平行運算(parallel computing),未來可能應用於 AI 硬體架構。雖然 MIT 的光子演算法並沒有解決 P 和 NP 是否恆等的問題,但它提供一個方案,可用於 NP 完全問題的求解,提升人類的數學知識;此外,光子運算未來也可能應用在其他領域,提升人類的科研技術力。

參考資料來源:
1.《DeepTech 深科技》:〈 用光挑战 “世界 7 大数学难题” 之首,麻省理工团队再证光学计算潜力
2.《Photonics Media》:〈Heuristic Approach Uses Photonics to Solve Complex Problems Fast
3.《RLE》:〈Solving complex problems at the speed of light
(本文提供合作夥伴轉載。首圖來源:pikrepo CC Licensed

延伸閱讀

工程師別惹怒數學家!25 年前,「布朗常數」讓英特爾賠 145 億台幣
集結 50 萬台電腦算力,數學家終於破解困擾 65 年的難題:三立方數和
教你如何用 Python 的平行運算,驗證數學界的百年難題「哥德巴赫猜想」


針對「網管」問題一次說明白!

轟動 CES 大展的  Wi-Fi 6 是什麼?

馬上了解

點關鍵字看更多相關文章: