DAOrayaki｜澄清量子霸权：量子计算里程碑的更准确术语

DAOrayaki ｜2023-06-13 8:56

过去几年对于量子计算来说是令人兴奋的时期。几家公司已经构建并提供了小型量子处理器，并且有开源软件可供编程

作者：W. J. Zeng

链接：

https://yakihonne.com/article/naddr1qq2hxa2k0fxkxajwxpxhyw2f2a49qdpnwft4wq3qn572rtak06pgerl9s3g0z5e95zf7uqgg0ntz7lpmf3lzh3rey2hsxpqqqp65wus6xl9

过去几年对于量子计算来说是令人兴奋的时期。几家公司已经构建并提供了小型量子处理器[1]，并且有开源软件[2]可供编程。现在每个人都想知道：量子计算机何时能够超越普通计算机？谈论时间表本身就是一个引人入胜的话题，但在本文中，我将尝试澄清我们所说的“更好”是什么意思。

这很重要，因为“更好”对于理论计算机科学家和投资者可能有不同的含义。如果没有对“更好”有共同的理解，那么谈论时间表只会令人困惑。

社区中已经有一些概念，如量子霸权[3]和量子优势[4]。不幸的是，这些术语在媒体中经常被随意使用，它们的定义可能不清楚。为了更清晰地表达，我提出以下四个量子计算机性能的里程碑：

量子霸权：这个里程碑包括两个结果：（1）对于给定问题，存在一个数学证明，证明任何可能的量子算法与任何可能的经典算法之间存在超多项式分离*，（2）展示出解决这个问题的量子计算机的性能（规模、速度或效率）是任何可用的经典计算机无法实现的。*请注意，只需相对于广泛认可的假设（如多项式层次不崩溃）存在这样的证明即可。
弱量子霸权：使用量子计算机解决任何问题比任何可用的经典解决方案更快、更便宜或更高效。
量子优势：使用量子计算机解决一个有价值的问题比任何可用的经典解决方案更快、更便宜或更高效。
强量子优势：量子优势伴随着一个证明（基于广泛认可的假设），证明该问题在任何量子解决方案和任何经典解决方案之间存在超多项式分离。等价地，对于一个有商业价值的问题，类似于量子霸权。

这四个里程碑构成了以下分类：

量子计算性能里程碑的分类法。

希望这个分类法能够澄清各个里程碑在何种情况下是重要的。例如，人们经常谈论量子霸权。然而，量子霸权既不是一个必要条件，也不是一个充分条件，用于量子计算机的大型商业市场。例如，我们可以证明等效的“GPU霸权”是不可能的，然而这项技术却有一个庞大的市场。也就是说，在量子优势之后，弱量子霸权是通向具有商业相关性市场的第一个里程碑。

这并不是说量子霸权和强量子优势不重要。它们是基础性的，能够深刻地说明我们宇宙的本质。个人而言，我同意Scott Aaronson的观点[5]，他说“清晰地展示量子霸权至少和（比如说）发现希格斯玻色子一样重要”。

关于量子计算的一个令人难以置信之处在于它既是一项科学探索，又是一项技术。在该领域发展的过程中，澄清我们所讨论的里程碑类型至关重要。

在未来几年中，能够参与我们领域的前进将是令人兴奋的！感谢Scott Aaronson、Simon Benjamin、Josh Combes、Travis Humble、Richard Stebbing和Guillaume Verdon对本文草稿的评论。