你所在的位置: 首页 > 正文

用光挑战“世界7大数学难题”之首,MIT团队再证光学计算潜力

2020-02-25 点击:1901

2000年,美国克雷数学研究所提出的七个“千年奖”问题被一一呈现给我们:NP完全问题、霍奇猜想、庞加莱猜想、黎曼猜想、杨-米尔斯存在性和质量差距、纳维尔-斯托克斯方程和BSD猜想。

随着人类正式进入20世纪20年代,这个千年的“数学大礼袋”是否更有可能被一层层撕开?

NP完全问题在百万美元奖金中排名第一,显示了它的突出地位和无限魅力。

至少,麻省理工学院的一项成就展示了解决这个问题的更好的技术方案:在一月份发表在《自然通讯》上的这项研究中,麻省理工学院的团队开辟了一条用光子学解决NP完全问题的途径。他们发明了一种新算法,专门用于探索基于光子硬件的NP完全问题。

Chart本文(来源:自然通讯)

进入量子计算的“领域”。

从生物学研究到药物发现到路线优化,科学工程中遇到的许多优化问题都可以归结为NP完全问题。

NP完全问题是一种非常困难的问题。然而,这些问题的神奇之处在于它们可以相互转化。也就是说,如果你能解决一个问题,那么你就能解决所有其他问题。

例如,旅行推销员问题(TSP问题)是一个经典的NP完全问题:假设一个旅行推销员想要访问n个城市,每个城市只能访问一次,最后返回出发的城市,并且距离是所有路径中最小的。当N=3时,这是一个可以快速解决的问题。然而,如果n是数以亿计的数,这一计算量对人脑和机器来说都是相当大的。

如果你能解决TSP问题,相应地,你也能解决NP完全问题,如背包问题。蛋白质折叠、路径优化、数独等。都是NP完全问题。

NP完全问题没有有效的最优解。直觉上,NP完全问题是“很难解决的”,因为解决问题的计算量与问题的范围成指数关系。

Figure验证或证伪NP完全问题(来源:维基)

在这项最新的工作中,麻省理工学院的切入点问题是NP完全伊辛问题。

"NP完全问题有一系列的问题。理论认为任何两个NP完全问题都可以相互映射。伊辛问题本身是NP完全的。理论上,我们解决伊辛问题的方法也可以用来尝试解决许多其他Np完全问题。”《研究通讯》的作者、麻省理工学院的前博士研究员沈尘告诉DeepTech。

伊辛问题是解决伊辛模型。伊辛模型最初是为磁性系统建模而提出的,描述的是电子向上或向下的自旋状态。后来,它被扩展到描述各种丰富的物理现象甚至社会经济活动,如连续量子相变、基本粒子的超弦理论、动态临界行为等。

随着伊辛模型从二维走向三维,如何更快、更准确地求解已成为学术界的一个主要问题。量子退火比经典计算更适合计算伊辛问题。这个问题的长期存在也促进了这种新型计算(如D-Wave的光学退火和量子退火机)和特殊算法(如“模拟退火”算法)的不断创新。伊辛模型也是量子计算领域的一个重要基准。

事实上,设计一台新的光计算机也被认为是一种可行的方法,即根据光信号对问题的解决方案进行编码。然而,长期以来,能够充分展示光子计算硬件优势的小型化光子计算硬件和特殊算法一直没有出现。

但是现在,麻省理工学院的团队不仅成功地开发了一种基于光子硬件的伊辛问题算法,而且进行了相应的硬件验证,用光束代替电子,用光信号强度模拟电子的两种自旋状态。

研究小组说光子优化对于复杂问题的效率比现有的量子解决方案要高得多。

(来源:D波)

以前的经典计算和量子计算可以解决伊辛问题,但是没有人开发出算法和硬件来解决光子计算机的伊辛问题。我们发现光子计算机可能比量子计算和经典电子计算更能解决一些问题。

新算法利用了光计算的所有优点,如高频率、低损耗、并行处理、低延迟和制造过程带来的强大可扩展性,并避免了光芯片的主要缺点。单一的计算精度不如数字电路高。”沈尘解释道,“更有趣的是,光计算的一些缺点,如自然动态噪声,帮助我们在这样的计算中更快地找到问题的答案。“光子解决伊辛问题的更好能力可能有助于未来的生物技术公司或共享旅游公司。

"作为七大数学问题之一,NP-完全问题是证明(或证伪)P=NP,从而在多项式时限内解决NP-完全问题。我们的光学计算不能解决P=NP的问题,但是我们真的可以用它来更好地解决NP完全问题,”沈尘说。

光学计算不应局限于人工智能。

近年来,纯粹使用光子物理现象的光学计算架构已经成为许多计算架构创新的最有潜力的候选之一。

业界之前对光学芯片的关注大多源于这样一个事实,即它们可能是最佳的人工智能计算硬件架构。光学特性本质上适用于线性计算(人工智能计算最重要的部分),包括高维并行计算。在过去的几年里,许多技术巨头都投资了光学芯片来建立企业。这也是主要原因。

但是对于许多从事光学计算的研究人员来说,他们可能不想把光学计算的领域局限于人工智能。

针对NP-Ising问题提出的光学算法创新只是该团队扩展光学计算领域的一次尝试。

"一般来说,当运行单个矩阵乘法时,光学芯片的性能比普通电子芯片好几百或几千倍。然而,当进行卷积神经网络或人工智能计算时,它受到许多其他算子和存储器读取的限制。这时,整个系统的优势可能只有十到几十倍。然而,在伊辛问题上,光学芯片基本上可以实现成百上千倍的优势,因为这种算法不需要太多的非线性部分和频繁的内存读取。此外,本文还发现,这种马尔可夫链蒙特卡罗(MCMC)算法中噪声的必要性只是利用了光作为模拟运算的缺点。我们扩大了光学计算的应用,”他说。

(来源:lightligence)

参与这项研究的沈尘也是2017年由光学芯片公司lightligence的创始人评选的“35岁以下的35项技术创新”之一。目前,在沈尘的领导下,光明智能正在全力开发光芯片的相关技术,包括芯片设计、核心算法、传输、外围应用等。以创建一个完整的光计算生态。用于解决伊辛问题的新算法可以在光智能公司开发的光学芯片原型板上运行(参见DeepTech的前一份报告:《麻省理工科技评论》点击阅读)。

随着这项研究的发表,麻省理工学院的马林索亚,新算法的开发者之一?我?教授还说:“光计算是一个非常古老的研究领域。因此,我们必须确定光子芯片的使用方向。换句话说,我们必须确定当代光子学的研究价值取向。”研究生查尔斯罗克塞-卡姆斯补充道:“我们已经确定的是:(1)光学计算用于执行快速和低成本的固定矩阵乘法;(2)用于计算容许噪声。这两个要素是我们工作的基石。“值得一提的是,在开发算法和对各种问题进行基准测试的过程中,研究人员发现许多相关的算法也可以在光子计算中实现,并且可以更快地找到解决方案。因此,沈尘对光计算的未来也充满了期待:“目前,利用集成光子技术来提高计算能力正在蓬勃发展,我们相信这项工作将是许多推广工作的一部分。“目前,麻省理工学院的研究团队正与其他研究人员合作,进行更多的碳证据

亚心网 版权所有© www.xatst.com 技术支持:亚心网 | 网站地图