量子小计算机能算调度优化小问题了

投稿 @ 2021.01.15 , 13:44

翻译:momo
来源:https://www.chalmers.se/en/departments/mc2/news/Pages/Tiny-quantum-computer-solves-real-optimisation-problem.aspx

量子计算机在特定问题的求解上是赢了常规计算机,可惜这些问题并无实际用途。下一步得让量子计算机干点有用的。查尔姆斯理工大学的研究人员就表示,他们的量子计算机虽然小但有用,能帮助求解实际的调度优化问题。

近年来,人们对建造量子计算机兴趣高涨,相关研究热火朝天。2019年,谷歌的研究团队取得了重大突破:他们的量子计算机求解比当时最好的超级计算机还快得多,美中不足是求解的问题没有任何实际用途——之所以选它也就是因为这个问题量子计算机容易算而常规计算机难算。因此,现在的重要任务是找些实际问题,常规计算机算不了,但是量子计算机可以解决。

查尔姆斯理工大学的量子计算机项目开始于2018年。项目负责人之一,理论物理学家Giulia Ferrini说:“我们想让正在开发的量子计算机早日解决实际问题,于是与产业界密切合作。”该项目的研究人员(包括一名来自航空物流公司Jeppesen的在职博士生)发现:量子计算机可以解决一个航空业问题的实例。

所有航空公司都面对调度问题。例如,如何为一架飞机分配航线就是一个调度优化问题。随着航线和飞机的数量增加,这个问题的规模和复杂性也会迅速增长。研究人员希望量子计算机能比常规计算机更擅长解决此类问题。量子计算机与常规计算机相比,基本组成单元在原理上完全不同。量子计算机的基本组成单元是量子位,很少的量子位就能处理相当多的信息。由于这种结构和功能上的差异,量子计算机必须以不同于常规计算机的算法编码。有种算法可以用在早期量子计算机上,叫做量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)。查尔姆斯研究小组已经在他们的量子计算机(一个只有两个量子位的处理器)上成功执行了该算法,并表明该算法能成功解决飞机航线分配问题。首次演示只涉及两架飞机,问题尺度非常小,因此可以轻松验证结果。

研究小组此举最先证明了QAOA算法能在实际中解决飞机航线分配问题。他们在算法运行上也比以往更进一步,做到这一点需要优良的硬件和精确的控制。“这证明我们已经有能力用量子处理器解决实际问题。我们现在用到的量子位还很少,但是它们运行得不错。我们的计划是首先确保在小规模上良好运行,然后再扩大规模。”负责实验设计的高级研究员Jonas Bylander说。Jonas Bylander也是查尔姆斯量子计算机项目的负责人之一。

研究小组的理论专家对同样的优化问题还模拟求解了多达278架飞机的情形,那将需要一台具有25个量子位的计算机。Giulia Ferrini说:“随着规模扩大,结果仍然很好。这表明QAOA算法有潜力解决更大规模的此类问题。”但是,要超越当今最好的计算机还需要更大的设备。查尔姆斯的研究人员已经开始扩大设备规模,目前正

(0)

相关推荐