ACM通信
最后一个字节
探索量子计算的前景
图片来源:Sasha Haagensen摄影
我们还没有意识到——或者甚至可能完全理解——量子计算的全部前景。然而，多亏了ACM计算奖得主Scott Aaronson的工作，我们对该技术的潜力有了更清晰的认识，他帮助建立了许多量子霸权的理论基础，并阐明了量子计算机最终将能够做什么。在这里，Aaronson谈论了他在量子复杂性方面的工作。
让我们从您在量子计算领域的第一个重要成果开始:您在研究生院完成的关于碰撞问题的工作。
碰撞问题是，你有一个多对一的函数，你的任务只是找到任何碰撞对，意味着任何两个输入映射到相同的输出。我证明了即使是量子计算机也需要多次访问这个函数来解决这个问题。
这是一种在密码学中很多不同情况下都会出现的问题。你是怎么想到的?
当我在20世纪90年代末进入这一领域时，我对理解量子计算机非常感兴趣，通过观察它们必须进行多少次查询才能了解一个函数的某些性质。这是一个叫做查询复杂度的主题，它实际上是我们对量子算法的大部分了解的来源。因为您只计算对输入的访问次数，所以您不会遇到P vs NP问题。但你是与量子计算机对抗，量子计算机可以进行叠加查询并给出叠加答案。有时候，量子计算机可以利用函数中的结构，以比任何经典算法所需的查询数倍少的方式来学习一些东西。
那么，你的问题需要什么样的结构才能让量子计算机利用它来获得指数级的加速呢?
这正是我们在过去30年里一直在做的事情。1995年，Peter Shor证明了量子计算机在提取周期函数的周期方面非常出色。另一些研究表明，如果你只是搜索一个输入，你的函数映射到一个指定的输出，那么量子计算机只能给出一个适度的平方根改进。碰撞问题之所以有趣，正是因为它似乎处于这两个极端之间:它的结构比周期查找问题少，但比“大海捞针”问题更有结构。
当我的导师Umesh Vazirani告诉我碰撞问题是他在量子查询复杂性中最喜欢的问题时，我说:“好吧，我知道不研究这个问题了，因为这个问题太大了。”但它一直出现在我关心的其他情况下。我在加州理工学院呆了一个夏天，我决定试着攻击它。
我有一个同事，Andris Ambainis，他在几年前发明了这个惊人的下限技术——现在称为Ambainis对手法。我当时还不知道，但他发明这个是为了解决碰撞问题，虽然他没能让它工作。但他可以解决一些我不能用这个方法解决的问题这个方法我很了解，叫做多项式法。我开始尝试使用Ambainis的方法来解决碰撞问题。我对它的研究可能比之前和之后的任何研究都要深入，我最终意识到多项式方法可以证明这个问题的下界，并表明即使是量子计算机也至少需要N个1／5查询来解决它，其中N是输出的数量。不久之后，石耀云改进了这项技术，并能够表明，首先，你需要N1/4查询，然后你需要N个1／3．
从那以后，你在量子霸权方面取得了突破性的成果。
大约在2008年或2009年，我对量子计算的经典模拟有多困难产生了兴趣。忘记量子计算机是否在做任何有用的事情;我们能有多强的证据证明量子计算难以模拟?如果这是你的目标，你可以把注意力从只有一个正确答案的因式分解问题转移到抽样问题，在抽样问题中，你的计算目标只是从N位字符串的某个概率分布中输出一个样本。
量子计算机可以很容易地对某些概率分布进行采样。
不仅如此，还有一个相当简陋的量子计算机。如果经典的计算机能够在多项式时间内有效地对相同的分布进行抽样，那么多项式层次结构将坍缩到第三层，我们将其作为一种不可信的标准尺度。
但如果你想做一个实验来证明量子霸权，仅仅有一个经典计算机难以精确采样的分布是不够的。任何量子计算机都会有大量的噪声，所以你能期望的最多是从接近理想分布的某个分布中取样。对于经典计算机来说，从相同的分布中进行近似抽样有多难?
为了回答这个问题，我们意识到你需要一个量子计算，其中不同可能输出的振幅(与概率相关)是所谓的“稳健的# p完备”，这意味着如果你可以近似它们中的大多数，那么你就可以解决任何组合计数问题。
而玻色子完全符合这一要求。
费米子和玻色子是宇宙中两种基本的粒子类型。如果你有一堆相同的费米子，你想知道它们从输入态到输出态的量子振幅，那么你必须计算一个矩阵的行列式。如果它们是玻色子，那么它就成为矩阵的永久元素。行列式和永久函数是理论计算机科学中最著名的两个函数，其原因与物理无关。行列式很容易计算，但是永久式是# p完备的。
“我们现在处在这样一个时代，在这些特殊的采样基准上，最先进的量子计算机和最大的经典超级计算机之间展开了一场真正的战斗。”
我记得在艾维·威哲森2000年的一次演讲中，他说:“玻色子要比费米子更努力地工作才能弄清楚自己要做什么，这难道不公平吗?”
这个笑话一直萦绕在我的心头，但我知道永久体拥有正确的属性，是坚固的#P-complete。我说，“如果我们可以设计一个量子计算它的振幅是矩阵的永久值呢?我想我们可以用玻色子。现在我最好了解这些玻色子是什么，以及物理学家如何模拟它们。”
最终，你和你的学生Alex Arkhipov提出了一个新的猜想，即近似玻色子采样将很难被经典计算机模拟。
我们做这件事纯粹是出于理论上的原因。但之后，我们做了关于它的演讲，实验物理学家们开始兴奋起来。特别是量子光学的人，因为光子是玻色子，他们一直在处理产生一堆相同的光子，把它们通过分束器网络发送出去，然后测量它们。
所以这是一场竞赛。
第一篇论文发表于2013年，来自澳大利亚的一个小组，他们只用三个光子就完成了这项工作，并通过实验证实，振幅是3 × 3矩阵的永久值。
现在，没有一个经典的计算机会在计算3乘3的永久函数时大费周章。基本上，如果我想计算一个n × n矩阵的永久项，难度将会增加大约2的光子数量的幂次方使用我们所知道的最好的经典算法。如果你想超越地球上任何经典的计算机，你需要50或60个光子。现在你谈论的是一个相当困难的实验，因为地球上没有一个光子源可以在你需要的时候，准确地产生一个光子。
但是在理论学家和实验学家之间发生了难以置信的有趣的互动——他们付出了巨大的努力，在实验学家可以做的事情中间达成妥协，而我们都认为这对经典计算机来说似乎很难。
2019年，谷歌的量子AI实验室宣布，它已经用53个超导量子比特证明了量子霸权，你和陈立杰(Lijie Chen)写了一篇论文，提供了一些理论证据来支持这一主张。
是的，我们开发了那些实验的理论。我们所知道的最好的经典模拟需要指数级的时间，我们给出了一些证据证明这是固有的。但它仍然存在争议。IBM和其他公司表示，他们可以用经典计算机模拟谷歌的结果，速度比谷歌想象的要快得多，尽管仍然没有突破指数障碍。
我们现在处在这样一个时代，在这些特殊的采样基准上，最先进的量子计算机和最大的经典超级计算机之间展开了一场真正的战斗。我预计量子计算机很快就会领先。如果今天真的发生了战争，那就意味着几年后，就不会再有真正的战争了。
©2021 0001 - 0782/21/12 ACM
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有发现记录