模拟优化器更有利于解决变量巨大的复杂计算问题 | 广东省智能创新协会

发布日期:2019-06-25 10:00
假设您想要创造一个智能机器人,可以绘制旅行销售人员的路线或安排在国际机场的所有航班。也就是说,各种各样的问题非常复杂,变量的数量惊人。目前,克服这些优化问题数量的最佳方法仍然是功能强大的计算机。



但是,研究开发模拟优化器--操纵物理组件以确定优化解决方案的机器--可以深入了解使其与传统计算机竞争所需的内容。

为此,今天发表在Science Advances上的一篇论文提供了第一个实验证据,即高连通性或每个物理组件与其他物理组件直接交互的能力是这些新型优化机器的重要组成部分。“连接非常非常重要,这不是人们应该忽视的事情,” 参与该研究的斯坦福大学博士后研究员彼得麦克马洪说。

为了更好地掌握连通性的概念,想象一下著名的旅行营业员问题,其中有问题的销售人员试图绘制城市之间最有效的路线。具有最高连通性的问题的变化是每个城市通过高速公路直接连接到每个其他城市的世界。在现实世界中,情况并非如此--例如,您将使用相同的高速公路在大部分路线上从纽约市前往西雅图。

该论文的作者发现,模拟优化器在其组件之间具有更高的连接性,其性能越好。为此,研究人员将他们的机器,连贯的伊辛机器与由量子计算公司D-Wave制造的量子退火炉进行了比较。

“两者之间的主要区别在于连接差异,”同时为Ising机器上的IEEE Spectrum撰写的 McMahon说道。D-Wave的量子退火器使用量子比特来模拟被优化的问题,这通常使得仅可以直接连接相邻的量子比特并限制整体连接性成为可能。然而,相干的伊辛机器使用可以穿梭的光脉冲,使得任何两个感兴趣的脉冲可以直接相互作用。

通过在两种类型的优化问题(Sherrington-Kirkpatrick模型和MAX-CUT)上测试这两个系统,研究人员表明,对于具有高连通性的场景,相干的Ising机器优于量子退火炉。例如,伊辛机器比量子退火炉更快地解决了一个比较复杂的问题,即1000万倍(1.2毫秒与约167分钟相比)。

麦克马洪说,并不是说伊辛机器比量子退火机更好。“在每个问题上,连贯的伊辛机器并不比D-Wave机器快。”麦克马洪指出:“当你解决稀疏连接的问题时,实际上速度较慢。这很大程度上是两台机器如何解决问题的结果,并且机器仍然在4毫秒内解决了这些问题。” 

尽管如此,McMahon认为重要的一点是,更多连接对专业优化者来说是一个福音。他说,“在连贯的伊辛机器或量子退火炉之间进行选择更少,更多的是关于检查这些机器内有多少连接。没有人会抱怨更多的连接!”。