自然流问题的第一个指数量子优势

Josiah02 · 发表于 2024-7-6 13:32:42

正如兔子从乌龟那里学到的，速度并不是一切。桑迪亚国家实验室和波士顿大学的理论计算机科学家发现，量子计算机在解决高级数学问题方面无与伦比。不同寻常的是，他们证明量子计算机并不比普通计算机快，相反，它们占用的内存要少得多。
这一发现颠覆了人们的传统观念：量子计算机的价值在于它能比普通计算机更快地解决某些问题。它还可以帮助研究人员为这一快速发展的技术找到更多实际用途。
“这是自然流问题的第一个指数量子优势，”团队成员桑迪亚的 Ojas Parekh 说。
内存对于任何计算机来说都很重要。内存越大，解决的问题就越大。对于以量子比特存储信息的量子计算机来说，“空间真的很重要，因为构建具有大量量子比特的量子计算机非常困难，”Parekh 说。
该团队在 6 月 24 日至 28 日于不列颠哥伦比亚省温哥华举行的计算理论研讨会上展示了他们的研究成果。数学证明可在arXiv预印本服务器上找到。
量子计算机的价值可能在于内存效率，而不仅仅是速度
1994 年，美国科学家彼得·肖尔 (Peter Shor) 证明未来的量子计算机将能够以惊人的速度破解标准加密算法，震惊了世界。然而，此后 30 年来，研究人员只发现了少数几个量子计算机能够比普通计算机更快解决的问题。
桑迪亚大学和波士顿大学的研究现在指出了可能存在量子优势的不同领域。
波士顿大学计算机系博士生纳德日达·沃罗诺娃 (Nadezhda Voronova) 表示：“量子优势研究的重点主要放在实现时间优势上。相对于内存等其他资源，量子优势的研究相对有限。”
将注意力转移到效率等其他属性上，可以帮助科学家找到量子计算机的更多实际用途。
“我们目前是否因为专注于或偏向某些类型的问题而错失了重要的量子优势？”帕雷克说。
什么是自然流问题以及它为何重要
该团队声称的核心数学问题称为最大有向切割，它很重要，因为它是研究人员所称的自然问题。
桑迪亚国家实验室的约翰·卡拉格说：“当我们谈论一个自然问题时，我们的意思是，这是一个独立有趣的问题，人们已经在经典环境中研究它了。”
Parekh 进一步解释说：“最大有向切割问题相当于在网络中找到两组代理，其中一组代理与另一组代理之间的通信最多。该问题可应用于网络安全和社交网络分析与设计。”
随着这类问题变得越来越复杂，计算机通常需要更多的内存。但研究小组发现，量子计算机不需要。它们的内存使用效率呈指数级增长，至少当数据以流的形式到达时是如此。当数据集太大而无法装入计算机内存或数据不断创建时，流式计算非常有用。
卡拉格尔此前曾发表文章称，量子计算机可能具有比他和他的团队现在证实的明显但较小的优势。指数比率的新发现意义重大，因为优势必须非常大，才值得花费时间和金钱来构建和运行量子计算机。
与 Shor 的算法一样，这一新发现仍然处于理论上，因为它尚未在计算机上得到验证。
这一发现暗示了量子计算的未来作用
最大有向割本身用处不大。然而，它是高等数学中一个广为人知的优化问题，研究团队认为这暗示了量子计算机未来可能具有的各种实际用途。
“例如，在网络安全方面，有效解决优化问题可以带来更好的资源分配、增强的事件响应策略和更准确的风险评估，”沃罗诺娃说。
卡拉格补充道：“这可能为解决传统计算机无法处理的大问题的算法指明方向。”
“可能还会有更多这样的算法，”沃罗诺娃推测。
帕雷克说：“实际上，没有人能够掌握完整的情况。”

账号		自动登录	找回密码
密码			立即注册