2000 年，由美国克雷数学研究所提出、7 个“千禧年大奖难题”一一摆在了我们的面前：NP 完全问题、霍奇猜想、庞加莱猜想、黎曼猜想、杨 - 米尔斯存在性和质量缺口、纳卫尔 - 斯托克方程和 BSD 猜想。随着人类正式进入 21 世纪 20 年代，这份来自千禧之年的“数学大礼包”，是否有更多的可能被层层拆开？
NP完全问题排在百万美元大奖的首位，足见其显赫地位和无穷魅力。一项出自麻省理工学院的成果展示了更好解决该问题的技术方案：在这项发表在 1 月 Nature Communications 的研究中， 麻省理工学院团队开辟了用光子学解决 NP 完全问题的途径。他们发明了一种新的算法，专门用于基于光子硬件探索 NP 完全问题。
进入量子计算“领地”
从生物学研究到药物发现再到路线优化，大量科学工程学中遇到的优化问题都可以简化为 NP 完全问题。
NP 完全问题是一类难度非常大的问题。但这类问题的神奇之处在于，问题之间是可以相互转换的。即，如果你能解答一个问题，那你就能解出其它所有问题。
例如，旅行商问题（TSP 问题，Travelling Salesman Problem）就是一个经典的 NP 完全问题：假设一位旅行商人要拜访 N 个城市，每个城市只能拜访一次，最终还要回到出发城市，且路程为所有路径之中的最小值。当 N=3，这是一个可以快速解答的问题，但是，如果 N 是一个上亿的数字，无论对人脑还是机器而言，这个计算量都是相当之大。
而如果能解 TSP 问题，相应的，你还可以同时解背包问题等 NP 完全问题。蛋白质折叠、路径优化、数独等，都属于 NP 完全问题。
针对 NP 完全问题，目前尚无有效的最优解法。从直觉上讲，NP 完全问题“很难解决”，因为，解决问题所执行的计算量与问题的范围大小成指数关系。
图丨证实或者证伪NP 完全问题 （来源：wiki）
而在这项最新工作中，麻省理工学院的切入问题是 NP 完全伊辛问题（Ising problem）。
“NP 完全问题有一系列问题，理论认为，任何两个 NP 完全问题都是可以相互映射的。而伊辛问题本身也是一个 NP 完全问题。从理论上来说，我们求解伊辛问题的方式也可以被拿来尝试求解很多其他的 Np complete 问题。”该项研究通讯作者、曾在麻省理工学院从事博士研究的沈亦晨告诉 DeepTech。
伊辛问题即对伊辛模型进行求解。伊辛模型最初是针对磁性系统建模而提出的，描述了电子指向向上或向下的自旋状态，后被扩展为用以描述广泛丰富的物理现象甚至社会经济活动，例如连续的量子相变、基本粒子的超弦理论、动力学临界行为等。
随着伊辛模型从二维走向三维，如何更快更精准地对其进行求解成为了学术界的重大问题。量子退火比经典计算更适合计算伊辛问题， 这个问题的长期存在也促进了这种新型计算（例如 D-Wave 的光学退火和量子退火机）和特殊算法（例如 “模拟退火” 之类的算法）的不断创新。伊辛模型同样也是量子计算领域的重要测试基准。
事实上，设计新的光学计算机器也被认为是可行方法，即基于光信号对问题的解决方案进行编码。不过，很长一段时间里，可用的小型化光子计算硬件、可充分展示光子计算硬件优势的专用算法都未能问世。
但现在，麻省理工团队不但针对伊辛问题成功开发基于光子硬件的算法，同时也做了相应的硬件验证，用光束代替电子，利用光的信号强弱模拟电子的两个自旋态。
研究团队表示，光子对于复杂问题优化解决的效率要远高于现有已经实现的量子解决方案。
（来源：D-wave）
“伊辛问题是一个通用的物理问题。几百年前学者们已经定义了它，目前相当一部分量子计算领域研究一直用它来展示量子计算的优势。
此前的经典计算和量子计算都可以去解决伊辛问题，但是没有人针对光子计算机去开发解决伊辛问题的算法和硬件。我们发现，光子计算机在某些问题上或许是比量子计算和经典电子计算更好的解决方案。
新的算法利用了光学计算的全部优势——高频率，低损耗、并行处理、低延时以及制造工艺所带来的强大可伸缩性，并且规避了光学芯片的主要劣势——单个计算精度不如数字电路高。”沈亦晨解释道，“更有趣的是，有些光计算的劣势，比如天然的动态噪声，反而在这类计算上帮助了我们更快地找到问题的答案”。
光子这种求解伊辛问题的更优能力，未来或可以帮助到生物技术公司或者共享出行公司。
“作为 7 大数学难题之一的 NP 完全问题，是要证明（或者证伪）P=NP，既在 polynomial time limit 里解决 NP 完全问题，我们的光计算并没有解决 P=NP 的问题，但是我们确实可以拿来更好得解决 NP complete 问题”，沈亦晨说。
光学计算不应该局限在 AI 上
近年来，纯粹使用光子物理现象的光学计算架构已成为诸多计算架构创新中最具潜力候选者之一。
此前业界对于光学芯片的关注，多源于其可能是最优 AI 计算硬件架构——光的特性先天适合线性计算（AI 计算里最重要的部分），其中包含高维度的并行计算。过去几年来，不少科技巨头投资光学芯片创企，主要原因也在于此。
但对于很多从事光学计算的研究者来说，他们可能并不希望将光学计算的场景局限在 AI 上。
这次针对 NP 伊辛问题提出的光学算法创新，正是团队希望扩展光学计算场景的一次尝试。
“一般来说，运行单独的矩阵乘法，光学芯片可以比普通的电子芯片效果好成百上千倍，而在做卷积神经网络或者 AI 计算时，受于很多其他算子和内存读取方面的限制，这时全系统的优势可能只有十到几十倍。但在伊辛问题上，光学芯片基本可以完全达到成百上千倍的优势，因为这类算法不需要太多的非线性的部分以及频繁的内存读取。而且在论文中我们发现，噪声在这类 Markov Chain Monte Carlo (MCMC)的算法里的必要性反而刚好利用了光作为模拟运算的劣势。我们扩大了光学计算的应用场景”，他说。
（来源：Lightelligence）
参与此次研究的沈亦晨，还是光学芯片公司 Lightelligence 的创始人、《麻省理工科技评论》于 2017 年评选出来的中国 “35 岁以下科技创新 35 人” 之一。Lightelligence 目前在沈亦晨的带领之下全力研发光学芯片的相关技术，包含芯片设计、核心算法、传输、周边应用等，欲打造一个完整的光学计算生态。用来求解伊辛问题的新算法，就可以跑在 Lightelligence 此前开发出的光学芯片原型板卡上（参加 DeepTech 此前报道：《沈亦晨：“光之魔术师”重新定义 AI 芯片 |“35 岁以下科技创新 35 人”中国榜单专栏》点击阅读）。
随着研究的发表，新算法开发者之一、麻省理工学院的 Marin Soljačić 教授也表示：“光学计算是一个非常古老的研究领域。因此，我们必须确定光子芯片在哪些方向可以施展拳脚。换句话说，我们必须确定当代光子学的研究价值取向。”
研究生 Charles Roques-Carmes 补充道：“我们确定的是：（1）光学计算用于执行快速且低成本的固定矩阵乘法；（2）用于执行容许噪声的计算。这两个要素是我们工作的基石。”
值得一提的是，在开发该算法并针对各种问题进行基准测试的过程中，研究人员发现了多种相关算法也可以在光子计算中实现，并且可以更快地找到解决方案。由此，沈亦晨也对光学计算的前景同样充满期待：“目前，利用集成光子技术提高计算能力正在蓬勃发展，我们相信这次的工作也会是诸多推动工作中的一部分。”
目前，麻省理工学院的这支研究小组正在与其他研究者合作，以进行更多的光学算法概念验证实验并对基准测试。当然，这些新的尝试还将继续跑在光子而非电子上。
