理论计算机科学家约翰·卡尔劳克（左）和奥哈斯·帕雷克（Ojas Parekh）在桑迪亚国家实验室（Sandia National Laboratories）发现了量子计算机优于普通计算机的任务，这一概念称为量子优势。图片来源：克雷格·弗里茨

正如兔子从那里学到的那样，速度并不是一切。桑迪亚国家实验室和波士顿大学的理论计算机科学家发现，量子计算机在解决高级数学问题方面无与伦比。不同寻常的是，他们证明了量子计算机并不比普通计算机快;相反，它们使用的内存要少得多。

这一发现颠覆了传统观点，即量子计算机的价值在于它可以比普通计算机更快地解决某些问题。它还可以帮助研究人员为快速发展的技术找到更多实际用途。

“这是自然流问题的第一个指数量子优势，”桑迪亚的Ojas Parekh说，他是该团队的成员。

内存对任何计算机都很重要。它拥有的内存越多，它能解决的问题就越大。对于以量子比特存储信息的量子计算机来说，“空间真的很重要，因为很难构建具有大量量子比特的量子计算机，”Parekh说。

该团队在6月24日至28日在不列颠哥伦比亚省温哥华举行的计算理论研讨会上展示了他们的发现。数学证明可在arXiv预印本服务器上找到。

1994年，美国科学家彼得·肖尔（Peter Shor）证明了未来的量子计算机将能够以惊人的速度破解标准加密算法，震惊了世界。然而，在那之后的30年里，研究人员只发现了一些其他问题，这些计算机可以比普通计算机更快地解决。

桑迪亚大学和波士顿大学的研究现在指向了一个不同的领域，在那里量子优势是可能的。

“量子优势研究的大部分重点都集中在实现时间优势上，”波士顿大学计算机科学系的博士候选人Nadezhda Voronova说。“关于其他资源（如内存）的量子优势的研究相对有限。

将注意力转移到效率等其他属性上，可以帮助科学家找到量子计算机的更多实际用途。

“我们目前是否因为专注于或偏向于某些类型的问题而错过了重要的量子优势？”帕雷克说。

该团队主张的核心数学问题称为最大定向切割，意义重大，因为它是研究人员所说的自然问题。

“当我们谈论一个自然问题时，”来自桑迪亚的约翰·卡尔劳克（John Kallaugher）说，“我们的意思是，这是一个独立感兴趣的问题——人们已经在经典环境中研究它了。

Parekh进一步解释说，“最大定向切割问题相当于在网络中找到两组代理，其中从一组到另一组的通信最多。这个问题在网络安全和社交网络分析和设计中得到了应用。

随着此类问题变得越来越复杂，计算机通常需要更多的内存。但研究小组发现，量子计算机没有。它们的内存使用效率呈指数级提高，至少当数据到达流时是这样。当数据集太大而无法放入计算机内存或连续创建数据时，流式计算非常有用。

Kallaugher此前曾发表过一篇文章，量子计算机可能比他和他的团队现在证明的具有明显但更小的优势。指数比率的新发现意义重大，因为优势需要非常大，才值得花费时间和金钱来构建和运行量子计算机。

与Shor的算法一样，这一新发现仍然是理论上的，因为它尚未在计算机上得到证明。

最大定向切割本身并不是很有用。然而，这是高等数学中一个广为人知的优化问题，研究小组认为这暗示了量子计算机未来可能具有的各种实际用途。

“例如，在网络安全领域，有效地解决优化问题可以带来更好的资源分配，增强的事件响应策略和更准确的风险评估，”沃罗诺娃说。

Kallaugher补充说：“这可能为算法指明了道路，这些算法可以处理任何经典计算机都无法处理的问题。

“可能还有更多这样的算法，”沃罗诺娃推测道。

“真的，没有人知道完整的画面，”帕雷克说。

更多信息：John Kallaugher 等人，在流模型中近似最大定向切割的指数量子空间优势，arXiv （2023）。DOI： 10.48550/arxiv.2311.14123

期刊信息：arXiv