章节介绍

版权所有 (c) 2021 百度量子计算研究所，保留所有权利。

量子力学和计算机科学自二十世纪八十年代开始结合并孕育了一个多学科交叉与融合的新型学科：量子计算。量子计算是遵循量子力学规律操控量子信息单元进行计算的新型计算模式。近四十年来，量子计算科技飞速发展，不同于经典计算机的机器——量子计算机问世了。从可计算问题的角度来看，量子计算机和经典计算机的能力并无差别；但是从计算效率来看，由于量子力学中存在叠加、相干和纠缠等神奇性质，在求解某些特定问题时，量子计算机的速度要远远超过经典计算机。

研究量子计算机的原始动机来自经典计算机内在局限性。经典计算机是以超大规模集成电路为硬件基础的计算设备。从数学角度看，经典计算机进行的是依赖于布尔逻辑的通用计算。在 20 世纪 30 年代，邱奇、图灵等人对通用计算进行深入的理论研究，其中最著名的结论之一当属邱奇-图灵论题（Church-Turing Thesis）：一切直觉可计算的问题均可由图灵机模拟。随着计算机科学的发展与成熟，“直觉可计算”这个抽象概念被计算理论中的“算法”（Algorithm）所取代，邱奇-图灵论题也被等价表述为：图灵机是可以实现任何算法的通用计算机。1945 年，冯·诺依曼提出制造计算机的基本原则：采用二进制逻辑，程序存储执行，以及计算机由五个部分组成（运算器、控制器、存储器、输入设备、输出设备），史称“冯·诺依曼体系结构”。1946 年，世界上第一台通用计算机 ENIAC（Electronic Numerical Integrator And Computer）在美国宾夕法尼亚大学研制成功，它占地面积约 170 平方米，包含 17840 根电子管，但是没有使用冯·诺依曼体系结构。1947 年，贝尔实验室的三位物理学家肖克利、巴丁和布拉顿发明了晶体管，使得基于冯·诺依曼体系结构的通用计算机在硬件上有了实现的可能。数字逻辑电路的发展催生出了通用电子计算机，而后通用电子计算机逐渐成为现代社会的重要生产工具，无时无刻地促进着社会的进步。1965 年，英特尔（Intel）创始人之一摩尔提出了计算机历史上著名的摩尔定律（Moore's Law）：每十八个月计算机性能翻一倍，而价格降一半。摩尔定律揭示了计算机技术日新月异的进步速度，同时也让人们意识到经典计算机的发展终究要面临物理极限的问题，这包括集成电路的密度、电子的量子效应、元器件的热效应等。量子计算机正是为了解决这一问题探索的产物。

1982 年，费曼提出了量子计算的概念${}^{\left[1\right]}$，指出以量子力学为基础的计算机在处理特定问题时，具有远超经典计算机的计算优势，这被认为是量子计算机最早的构想。1985 年，多伊奇（David Deutsch）将费曼的思想具体化并提出量子图灵机模型${}^{\left[2\right]}$。通过对量子图灵机性质的研究，多伊奇预言了量子计算机的潜在能力。1994 年，秀尔（Peter Shor）提出了质因数分解的量子算法，该算法的计算速度是已有经典算法的指数倍${}^{\left[3\right]}$。这意味着当下最被广泛使用的公钥密码体系——RSA 加密算法${}^{\left[4\right]}$可以被量子计算机高效破解，进而刺激了科学家们对量子计算的研究，推动了量子计算和理论计算机科学的发展。1995 年，格罗弗（Lov Grover）提出非结构化量子搜索算法${}^{\left[5\right]}$，相比最好的经典算法有平方级加速。非结构化搜索是现实生活中最常见的问题之一，因此格罗弗算法有广阔的应用场景。除了量子算法上的进展，量子计算机设计也蓬勃发展起来。2011 年，D-Wave 公司发布了“全球第一款商用型”量子计算机 "D-Wave One"，拥有 128 个量子比特，被用于先进武器设计和雷达开发测试等领域。2019年，IBM 展示世界首款基于量子电路的商业化量子计算机 "IBM Q System One"，它拥有 20 个量子比特，可通过 IBM 云服务接入。同年，谷歌（Google）的 Frank Arute 等人在世界顶级期刊《自然》上发表最新研究成果${}^{\left[6\right]}$：拥有 54 个量子比特的超导量子计算机 "Sycamore" 在执行特定任务时，计算速度远超最先进的经典计算机。2020 年，中国科学技术大学潘建伟团队研制出 76 个光子的量子计算原型机“九章”。2021 年，中国科学技术大学潘建伟团队发布 66 量子比特可编程超导量子计算原型机“祖冲之号”。这些技术上的成就意味着“有噪中等规模量子”时代（Noisy Intermediate-Scale Quantum, NISQ）${}^{\left[7\right]}$即将到来。拥有 50-100 量子比特以及高保真量子门的量子计算机，让量子计算得以踏足经典计算机无力探索的新领地。

另一方面，自费曼提出用量子计算的概念后，量子硬件研究工作也得到飞速发展。作为量子计算的硬件基础，科研人员提出了很多有前景且具备操作基础的量子硬件平台，代表性平台包括

• 超导量子计算（Superconducting Quantum Computing），
• 离子阱量子计算（Trapped Ion Quantum Computing），
• 里德堡原子量子计算（Rydberg Atom Quantum Computing），
• 核磁共振量子计算（Nuclear Magnetic Resonance Quantum Computing, NMR），
• 半导体量子点量子计算（Semiconductor Quantum Dot Quantum Computing），
• 光量子计算（Photonic Quantum Computing），
• 光腔量子计算（Cavity QED Quantum Computing），
• 氮空穴色心量子计算（Nitrogen Vacancy Center Quantum Computing），以及
• 拓扑量子计算（Topological Quantum Computing）。

这些技术的发展一方面取决于人们制造工艺的进步，另一方面也取决于量子计算基础理论的突破。类比经典计算机经历的“电子管 → 晶体管 → 集成电路 → 超大规模集成电路”的发展历程，量子计算机硬件尚处于初级阶段。不同量子硬件平台正齐头并进，蓬勃发展，向着规模化商用量子计算机的方向不断前行。

本章接下来的内容介绍量子计算的基本知识，由三个部分组成：

1. 在第二节中，我们介绍学习量子计算必要的数学知识：线性代数。量子计算所涉及的线性代数为复线性代数，和一般以实线性代数为主的线性代数教程稍有差异，不过这并不会增加太多学习难度。第二节中包含了复线性代数中的向量、矩阵、内积、张量积以及谱分解定理等概念。特别地，我们引入狄拉克符号，以简化量子计算中的部分推演过程。习惯狄拉克符号表示有助于更好地学习后续的量子计算。
2. 在第三节中，我们介绍量子计算的基本单元：量子比特，量子门，以及量子测量。利用这些基本单元，我们以“贝尔态的制备和测量”为例，演示一个简单的量子计算过程。需要说明的是，量子计算有几种不同但是等价的计算模型：量子电路模型（Quantum Circuit Model），量子图灵机模型（Quantum Turing Machine Model），基于测量的量子计算模型（Measurement-Based Quantum Computing Model），和量子随机存储器模型（Quantum Random Access Memory Model）等。本教程采用的是量子电路模型，它将信息存储在量子比特中，通过类似经典逻辑门的量子门来实现量子计算。
3. 在第四节中，我们介绍量子计算的物理基础：量子力学，简要回顾了上个世纪初量子力学从诞生到繁荣的历史过程。我们从经典理论无法解释的黑体辐射问题出发，引出能量量子化的概念，逐步拓展到微观原子结构，介绍原子能级结构、光量子、物质波等诸多量子化的概念。紧接着我们介绍量子力学理论基础，简要介绍了海森堡矩阵力学和薛定谔波动方程两种等价的量子力学描述方法，并在此基础上通过数学公设化的思想将量子力学基本理论抽象成四大公设。而这四大公设恰恰对应于第三节中量子比特、单量子比特门、量子测量和多量子比特门四部分，这里将使用更抽象的形式重述一遍。最后我们将结合具体的物理实际过程，阐述四大公设在量子力学和量子计算上的作用。

本章节部分内容参考 Nielsen 和 Chuang 编写的量子计算和量子信息经典教材${}^{\left[8\right]}$，感兴趣的读者可自行查阅。

在学习与使用本知识库的过程中，欢迎积极反馈建议或者意见至 quantum at baidu.com，这将有助于我们不断地优化迭代量易简。

参考资料

[1] Feynman, Richard P. "Simulating physics with computers." International Journal of Theoretical Physics 21.6 (1982): 467–488.

[2] Deutsch, David. "Quantum theory, the Church–Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985): 97-117.

[3] Shor, Peter W. "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS'94). IEEE, 1994.

[4] Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21.2 (1978): 120-126.

[5] Grover, Lov K. "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 1996.

[6] Arute, Frank, et al. "Quantum supremacy using a programmable superconducting processor." Nature 574.7779 (2019): 505-510.

[7] Preskill, John. "Quantum Computing in the NISQ era and beyond." Quantum 2 (2018): 79.

[8] Nielsen, Michael A., and Isaac L. Chuang. "Quantum Computation and Quantum Information: 10th Anniversary Edition." Cambridge University Press, 2010.

最后更新时间：2021年12月20日