摘自德克萨斯大学奥斯汀分校计算机科学与系统专家，讲师，Scott Joel Aronson的博客您阅读了这些故事-在《金融时报》，《技术评论》，CNET，Facebook，Reddit，Twitter中[[
在Habr /上大约。 翻译或其他地方-Google的一组研究人员通过其53量子位超导设备获得了量子计算的优势。 它们很容易找到，但是我不会给它们提供链接-仅因为它们尚不存在。
全世界都知道，谷歌确实在准备一个有关量子卓越的重大公告，该公告应该与其中一份备受推崇的科学期刊上的研究成果发表同时发布。 这很可能会在一个月内发生。
同时，参与这项开发的NASA意外地在公共站点上发布了旧版本的Google。 她在那里呆了很短的时间，但足够去英国《金融时报》，我的收件箱和数百万其他地方。 缺乏事实的关于这项工作的论据可以无处不在。
显然，我们的世界被剥夺了明确宣布“人类进入太空”这一新时刻的机会，在这个新闻发布会上，
强有力的丘奇-图灵论点将在实验上遭到驳斥。 这将更像赖特兄弟的逃亡，关于零散的谣言在1903年至1908年之间浮出水面，威尔伯和奥维尔最终同意进行示范飞行（幸运的是，只有在我们这种情况下，问题的解释才会涉及到更少的时间！）
我已经待了几个月。 对于我来说，很难在我的博客上写这件事非常困难。 我答应保持沉默，但我无法抗拒在这里和那里留下不同提示的愿望-例如，在我上一次关于
保罗·伯奈 （
Paul Bernays）的 活动的演讲中，我特别设计了我的演讲课程，以便他们能讲到这一点。
此项是确认这些事实的正式公告。 如果我们已经可以看到闪电，那么雷声的权利就属于Google的一组研究人员，以及时间和地点。
相反，我决定澄清这个问题，以消除我作为博客作者和“社会知识分子”时在互联网上流传的错误信息，并向您介绍“关于Scott量子优势的一系列出色的问答”。 万一您突然对量子优势感兴趣，或者想知道如果来自Mountain View或假设其他地方的某个搜索引擎公司宣布实现
量子优势将会发生什么。
好吧，我们不要拉扯猫的尾巴：
问题1：什么是量子计算卓越？该术语通常简称为量子优势（KP）。 它表示使用量子计算机（QC）解决某些定义明确的问题，使用当今经典计算机上的当今众所周知的算法解决这些问题将花费更多数量级的时间-不仅如此，而且由于渐近量子复杂性。 这里的重点是100％确保在QC上解决了该任务，而这在经典计算机的帮助下确实无法实现。 理想情况下，任务应该是可以在不久的将来解决的（借助于嘈杂的，不是已经存在或即将出现的通用QC的帮助）。 如果此任务仍然有用，那就更好了-但这不是必需的。 赖特兄弟的飞机或
芝加哥柴堆本身并没有用。
问题2：如果Google的研究人员真正接触到HF，这是否意味着“任何代码都可以被黑客入侵”，因为最近美国民主党民主党候选人安德鲁·杨（Andrew Young）发了推文？不正确（尽管作为候选人，杨对我很漂亮）。
有两个问题。 首先，Google，IBM和其他公司今天创建的设备包含50-100量子位，并且没有纠错系统。 要运行
Shore算法来破解RSA加密，需要数千个逻辑qubit。 借助当今已知的纠错方法，这很容易需要数百万个物理量子位，并且质量要优于现有的量子位。 我认为没有人能接近这个目标，我们也不知道要花多长时间。
其次，即使在一个假想的将来，如我们今天所看到的那样，具有纠错功能的可扩展QC也将能够破解某些代码，但不是全部。 巧合的是，可以破解的公钥包括我们当今用于互联网安全的大多数密钥：RSA，Diffie-Hellman协议，椭圆曲线等。 私钥加密将产生最小的影响。 还有一些公钥系统的候选人（例如，基于光栅的人），其破解方法在20年的质量控制尝试中尚未为任何人所知。 另外，已经在尝试切换到这样的系统。 详细信息在我
给丽贝卡·戈德斯坦的信中 。
问题3：Google计划进行或已经进行了哪些计算（传统上较为复杂）？我可以说，尽管我很尴尬。 计算如下：“测试器”生成一个随机量子电路C（1个量子比特的门的随机序列和最接近它的第二个量子比特，在50-60个量子比特的二维晶格上深度约20）。 然后，测试人员将C发送到量子计算机，并指示他将电路应用于全0的初始状态，以基数{0,1}来测量结果，发送观察到的n位字符串，并重复数千或百万次。 最后，经典测试人员使用他的C知识，进行统计测试，以验证输出确认QC执行了计算。
也就是说，这不是一项像分解这样的任务，它只有一个正确的答案。 电路C在n位字符串上产生概率分布，我们称其为D
C ，任务是从该分布中产生样本。 实际上，将有2
n条线表示支持D
C －并且将有很多条线，以至于如果QC能够正常工作，那么我们将永远不会看到相同的输出。 重要的是，D
C的分布不均匀。 有些线会受到振幅的相长干涉，其概率会更大，而其他线会受到相消干涉，其概率会较小。 并且尽管我们只会看到少数几个样本，但与2
n相比，它们的数量很小，但我们可以检查它们是否倾向于行，我们认为这更有可能，最终，这将增加我们对发生传统上无法达到的结果的信心。 。
简而言之，只会要求KK执行随机（但已知）的操作序列-不是因为我们需要特定的结果，而是因为我们试图证明它可以在某些明确定义的任务中领先于经典计算机。
问题4：但是，如果KK仅存在以发出随机垃圾，其唯一含义是很难在经典计算机上进行模拟，那么谁在乎呢？ 那不是镀锡的三明治，一无所有吗？不行 正如我已经写过的，这不是一次包含所有内容的三明治，而是绝对包含某些东西的三明治！
尊重正在讨论的主题的庞大性以及实现该主题所必需的极其复杂的工程成就。 在CP出现之前，怀疑者可能会感到很有趣，因为在20多年来花费了数十亿美元之后，没有一个质量控制曾被用来解决比笔记本电脑处理速度更快的任务，或者至少不能解决问题取决于该计算机的量子性质。 但是在即将到来的KP世界中，这已经是错误的。 通过计算掌握了2
50或2
60复数的叠加，所使用的时间和资源与2
50或2
60相比很小。
我一直怀念赖特兄弟的飞机，因为我对我们正在谈论的话题与互联网上各方对此主题的忽视之间的深渊感到震惊。 这类似于一个坚决认为不可能在空中进行有用旅行的人的反应，然后他看到一架普通的木制螺旋桨飞机在空中air翔-这种奇观不会反驳他的观点，但也不会支持它。
这些年来，我是否真的一直在为无所作为而
担心 ，不断吹捧CC所取得的不太重要的里程碑会耗尽人们的耐心，而他们却不在乎什么真正值得的事情发生？
Q5：许多年前，您为大众夸大了D-Wave及其有关通过量子退火解决优化问题的巨大量子加速的陈述而感到羞耻。 现在，您为不热情地欣赏共产党而感到羞愧。 你为什么不决定呢？因为我的目标不是在任何特定方向上引领“热情水平”，而是要确保它是正确的！ 您是否可以说回想一下，即使我对D-Wave的批评使我在某些圈子中不受欢迎，我还是对D-Wave总体上是正确的吗？ 因此，关于KP，我也尝试正确。
问题6：如果与KP相关的计算仅考虑概率分布中的样本，我如何验证计算正确？你问的好东西！ 这是我们和其他科学家在过去十年中一直在发展的理论问题。 我已经在B3中对此进行了简要说明：可以从质量控制返回的样本中对计算进行统计检查，并确保它们更喜欢添加到概率分布D
C的“峰值”中
。 简便的方法之一是Google所谓的“线性交叉熵检查”：这是对QC生成的所有样本s
1 ，.. s
k的 Pr [C输出s
i ]求和，然后在该数量出现时声明检查成功超出某个边界-例如，对于常数1 <b <2，bk / 2
n 。
当然，要执行此测试，有必要在经典计算机上计算概率Pr [C output s
i ]-唯一的方法是穷举2
n时间。 这有问题吗？ 不，如果n = 50，并且您是Google，并且可以处理2
50之类的数字（尽管您不能处理2
1000 ，这是一个超出
googol的数字
-ha ，ha）。 通过在某个地方启动一个经典内核集群一个月，您最终将能够确认QC的正确退出，并在几秒钟之内发出-同时QC的工作速度提高了多个数量级。 但是，这也意味着基于采样的CP实验是为当今创建的50量子位设备设计的。 即使使用一百个量子位，即使使用地球的所有计算能力，我们也无法确认QC的结果。
我强调这个问题对于使用类似于我们现在进行的样本的实验是典型的。 如果肖氏算法将2000个数字分解，则只需将结果因子相乘并检查它们是否属于质数，就可以轻松地进行检查。 或者，如果将CC用于模拟复杂的生物分子，我们可以在实验中测试其操作。
Q7：请稍等。 如果经典计算机只能在实验的仿真模式下（尽管很慢）才能在KP上验证实验的结果，那么这怎么会是“量子优势”呢？来吧 以53个量子比特的芯片为例，很合理的做法是，在这种模式下您仍然可以直接检查工作结果，从而实现数百万倍的加速，并且还可以看到，加速随着量子比特数量的增加呈指数增长-正如渐进分析所预测的那样。
问题8：是否有任何数学证据证明没有快速的经典算法可以在抽样方面超过KP实验？今天不行 但这不是KP研究人员的错！ 理论信息学专家甚至无法证明最简单的假设，例如P≠NP或P≠PSPACE，因此您不希望明确地排除快速经典模拟的存在。 我们只能希望条件复杂。 我们确实证明了
其中一些 结果 。 该领域最大的理论问题是条件复杂度最佳结果的证明。
问题9：采样框本身有什么用处？第一次考虑这个话题时，人们通常认为对这个问题的明显答案是“不”（我就是其中之一）。 但是最近情况发生了变化-例如，由于我的确认随机性协议得以证明，该协议演示了如何将带有采样的CP的实验很快地转变为比特生成器，可以向怀疑的第三方观察者证明其随机性（在某些计算假设下）。 这可能会应用于
PoS加密货币和其他加密协议的创建。 我希望在不久的将来会发现更多这样的应用程序。
问题10：如果KP实验只是生成随机位，那有趣吗？ 通过简单地将量子比特转换为随机比特，这不是一件容易的事吗？最重要的是，使用KP进行的实验不会生成统一的随机位。 他从50位或60位行的一些复杂的相关概率分布中进行选择。 在我
确认的随机性协议中，偏离同质性在CP如何说服经典怀疑论者中认为位真正是随机的并且没有秘密系统（如伪随机数生成器）起着核心作用。
问题11：但是，数十年来的量子力学实验（例如那些违反了贝尔不等式的实验）是否尚未证明KP？这只是一个混乱。 这些实验显示了其他种类的“量子优势”。 例如，在违反贝尔不等式的情况下，这就是“量子相关优势”。 它没有显示出计算上的优越性，也就是说，无法在经典计算机上进行模拟（尽管经典模拟不会对空间局部性或类似情况产生限制）。 如今，人们通常指的是KP带来的量子计算优势。
Q12：嗯，但是有许多材料和化学反应的例子，很难经典地模拟，还有特殊的量子模拟器（例如，哈佛大学的Lukin小组）。 为什么不将它们视为KP的示例？根据某些定义，它们可以视为KP的示例！ Google研究人员的工作之间的主要区别在于，他们的设备是完全可编程的-可以将其编程为与最近邻居的任意2比特比特门序列，只需从量子计算机发送必要的信号即可。
换句话说，KP怀疑论者再也不会抱怨说，如果存在难以经典地模拟的量子系统，那仅仅是因为自然界难以模拟，而且我们不能随意改变在其中发现的随机化合物因此，自然不能将这些系统视为“模拟自己的计算机”。 根据任何合理的定义，谷歌，IBM和其他公司今天正在建造的超导设备是真实的计算机。
问题13：您是否发明了量子优势的概念？不行 我在他的定义中扮演了重要角色，这就是为什么Sabina Hossenfelder和其他人将这个想法归功于我。 “量子优势”一词是约翰·普雷斯基尔（John Preskill）在2012年提出的，尽管关键概念在某些方面可以追溯到1980年代初的量子计算本身。 1994年，使用Shore算法对大数进行分解成为KP领域的一项真正的实验-尽管今天这个问题很难解决。
据我所知，该思想的实质是使用采样问题来演示CP，它是由Barbara Theral和David Divincenzo在2002年进行的有远见的
工作中首次提出的。 “现代”组织实验的尝试始于2011年，当时我和我和Alex Arkhipov在BosonSampling上发表了我们的
工作 ，而Bremner，Josa和Shepherd在转换汉密尔顿学上发表了我们的
工作 。 这些工作不仅表明“简单”的通用量子系统不能解决采样上看似复杂的问题，而且针对这些问题的有效经典算法将导致
多项式层次结构的
崩溃 。 我和Arkhipov还采取了第一步，以证明即使是量子采样问题的近似版本也可能是经典的。
据我所知，“电路的随机采样”的想法（即通过选择超导体系结构中的随机2量子位阀序列产生复杂的采样问题）出现在我于2015年12月开始的电子邮件通信中，约翰也参加了Martinis，Hartmut Niven，Sergio Boixo，Ashley Montanaro，Michael Bremner，Richard Josa，Aram Harrow，Greg Cooperberg等人，这些信件被称为“一个困难的40比特抽样问题”，而我的来信开头是“抱歉垃圾邮件”。我讨论了用样本演示KP的三种方法的优缺点：（1）随机轮廓，（2）交换哈密顿量，（3）BosonSampling。库珀伯格为第一选择辩护后，参与者迅速达成共识，从工程学的角度来看，第一种选择的确是最好的-如果现有的（1）理论分析还不够，那么我们可以提出一些建议。之后，来自Google的一组人员对理论和数值随机轮廓的样本进行了大量分析，Chen Lijie Chen和Buland和我的同事为该问题的经典复杂性提供了各种证据。问题14：如果实现了KP，这对怀疑论者意味着什么？我不想在他们的位置！他们可以移动到可能进行KP的位置（谁说这是不可能的？他们肯定不是！），而且错误的量子校正一直是一个真正的问题。他们中的许多人确实支持这一特殊立场。但是其他人，包括我的朋友吉尔·卡莱（Gil Kalay），在此处的博客文章中声称，由于根本原因，无法实现KP。而且我不会让他们离开。Q15：接下来呢？达到KP意味着Google小组已经拥有必要的设备来演示我的协议以生成确认的随机位。这确实是我们计划要做的第一件事。下一个明显的里程碑将是使用具有50-100量子位的可编程QC进行有用的量子模拟（例如，凝聚态系统），其速度快于任何已知的经典方法。第二个明显的里程碑将是量子纠错的使用演示，从而使编码的量子比特比基础的物理量子比特寿命更长。毫无疑问，谷歌，IBM和其他公司将竞相争取这两个里程碑。发表文章后，史蒂夫·格文（Steve Girwin）提醒我，耶鲁大学的小组已经接触到量子误差校正，尽管在玻色子系统中，而不是在超导量子位系统中。因此，也许下一个里程碑可以更好地表述为：在一个系统中实现量子计算的优越性和有用的量子误差校正。