彻底读懂量子计算机背后的原理

　　编译/大路
　　作者/Scott Aaronson
　　你或许听说过这样一种说法，量子计算机是一种「违背常识的」机器——通过在不同的平行宇宙中「计算」来得到正确答案，通过量子计算机，人类很快就会治愈癌症和全球变暖。
　　15年来，在我的博客和其他地方，我一直在抨击这种卡通化的观点，并去试图解释真实但更迷人的真相。我把这些工作当作一项公共服务，也是我作为一个量子计算研究者的道德责任。
　　有时候，我也感觉这项工作有些艰辛。但多年来，随着企业和政府投资数十亿美元，以及技术发展到可编程的50量子位设备（在某些设计好的基准上）或许真的可以让世界上最大的超级计算机一展身手，关于量子计算机的令人发指的炒作只会增加。就像在加密货币、机器学习和其他时尚领域一样，有了钱就有了骗子。
　　不过，在反思的时候，我明白了。现实情况是，即使你去掉所有的不良动机和贪婪，仍然很难在没有数学的情况下简单而诚实地解释量子计算。正如量子计算先驱理查德-费曼(Richard Feynman)在谈到为他赢得诺贝尔奖的量子电动力学工作时曾经说过，「如果能用几句话来描述它，它就不值得获得诺贝尔奖了！」
　　图示：量子计算先驱理查德-费曼(Richard Feynman)
　　但这并没有阻止人们去进行「营销式」的宣传。自从1994年彼得-肖尔发现量子计算机可以破解保护互联网交易的大部分加密技术以来，人们对这项技术的兴奋已经不仅仅是出于知识上的好奇心。事实上，该领域的发展也通常被作为商业或技术故事而不是科学故事来报道。
　　通常媒体会说：「看，这里面有这么多深奥的量子技术，但你只需要了解基本理论就可以了。物理学家即将建造更快的计算机，这将彻底改变一切。」
　　问题是，量子计算机不会彻底改变一切。
　　图示：500量子比特相当于10亿多的经典比特 。（来源：www.youtube.com）
　　是的，它们有一天可能会在几分钟内解决一些特定的问题，而这些问题（我们认为）在经典计算机上的计算时间或许比宇宙寿命还长。但这还有许多其他重要的难题，因此不少专家认为量子计算机即使有帮助，也是微不足道的。此外，虽然谷歌和其他公司最近提出了可信的说法，他们已经实现了人为的量子加速，但这只是针对某些特定的、深奥的基准（我帮助开发的基准）。一台足够大和可靠的量子计算机在实际应用中超过经典计算机，如破解密码和模拟化学，可能仍需一个漫长的时间。
　　但是，一个可编程的计算机怎么可能只对 「某些问题」更快？为什么会这样？在这种情况下，「大而可靠」的量子计算机意味着什么？为了回答这些问题，我们必须进入深层次的东西。
　　让我们从量子力学开始。(还有什么比这更深奥的呢？)叠加的概念是很难用日常语言表达的。因此，毫不奇怪，许多作家选择了一个简单的方法。他们说，叠加的意思是「同时存在」，所以量子比特，只是一个可以「同时为0和1」的比特，而一个经典比特只能是其中之一或另一个。他们继续说，量子计算机将通过使用量子比特在叠加态中尝试所有可能的解决方案来提高其运算速度——也就是说，在同一时间，或「并行地」计算。
　　这就是我认为的通常量子计算理论普及里的基本错误，也是导致其他所有问题的根源性错误。从这里开始，量子计算机通过「尝试所有可能的答案来快速解决计算难题」。
　　问题是，对于一台计算机来说，在某些时候，你需要看它并读取一个输出。但如果你看的是所有可能答案的平等叠加，相当于量子力学的规则说你只会看到并读到一个随机的答案。如果真是如此，你完全可以自己选一个啊。
　　叠加的真正含义是「复数的线性组合」。这里，我们指的「复数」不是「复杂」「多个」的意思，而是指一个实数加一个虚数，而「线性组合」意味着我们把不同倍数的状态加在一起。因此，一个量子比特是一个比特，它有一个被称为振幅的复数，附加在它为0的可能性上，还有一个不同的振幅附加在它为1的可能性上。这些振幅与概率密切相关，因为某些结果的振幅离零越远，看到这个结果的机会就越大；更准确地说，概率等于距离的平方。
　　图示：0到1之间的概率。（ 来源：www.youtube.com）
　　但振幅不是概率。它们遵循不同的规则。例如，如果对振幅的某些贡献是正的，而其他贡献是负的，那么这些贡献可以破坏性地干扰并相互抵消，从而使振幅为零，相应的结果则永远不会被观察到；同样，它们也可以「建设性地干扰并增加」特定结果的概率。
　　为量子计算机设计算法的目标是编排一个「建设性和破坏性的干扰模式」，以便对于每个错误的答案，对其振幅的贡献能相互抵消，而对于正确的答案，贡献则相互加强。只有当你能安排好这些，你就会以很大的概率看到正确的答案。
　　而棘手的部分是在不事先知道答案的情况下做到这一点，而且要比你用经典计算机做的更快。
　　27年前，肖尔展示了如何在整数因式分解问题上做到这一切，它打破了广泛使用的加密代码，这些代码是许多在线商务的基础。我们现在也知道如何对其他一些问题做到这一点，但遗憾的是只能通过利用这些问题中的特殊数学结构。这不仅仅是一次尝试所有可能答案的问题。
　　更加困难的是，如果你想诚实地谈论量子计算，那么你也需要理论计算机科学的概念词汇。我经常被问到，量子计算机会比今天的计算机快多少倍。一百万倍？十亿？
　　这个问题忽略了量子计算机的重点，即实现更好的「扩展行为」，或运行时间与n的函数，即输入数据的比特数。这可能意味着在一个问题上，最好的经典算法需要的步骤数随n呈指数增长，而解决这个问题的步骤数只随n的平方增长。在这种情况下，对于小的n，用量子计算机解决这个问题实际上会比用经典算法解决这个问题更慢、更昂贵。只有随着n的增长，量子加速才会首次出现，然后最终占主导地位。
　　但我们怎么能知道有没有经典的捷径——一个传统的算法会有类似于量子算法的加速行为呢？这个问题虽然在流行的说法中通常被忽视，但它确实是量子算法研究的核心。困难往往不是证明量子计算机可以快速做某事，而是令人信服地论证经典计算机不能做这些事。
　　唉，事实证明，要证明这个问题的难度是惊人的，著名的P与NP问题就说明了这一点（该问题大致上问的是，是否每个有快速可检查的解决方案的问题也能被快速解决）。这不仅仅是一个学术问题，在过去的几十年里，当经典算法被发现「应该」具有类似的性能时，猜想的量子加速却多次「缺席」。
　　请注意，在解释了这一切之后，我仍然没有说过一个关于建造量子计算机的实际困难。一句话，之前的介绍都是「退相干」的，这意味着量子计算机和它的环境（附近的电场、温暖的物体和其他可以记录量子比特信息的东西）之间没有任何关联。其实这些因素都可能导致对量子比特的过早「测量」，从而使它们坍缩为肯定为0或肯定为1的经典比特，意味着量子计算机丝毫没有发挥其特殊价值。
　　这个问题的唯一已知解决方案是量子纠错：1990年代中期提出的一个方案，将量子计算的每个量子比特巧妙地编码为几十个甚至几千个物理量子比特的集体状态。但研究人员现在才开始让这种纠错在现实世界中发挥作用，而真正将其投入使用还需要更长时间。当你读到有关50或60个物理量子比特的最新实验时，重要的是要理解这些量子比特并没有被纠错。而在它们被纠正之前，我们不期望有能够超过几百个量子比特的规模。
　　最后，如果你真的理解了以上我所介绍的概念，你可以尝试去阅读一些真正前沿性的研究论文了！