彼得·肖尔 量子计算的早期岁月
发布时间：2022-11-16 20:02:20 所属栏目：外闻 来源：互联网
导读： 从1911年的首届会议开始，索尔维物理学会议就一直对量子物理的发展起着推动作用。
今年5月，第28届索尔维会议在布鲁塞尔召开，会议主题为“量子信息的物理”。量子
今年5月，第28届索尔维会议在布鲁塞尔召开，会议主题为“量子信息的物理”。量子
|
从1911年的首届会议开始，索尔维物理学会议就一直对量子物理的发展起着推动作用。 今年5月，第28届索尔维会议在布鲁塞尔召开，会议主题为“量子信息的物理”。量子计算先驱彼得·肖尔出席会议并做了报告。这是肖尔的报告文稿，将收入会议文集中。 蒙索尔维国际物理学化学研究会慷慨允诺，我们得以把这篇文章翻译刊载出来。 这是文章的上半段，讲述了上世纪80、90年代期间，量子计算起步阶段学界的一些趣事：比如费曼对是否应该“探讨自然成因”前后不同的看法、他在“负概率”一文中未提及作为动机的贝尔定律；肖尔受“西蒙问题”的启发解决了离散对数问题，而他之后关于离散对数问题的讲座被“以讹传讹”为解决了因数分解问题，以及物理学家知道他这一工作的始末...... 撰文 | 彼得·肖尔（美国麻省理工学院应用数学系教授，Shor算法提出者） 翻译 | 左芬（博士，上海微观纪元数字科技有限公司） 彼得·肖尔丨来源：麻省理工大学 这个演讲最初是为了纪念1981年在恩迪科特大楼举办的物理与计算会议的40周年而准备的，所以我觉得我应该从1981年说起。 我那时是加州理工的大四学生，所以当费曼为恩迪科特大楼会议准备主题发言时我已经在那儿了，而那次发言成为了最早仔细审视量子计算的几次尝试之一。 我在加州理工的时候什么消息也没听到，事实上我很久以后才读到费曼的文章。 不过我倒是想提一下我听他在加州理工的另一个讲座，因为那个讲座表明他那时正在思考物理学基础方面的问题。 费曼的报告是关于负概率的。 在报告开头，他解释说他一直在思考贝尔定理，因为它说明量子物理不可能是一种局域的、实在的隐变量理论。 这就意味着，量子力学的任何解释要么要求非局域性，要么要求非实在性（这里局域性意味着信息不能超光速传播，而实在性意味着你能测量的东西对应着粒子的具体性质）。 费曼解释说他所做的就是仔细审查证明贝尔定理用到的前提，看里面是否存在隐藏的假设。 他确实找到了一个——那就是所有概率都必须在0和1之间。 这并不像初听起来那么古怪——简谐振子的维格纳函数的行为就恰好这样，而且费曼也提到了这一点。 他接着展示了他发现的关于负概率的一些结果；报告的这部分内容我记得不是很清楚了。 更早的时候，在1964年的系列讲座上，费曼曾说： “我来告诉你大自然到底是怎样的。如果你直接接受她表现出来的样子，你会发现她是迷人的、令人愉快的。如果你能忍住，就不要老是问自己，‘它怎么会是那样子的呢？’，因为你会‘深陷泥潭’，进入到一个没人能逃脱的死胡同中。没人知道它为何那样。” 但是这时，15年后，他却在探讨自然为何会是这样的一个可能的原由。从这里你可以看出来费曼并没有采纳他自己的建议。 当然，也许他的建议不是给终身教授，而是给研究生们的；对他们来说，那可能是很好的建议——在量子力学的基础上得出新的、重大的结果是相当难的，所以它对研究生来说不是一个好的课题。 几年后的1983年，费曼把报告中的一些想法写了下来，写成了一篇叫做“负概率”的文章，但文章在那好多年后才得以发表。 那篇文章有趣的地方在于，它并没有提到作为动机的贝尔定理。 他的文章首先讨论了维格纳函数，这些函数确实给出了负值的概率。费曼接着将维格纳函数推广到自旋系统的量子比特。 而费曼在他的报告中讲述的原始动机已经被消除量子场论中的无穷大所取代。因此想必费曼的原始想法并不奏效——他没能利用负概率解决爱因斯坦-波多尔斯基-罗森（EPR）悖论。 我不知道究竟是什么导致了动机的改变。难道他觉得试图找出一种更好的方式来理解贝尔定理这个动机太丢人了，因为这牵涉到量子力学的基础，所以他想出了一个更加体面的？或者是还有别的什么原因？ 我还想说说那个年代另一篇有趣的文章。 1985年，大卫·多伊奇写了一篇关于量子图灵机、量子计算以及量子邱奇-图灵论题的文章。 多伊奇的动机部分源自于量子力学的基础——他宣称有了量子计算机，就有可能检验量子力学的埃弗里特（多世界）解释。 他在文章中说： 对这些性质的直观说明给埃弗里特之外的所有量子理论解释带来了无法承受的压力。 我想表明在这一点上我并不认同他，尽管他一直没有改变观念。 1985年，费曼写了他1982年文章的续篇，其中给出了如何建造量子计算机的详尽得多的提议。不过这一提议仍然不太切实可行，因为它在构建初态和跃迁振幅上要求极其高的精度。 作为一个有趣的旁注，我想指出当大卫·多伊奇和理查德·费曼在考虑量子计算时，他们都在思考着量子基础。我的直觉是这很重要。 如果你认同了大卫·梅尔曼版本的哥本哈根解释——“闭上嘴去算吧”——那么你就不会去思考量子的古怪性，这样你可能也就不会去思考量子古怪性的可能用途。 在加州理工，我学了一些物理课程，但主修数学。 我接着去了麻省理工的应用数学研究生院，在那里研究数学与计算机科学的交叉部分，并最终在贝尔实验室找了一份数学和计算机科学方面的工作。 我第一次听说量子信息是在查理·本内特在贝尔实验室做的一次报告上，他在报告里讲述了BB84量子密钥分发协议（译注：该协议由Bennett与Brassard于1984年提出，故名）。我不记得那是哪一年了，不过肯定是在80年代末期。 我记得我对他的报告非常着迷，还思考过一阵查理提出的一个未解难题。这个难题就是你能否严格证明BB84协议是安全的。 在思考过程中，我完全不清楚如何将量子力学表述成某种数学形式，以便严格证明该协议是安全的。所以我放弃了那个问题。 说起来有点好笑，到了2000年，在我熟知了量子计算、量子信息和量子纠错码之后，约翰·普雷斯基尔和我倒是想到了BB84安全的一种简单证明方式。 这已经是BB84安全性的第三种证明，不过前两种证明，分别由迈耶斯和比哈姆等人完成，相当复杂。 我仔细读了迈耶斯的证明并意识到CSS编码（译注：即Calderbank-Shor-Steane编码，后文有详细介绍）隐含在其中，而如果使用这些编码，你可以得到一种简单得多的证明。 在本内特在贝尔实验室的报告之后，我再也没想起过量子计算，直到1992年优曼许·沃兹内尼到贝尔实验室来做报告，讲述他和伊桑·伯恩斯坦关于量子图灵机的文章。 这篇文章后来发表在1993年6月的计算理论研讨会（STOC）上，最负盛名的两个理论计算机科学会议之一。 我对那个报告极为着迷，而且我可能比其他计算机科学家理解得都深一些，因为我在大学时学过一些物理。 伯恩斯坦和沃兹内尼给出了一个精心设计的问题使得量子计算机看起来可以做得更好，但我对那个问题不是太满意。 于是我开始思考是否可以用量子计算机更有效地解决一个实际问题。 我并没能真正取得进展，直到我读到丹·西蒙的文章。 他在文章里用量子计算机算法解决了一个人为问题，“西蒙问题”，并且比最好的经典算法还要好得多。 我会读到这篇文章是因为我在1994年STOC会议的项目委员会里，而委员会拒收了那篇文章（尽管我已争取了）。 我听说丹·西蒙的出发点是想证明数字计算机不再比量子计算机强大，但他最终找到一个问题显示了相反的结果。 西蒙用到了一个二进制矢量空间上的傅里叶变换来找出该矢量空间上一个函数的周期。 我知道傅里叶变换对寻找周期有帮助，而且我知道离散对数问题跟周期性有关，所以我开始寻求在量子计算机上解决离散对数问题的方法。 离散对数问题是一个有名的难题，如果你解决了它，就可以破解一些公钥加密系统。 西蒙算法和离散对数问题中的周期寻找的差异在于，对于西蒙问题，你需要在n-维超立方体上找到一个函数的周期，而对于离散对数问题，你需要在P-1×P-1环面上寻找周期。 （编辑：威海站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐