彼得肖尔量子计算的早期岁月（下）

　　译者按
　　从1911年的首届会议开始，索尔维物理学会议就一直对量子物理的发展起着推动作用。
　　今年5月，第28届索尔维会议在布鲁塞尔召开，会议主题为＂量子信息的物理＂。量子计算先驱彼得·肖尔出席会议并做了报告。这是肖尔的报告文稿，将收入会议文集中。
　　蒙索尔维国际物理学化学研究会慷慨允诺，我们得以把这篇文章翻译刊载出来。
　　前几天我们发布了文章的上半部分（参见： 彼得·肖尔：量子计算的早期岁月（上） ），今天发布文章的下半段，讲述了纠错码和容错计算的发现过程。纠错和容错是技术上实现量子计算机的关键，也是当前研究的热点。
　　这部分内容涉及一些技术细节，在这里稍作解释。量子纠错码最初是通过类比经典纠错码发展起来的，其中的关键是阿达马门H的使用。在量子容错计算方面，文章中事实上用到了魔法态制备和（单比特）量子隐形传态（Quantum Teleportation），就是把不易进行容错操作的门放在初态制备过程中，然后通过量子隐形传态传送到量子电路中的所需位置。
　　这些内容我们会有选择性地在后续的文章中介绍。
　　撰文 | 彼得·肖尔 （美国麻省理工学院应用数学系教授，Shor算法提出者）
　　翻译 | 左芬 （博士，上海微观纪元数字科技有限公司）
　　摘要
　　我重新梳理了关于量子计算早期进展的一些记忆片段。这些进展包括因数分解算法、纠错码以及容错的发现。
　　彼得·肖尔丨来源：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  个量子比特分离开来，因此错误不会传播得非常远。不过，这仅仅对克利福德群里的门奏效，而克利福德群的门无法让你做通用计算。
　　事实上，如果你的量子电路只含有克利福德群里的门，它可以 用经典计算机来仿真 。
　　如何在编码的量子比特上执行非克利福德门？
　　其实我们只需要弄清楚如何实现不在克利福德群里的一个门就行了。我最开始尝试的是 在编码的量子比特上实现这个门
　　你没法轻易检验叠加的相位；不过，如果你小心构建你的电路，这个相位的错误只会导致量子码中的可纠正错误，从而可以用纠错电路处理。
　　我的文章并没能给出我想要证明的容错结果，也就是 阈值定理 。
　　阈值定理是说，如果你有足够低的常值错误率，你可以对任何量子电路构建它的容错版本，并且只承担不超过多项式水平的额外开支。
　　我的文章的一个不足之处是，它只展示了如何实现 有限门集 。我说明了如何实现所有的克利福德门和托佛利门。你还可以找到其它一些门的严格构建方式。不过，基于量子容错的本质，任何容错协议都只能执行有限的门集。
　　这是因为，如果它可以容错地实现依赖于一个连续参数的一族门，你是没法区分该连续参数的两个相近值的。因此，你所需要做的是找到一组离散门集，对 较小数目量子比特 上的任意幺正变换给出很好的近似。
　　索罗维-基塔耶夫定理 表明这是可行的。事实上，这一定理表示，如果SU(k)中的任意有限门集可以生成SU(k)中稠密的一个群，那么SU(k)中的任意门都可以用这个门集的一个相对较短的序列来很好地逼近。
　　利用这一点你可以证明，如果对能生成SU(k)中稠密的一个群的任意门集实现了容错操作，你可以用这些近似去构建一个容错电路，使得它能 足够好地逼近任何电路 ，并且只需要承担多对数的额外开支。
　　我的文章也没有说明量子计算机能够完全容错地建造。
　　它表明，如果你的量子硬件的错误率是  ε  ，你可以运行
　　数量级的门，使得总错误率较小，这里  c  是某个常数。
　　可是，我真正想证明的是，存在某个 阈值 ，如果错误率  ε  在这个阈值之下，任意长的运算都可以容错地进行。
　　两个研究组最终证明了这一结果，通过将我的构造自我级联很多次。要计算  n  步，你需要级联loglog  n  层，并为此 付出多对数的开支 。
　　阿列克谢·基塔耶夫发现了另一种执行容错量子计算的方法，通过利用 拓扑码 。
　　阈值定理的发现说明量子计算机 在技术上也许是可行的 （尽管仍然很困难） ，从而导致了对各种实际建造路线的研究的大爆发。
　　原文链接：
　　The Early Days of Quantum Computation，Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964
　　本文经授权转载自微信公众号＂中国信息协会量子信息分会＂。
　　特 别 提 示
　　1. 进入『返朴』微信公众号底部菜单＂精品专栏＂，可查阅不同主题系列科普文章。
　　2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如＂1903＂，可获取2019年3月的文章索引，以此类推。