查看原文
其他

彼得·肖尔:量子计算的早期岁月(下)

量子计算工作组 中国信息协会量子信息分会 2023-04-07
点击上方蓝字 | 关注我们


译者按:

从1911年的首届会议开始,索尔维物理学会议就一直对量子物理的发展起着推动作用。

今年5月,第28届索尔维会议在布鲁塞尔召开,会议主题为“量子信息的物理”。量子计算先驱彼得·肖尔出席会议并做了报告。这是肖尔的报告文稿,将收入会议文集中。

蒙索尔维国际物理学化学研究会慷慨允诺,我们得以把这篇文章翻译刊载出来。

前几天我们发布了文章的上半部分(点击蓝字阅读),今天发布文章的下半段,讲述了纠错码和容错计算的发现过程。纠错和容错是技术上实现量子计算机的关键,也是当前研究的热点。

这部分内容涉及一些技术细节,在这里稍作解释。量子纠错码最初是通过类比经典纠错码发展起来的,其中的关键是阿达马门H的使用。在量子容错计算方面,文章中事实上用到了魔法态制备和(单比特)量子隐形传态(Quantum Teleportation),就是把不易进行容错操作的门放在初态制备过程中,然后通过量子隐形传态传送到量子电路中的所需位置。

这些内容我们会有选择性地在后续的文章中介绍。


摘要

我重新梳理了关于量子计算早期进展的一些记忆片段。这些进展包括因数分解算法、纠错码以及容错的发现。

彼得·肖尔 来源:nature.com

正文

针对量子计算有一种强烈的反对意见,罗尔夫·兰道尔五月份在圣塔菲研究所的会议上就提出来了。

量子计算机看起来无法提供容错。而在没有容错的情况下,如果你要在一台量子计算机上运行N步,你得保证每一步都精确到1/N。

当N很大的时候,比如10亿(这差不多是你对一个加密上有意义的大数做因数分解所需要的),这在实验物理学家们看来是绝对不可能的。



有两个主要的量子力学原理,海森堡不确定性原理和量子不可克隆定理,被视为纠错的阻碍。

海森堡不确定性原理是说你无法完整地测量出量子计算机的态。量子不可克隆定理则是说你无法复制一个未知量子态。

假定你用不可靠的元件来搭建经典计算机,并且希望让它容错,有很多技术可以使用。

一种是检验点——你周期性地记下你的计算状态,而一旦计算在某个点偏离了,你不用从头开始,只需要在检验点开始就可以了。

另一种技术是纠错码。这些编码利用冗余来帮助你修复在存储中损坏的比特。

最后,还有一种技术是大量冗余。你在计算中保留每个比特的多个副本,并且不断地对它们进行相互比较来修复那些出错的。大量冗余可能是这些技术中最强力的,冯·诺依曼1956年就研究过。

问题在于,量子不可克隆定理似乎表明所有这些都不可行。对于检验点来说,你不能记下你的计算状态再继续计算——这是在做备份。对于大量冗余来说,修复错误涉及备份——如果你有四个好的计算副本和一个坏的副本,由此得出五个好的副本也是不可克隆定理认为不可能的事情。



幸运的是,尽管纠错码看上去也需要冗余,但还能奏效。

虽然在上学的时候没怎么学过,我在贝尔实验室的数学中心待过,所以了解纠错码的一些内容。

最简单的经典纠错码是重复码,这时你给比特做多个备份,然后利用多数票来修复错误。可以运作的最短码是三比特码(因为你需要多数)。

对于量子码你也可以这么做。这一编码如下,它将一个量子比特编入三个量子比特中

这里,代表逻辑量子比特,被编码进三个物理量子比特中。这一编码纠正比特错误,但它让相位错误的可能性变成了三倍。

我意识到存在量子编码的一种变换,就是我们现在所说的阿达马变换,可以把比特错误变成相位错误,反之亦然。这一变换就是

如果你作用上这一变换,你会得到一个相位错误纠正码,它可以纠正相位错误,但会让比特错误的可能性变成三倍。这一编码就是

你可以将这两种码组合起来,通过一种叫做级联的过程,这是经典编码理论中非常重要的一种技术:首先,你将想要保护的量子比特用其中一种量子码编码;接着你将得到的态中的每个量子比特用另一种码编码。

当你将它们用这种方式组合后,你得到如下可以同时纠正比特错误和相位错误的9-量子比特码

我就是这样发现9-量子比特码的。



经典上,重复码非正式地出现得有几千年了。

不过,更复杂的经典纠错码,比重复码有效得多的,才发现不到五十年的时间,这其中最早的一种是由理查德·汉明发现的。

照此类推,我决定去寻找更复杂的量子纠错码。

我开始把玩经典的7-比特汉明码——仅比重复码复杂的经典码——并发现了其量子版本,它把一个量子比特编码进七个量子比特中,并且纠正一个错误。

这里的关键又是阿达马变换,它把比特错误和相位错误来回转换。经典的汉明码纠正比特错误。不过,如果你把它的码字以适当的方式做成叠加态,就会在阿达马变换下是不变的,从而可以同时纠正比特错误和相位错误

这给出了7-量子比特的量子汉明码:

我把这一构造展示给罗伯·凯尔德班克,接着我们将它推广成一大类量子纠错码,通过组合两种相互弱对偶的经典码。

安德鲁·司迪恩在差不多同一时间发现了量子汉明码和这种构造方式,所以这些编码如今以它们的发现者命名为CSS码



在这些发展之后,人们开始寻找其它的量子纠错码。

两个小组,一个在洛斯阿拉莫斯国家实验室,一个在IBM,把这一问题交给了电脑,并且都发现了一种5-量子比特码

这两种5-量子比特码看起来完全不同,但你可以作用一系列变换,然后看出它们其实是一样的。此外尽管看上去它们明显具有某种结构,这一结构究竟是什么却并不清楚。

当我试着去弄清这一编码的结构时,我决定去做的第一件事就是去找出它的对称群

我问尼尔·斯隆是如何找对称群的,他告诉我某种软件——确切地说,是MAGMA——并且给了我一个MAGMA程序实例,是他写出来计算他研究中用到的一个群的大小的。

软件显示我的群跟他的群是同样大小,都是5160960。不仅如此,如果仔细观察,会发现它们其实就是同一个群,并且在两个问题之间存在着深层联系。

这引导我们发现了稳定子码理论(丹尼尔·戈特斯曼同时也发现了)。

在此期间还有些其它有趣的进展。

阿列克谢·基塔耶夫听说了因数分解的结果,但因为在俄国,他实在没法拿到文章。于是他想出了结果的另一种证明,这给我们带来了相位估计算法

而贝尔实验室的洛夫·格罗弗发现了一种量子搜索算法,效率是最好的经典搜索算法的平方。



最后我想谈论的事情是容错

为了建造量子计算机,光是能用无噪声门进行纠错是不够的;你还得能用有噪声门纠错。这意味着,你纠错的速度得比你引入新错误的速度更快。

冯·诺依曼1956年说明了用经典含噪门如何做到这一点。但对于量子比特这略为棘手——你得弄清楚如何在解码之前对编码的量子比特执行操作,因为一旦解码出逻辑比特,你可能已经将它们暴露在错误之中了。

我意识到对于克利福德群(译注:由阿达马门H,相位门S以及受控非门CNOT生成的群,其中S门的效果是将量子比特绕z轴转动π/2角度。)里的门这是相当直接的,因为对于某一类的CSS码你可以横向执行这些门,也就是说,可以让编码一个逻辑量子比特的第i个量子比特只与其它逻辑量子比特的第i个量子比特作用。

这将码字的第i个量子比特与第j个量子比特分离开来,因此错误不会传播得非常远。不过,这仅仅对克利福德群里的门奏效,而克利福德群的门无法让你做通用计算。

事实上,如果你的量子电路只含有克利福德群里的门,它可以用经典计算机来仿真



如何在编码的量子比特上执行非克利福德门?

其实我们只需要弄清楚如何实现不在克利福德群里的一个门就行了。我最开始尝试的是在编码的量子比特上实现这个门

当我们把这个门作用到一个任意的编码量子比特上,,会发生什么?我们会得到

对比它与下面这个态

怎样才能把这个态变成需要的态

我们可以作用一个受控门改变态的符号,接着作用从第二个量子比特到第一个量子比特的CNOT,或者说受控门。(受控泡利门是在克利福德群里的,所以我们可以容错地运行。)这会为我们给出这个态

现在,如果我们在基下测量第一个编码量子比特并且得到结果,我们就得到了所要的态。相反,如果我们得到结果,我们会有态

于是我们找到了一个流程,可以将一个态顺时针或者逆时针转动2π/3,每个方向各有1/2的概率。

不过,因为顺时针转动这个角度两次会给出逆时针的转动,我们可以重复这个过程直到得到态,而且我们预期要做的转动次数也只有两次而已。



以上想法的困难在于,怎样制备编码态并不清楚。

我花了一些时间和精力,想到了如何使用类似的方式来构建托佛利门(译注:即量子控-控-非门,也叫量子与门)。

我们不再使用辅助态,而是使用

制备这个辅助态的关键是使用猫态。你可以检验这个态来保证它是包含最多0的态和包含最多1的态的叠加。

你没法轻易检验叠加的相位;不过,如果你小心构建你的电路,这个相位的错误只会导致量子码中的可纠正错误,从而可以用纠错电路处理。



我的文章并没能给出我想要证明的容错结果,也就是阈值定理

阈值定理是说,如果你有足够低的常值错误率,你可以对任何量子电路构建它的容错版本,并且只承担不超过多项式水平的额外开支。

我的文章的一个不足之处是,它只展示了如何实现有限门集。我说明了如何实现所有的克利福德门和托佛利门。你还可以找到其它一些门的严格构建方式。不过,基于量子容错的本质,任何容错协议都只能执行有限的门集。

这是因为,如果它可以容错地实现依赖于一个连续参数的一族门,你是没法区分该连续参数的两个相近值的。因此,你所需要做的是找到一组离散门集,对较小数目量子比特上的任意幺正变换给出很好的近似。

索罗维-基塔耶夫定理表明这是可行的。事实上,这一定理表示,如果SU(k)中的任意有限门集可以生成SU(k)中稠密的一个群,那么SU(k)中的任意门都可以用这个门集的一个相对较短的序列来很好地逼近。

利用这一点你可以证明,如果对能生成SU(k)中稠密的一个群的任意门集实现了容错操作,你可以用这些近似去构建一个容错电路,使得它能足够好地逼近任何电路,并且只需要承担多对数的额外开支。



我的文章也没有说明量子计算机能够完全容错地建造。

它表明,如果你的量子硬件的错误率是ε,你可以运行数量级的门,使得总错误率较小,这里c是某个常数。

可是,我真正想证明的是,存在某个阈值,如果错误率ε在这个阈值之下,任意长的运算都可以容错地进行。

两个研究组最终证明了这一结果,通过将我的构造自我级联很多次。要计算n步,你需要级联loglogn层,并为此付出多对数的开支

阿列克谢·基塔耶夫发现了另一种执行容错量子计算的方法,通过利用拓扑码

阈值定理的发现说明量子计算机在技术上也许是可行的(尽管仍然很困难),从而导致了对各种实际建造路线的研究的大爆发。

原文链接:

The Early Days of Quantum Computation,Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964

作者简介:彼得·肖尔,美国麻省理工学院应用数学系教授,Shor算法提出者

译者简介:左芬,博士,上海微观纪元数字科技有限公司


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存