几天前，来自Google的一篇文章草稿，介绍了他们在超导量子计算机中实现量子优势的事实，该文章泄露给了网络。 文本本身很快被删除，谣言和假设（包括错误的假设）在文本周围成倍增加。 该文章的作者是量子算法方面的领先专家之一
斯科特·亚伦森教授 ，并拥有一个出色的博客。 在上一篇文章中，他回答了有关量子优势的主要问题。
来自翻译者。 我根本不是算法复杂性特别是量子算法方面的专家。 但是，对于我来说，该帖子似乎太有趣了，因此无法在Habré上进行讨论，如果出现任何术语错误或用法不正确，请踢我下午。
您已经看过一些故事-在《
金融时报》 ，《
技术评论》 ，
CNET ，Facebook，Reddit，Twitter或其他地方，都在谈论Google的一个小组用53量子位的超导计算机实现了量子优势。 这些故事很容易找到，我不会在这里附加它们，因为还没有一个故事存在。
众所周知，Google实际上正在准备有关量子优势的重要声明，该声明与酷炫杂志上的科学文章（是哪一个？选择很小-两种之一）一起计划的。 我希望这会在一个月内发生。
同时，文章的某些作者所在的NASA偶然在公共站点上发布了该文章的旧版本。 她在那里呆了很短的时间，但足够长的时间出现在《
金融时报》，我的邮件和百万其他地方。 关于其重要性没有事实的猜测会增加。
似乎世界被剥夺了“月球降落”的纯粹时刻，在一次新闻发布会上，实验证据证实了延伸的“丘奇思想”论断。 这将更像怀特兄弟的逃亡-在1903年至1908年之间，威尔和奥维尔最终决定展示他们的逃亡时，有关谣言和半真相的消息渗入了公共场所。 （这次，幸运的是，所有内容将被更快地澄清！）
这篇文章不是官方声明或任何确认。 尽管已经可以看到雷电，但雷声在其选择的时间和地点属于Google的一个小组。
相反，我想阻止错误信息的传播，并在此处提供我的Scott的《最高量子至上性常见问题解答》作为博客作者和“公共知识分子”。 您知道，如果您突然对量子优势感到好奇，或者一直想知道如果突然从Mountain View或其他地方的某个搜索公司宣称已经实现了量子优势，将会发生什么。
事不宜迟，这里是：
B1。 什么是量子计算卓越？通常将其简化为“量子优势”，该术语是指使用量子计算机来解决一组特殊问题，在使用任何已知算法的经典计算机上解决这些问题将花费更长的数量级-并非出于某些随机原因，而是由于渐近量子复杂性。 这里的重点是要尽可能确保该问题确实以量子方式解决，并且确实是经典上无法实现的，理想情况下，它将使我们能够在不远的将来实现计算加速（已经有嘈杂的，非通用的量子计算机那里或将很快）。 如果任务对某些事情也有用，那就更好了，但这不是必需的。 赖特飞机和费米柴堆本身并没有用。
B2。 如果Google确实取得了量子优势，这是否意味着现在就没有破解密码 ，因为美国当选美国总统候选人安德鲁·扬（Andrew Young）最近已关闭？不，不是（尽管我仍然喜欢Young的候选人资格）。
有两个问题。 首先，由Google，IBM和其他公司创建的设备具有50-100量子比特，并且没有纠错。 使用Shore算法对RSA进行黑客攻击将需要数千个逻辑量子位。 使用众所周知的纠错方法，很容易需要数百万个物理量子位和比我们现在更好的质量。 在我看来，没有人能接近这个目标，我们也不知道他们将有多快能接近这个目标。
第二个问题是，即使在假设的具有错误校正功能的QC的未来中，至少到现在我们仍将只能破坏部分代码，但不能破坏所有代码。 巧合的是，可以破解的公钥包括我们用于保护Internet安全的大多数算法：RSA，Diffie-Hellman，椭圆密码学等。 但是基于私钥的加密不应该受到影响。 还有一些公钥密码系统（例如，基于光栅的密码系统），即使经过20多年的尝试，也没人知道如何使用QC进行破解，并且有尝试切换到这些系统的尝试。 例如，请参阅我
给丽贝卡·戈德斯坦的信 。
B3。 Google计划进行（或已经完成）哪些计算，这通常被认为是复杂的。当然，我可以告诉您，但我同时感到愚蠢。 计算是这样的：实验者生成一个随机量子电路C（即在最近的相邻门之间的1量子位和2量子位的随机序列-深度为20，例如作用于n = 50-60量子位的2D网络上）。 之后，实验者将C发送到量子计算机，并要求他将C应用于初始状态0，以{0,1}为基础测量结果，发回n位可观察序列（字符串）并重复数千或百万次。 最后，利用他对C的知识，实验者对结果与量子计算机的预期输出的符合性进行了统计检查。
与数字分解不同，此任务不是具有唯一正确答案的任务之一。 方案C的操作结果是在n位字符串上的统计分布（我们称其为D
C ），我们需要从中选择样本。 实际上，通常D
C可以对应2
n行-如此之多，以至于如果QC能够按预期工作，它将永远不会在输出中产生两次相同的行。 D
C的分布不均匀很重要。 一些线是由于振幅的相长干涉而产生的，因此具有较高的概率，而另一些是由于相消性的结果而具有较低的概率。 尽管只得到了所有可能的2
n个样本的一小部分，但我们可以从统计角度检查这些样本的分布以了解预期的不均匀分布，并确保获得的样本很难经典再现。
TL； DR，要求量子计算机应用随机（但已知）的量子操作序列-不是因为我们对结果感兴趣，而是因为我们试图证明QC可以比传统计算机更好地执行此明确定义的任务。
B4。 但是，如果量子计算机仅执行一些垃圾代码，而垃圾代码的唯一目的是经典模拟难以实现，那么谁在乎呢？ 那不是什么都没有的大蛋糕吗？不行 当然，这并不是所有美味的馅饼，而是至少有东西的馅饼。
至少要对我们在这里谈论的内容的庞大性以及将其转化为现实所需要的工程天才有所尊重。 在没有量子优势（KP）之前，KP怀疑论者只是笑着说，即使经过数十亿美元的投入和20多年的工作，量子计算机仍然无法完成比笔记本电脑更快的工作。 至少不使用量子性。 在获得世界上的量子霸权之后，他们不再笑了。 使用比2
50或2
60小得多的时间和数据量资源来计算2
50或2
60复数的叠加
我之所以说赖特飞机，是因为我们正在谈论的话题与拒绝（我在互联网的不同部分看到的）之间的差距是完全无法理解的。 好像您相信原则上不可能飞行，然后您看到一架脆弱的木制飞机-它可能不会动摇您的信念，但它当然不应该加强它。
我是对的，在多年前
担心不断地大肆宣传KK的成就要差很多会让人疲倦，而当真正有价值的事情最终发生时，他们会被该死吗？
B5。 许多年前，您指责大众对D-Wave的热情以及他们声称在使用量子退火的优化问题中具有惊人的量子优势的说法。 现在，您谴责他们缺乏对量子优势的热情。 你怎么这么善变因为我的目标不是朝着明确选择的方向改变热情水平，而是正确的。 事后看来，即使我的陈述使我在某些圈子中非常不受欢迎，我是否主要还是对D-Wave正确？ 好吧，现在我也试图在量子优势上做对。
B6。 如果量子优势计算仅基于概率分布中的样本，那么如何验证它们的正确性呢？感谢您的询问！ 这正是我和其他人在过去十年中发展了许多理论基础的话题。 我已经在答案B3中告诉了简短的版本：您可以通过对量子计算机给出的样本进行统计测试来验证其是否集中在随机概率分布D
C的峰值附近，从而对此进行测试
。 Google称之为“线性交叉熵检验”的一种简便方法是简单地将KK返回的所有样本s
1 ，...，s
k的所有Pr [C产量s
i ]相加，然后声明检验是否成功并且仅在总和超过一定水平时，例如bk / 2
n ，其中b是1到2之间的常数。
坦白地说，为了应用此测试，您需要在经典计算机上计算Pr [C给s
i ]的所有概率-唯一已知的方法是在〜2
n的时间内进行迭代。 但这会打扰任何人吗？ 不，如果n = 50，并且您使用google，则可以计算2
50之类的数字（尽管您不会得到2
1000 ，这要优于
google ，khe-khe）。 在淘汰了一个月的大量经典内核之后，您最终会得到CC在几秒钟内产生的结果-同时，确保CC快几个订单。 尽管如此，这意味着基于采样的实验几乎是专门针对具有约50量子位的设备而设计的。 即使是100量子位，我们也不知道如何使用地球上所有可用的计算能力来确保结果。
（我单独注意到，此问题仅适用于采样实验，类似于现在正在进行的操作。如果使用Shor算法将2000位数字分解为因子，则可以通过简单地将所有因子相乘并检查其简单性来轻松地检查结果。如果KK用于模拟复杂的生物分子，则可以通过对该分子进行实验来检查结果。）
B7。 等一下 如果经典计算机只能在经典计算机仍可以模拟实验（尽管速度很慢）的模式下才能验证量子优越性实验的结果，那么如何说“量子优势”呢？那你呢 使用53量子位的芯片，您可以看到数百万次的加速，并且您仍然可以验证结果，还可以验证加速度是否随着量子位的数量呈指数增长，就像渐进分析所预测的那样。 这并不重要。
B8 是否有任何数学证据证明没有快速的经典计算机能胜过基于采样的KP实验的结果？目前不行。 但这不是量子优势研究人员的错！ 只要理论家甚至不能证明基本假设，例如P≠NP或P≠PSPACE，并且没有这个假设，我们就不能无条件排除快速经典模拟的可能性。 我们可以期望的最好条件是条件复杂性。 我们对此有一些结果，例如，有关
玻色子采样 的文章或
Bouldand等人的文章。 关于计算随机电路幅度的平均＃P复杂度，或我
与Lijie Chen的文章 （“量子至上性实验的复杂性理论基础”）。 我认为，这方面最重要的悬而未决的问题是最好的条件困难的证明。
B9。 采样量子优势有什么用吗？直到最近，答案显然还没有！ （我知道，因为我本人就是其中之一）。 但是，最近情况发生了变化-例如，由于我
通过了认证的随机性协议，该协议显示了如何基于采样的KP如何独立用于生成即使对于怀疑的第三方也可以证明是随机的比特（在有关计算的假设下）。 这反过来又在加密货币和其他加密协议中得到了应用。 我希望更多的此类应用会很快到来。
B10。 如果在量子优势方面的实验能使随机位产生一切，那为什么会如此有趣呢？ 仅通过测量就不可能将量子位简单地转换成随机位吗？最重要的是QC会生成非均匀分布的随机位。 取而代之的是，它从50-60位字符串上的一些复杂的，相关的概率分布中进行选择。 在我的协议中，对一致性的偏离在质量控制说服怀疑论者如何真正选择随机位而不是秘密使用某种伪随机发生器方面起着核心作用。
B11。 例如，数十年来违反贝尔不等式的量子力学实验没有表现出量子优势吗？这是一个纯粹的词汇问题。 这些实验证明了其他类型的量子优势：例如，在贝尔不等式的情况下，它们可以称为“量子相关优势”。 他们没有表现出量子计算的优越性，即 能够找到经典计算机无法访问的内容的能力（经典计算机在本地空间上没有任何限制，等等）。 如今，当人们使用“量子优势”一词时，它们的意思是量子计算优势。
B12。 即使这样，也没有不计其数的难以经典地模拟的材料和化学反应的例子，以及特殊构造的量子模拟器（例如哈佛大学Lukin小组的那些）。 他们为什么不考虑量子计算的优势？在某些人的定义中，它们被视为！ Google计算机的主要区别在于它们具有完全可编程的计算机-您只需输入经典计算机中的命令，即可输入任意2个qubit门序列（用于相邻的qubit）。
换句话说，KP怀疑论者不再能够嘲笑地注意到，当然，量子系统很难经典地模拟，但这仅仅是因为自然界通常很难模拟，并且您不能将现场发现的随机分子重新编程到计算机中以模拟自身你自己 从任何合理的定义来看，由Google，IBM和其他公司创建的超导设备是完全意义上的计算机。
B13 您（斯科特·亚伦森）（Scott Aaronson）是否发明了量子卓越的概念？不行 我在其发展过程中发挥了作用，因此，例如，萨宾娜·霍森菲尔德（Sabina Hosenfelder）等
错误地将整个想法
的作者
归因于
我 。 “量子优势”一词是约翰·普里斯基尔（John Preskill）在2012年提出的，尽管从某种意义上说，基本概念出现在80年代初期的量子贡献之初。 在1994年，使用Shore算法分解大量数据成为测试量子优势的主要实验，尽管目前这仍然很难产生。
据我所知，可以使用采样的关键思想是由Barbara Terhal和David DiVincenzo在2002年的
一篇文章中首次提出的。 当前对CP采样的工作始于2011年左右，当时我和Alex Arkhipov发表了有关
玻色采样的文章，而Bremner，Jozsa和Shepherd独立发表
了关于通勤哈密顿量模型的文章 。 这些文章不仅显示了可以解决明显复杂采样问题的“简单”系统，也没有显示通用量子系统，而且还表明，有效的经典算法的存在将意味着
多项式层次结构的下降。 我和阿科希波夫（Arkhipov）也为以下论点奠定了基础：即使量子采样的近似版本也可能经典地复杂。
据我所知，“随机采样电路”的想法（即通过在超导架构中随机选择2个量子比特门的序列来产生复杂的采样问题）产生了它们的对应关系，我从2015年12月开始，包括约翰·马丁尼斯，哈特穆特·纳文，塞尔吉奥·布瓦（Sergio Boixo），阿什莉·蒙塔纳罗（Ashley Montanaro），迈克尔·布雷姆纳（Michael Bremner），理查德·乔萨（Richard Jozsa），阿拉姆·哈罗（Aram Harrow），格雷格·库珀伯格（Greg Kuperberg）等。 该主题的标题为“具有40个Qubit的挑战性采样问题”，而信函的开头为“对不起垃圾邮件”。 : (1) , (2) , (3) . , (1), , (1) , (1), - .
Google , ,
Lijie Chen Bouland et al. .
14. , ?, ! , , , , ( ? !), . , . , Gil Kalai , , , , . .
15. ?, , , Google . .
, , 50-100 - (, ) , . , , , . , IBM, Google .