A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine.

—— A. M. Turing

从人类生产、生活的早期开始，计算就一直伴随着人类的进步与发展。从结绳记事到现在利用超级计算机模拟宇宙的演化，计算理论已经从早期的算术发展成为一门庞大的学科，而计算工具也从早期的算盘发展到“太湖之光”这样的超级计算机。

在图灵（Turing）于1936 年提出图灵机模型（丘奇（Church）也提出了等价的模型）以后，计算理论和计算工具都得到了飞速发展。图灵模型使得人们能够精确地定义算法，其本身也成为现代计算机的雏形。基于Church-Turing论题，任何可计算函数都可通过图灵机计算（也可看作可计算函数的定义）。Church-Turing论题也说明，函数的可计算性与计算模型、实现模型的物理理论（经典的还是量子的）以及实现计算的一切外在因素等都无关。计算的普适性使我们可以在同一个计算模型下通过“编程”的方式实现不同的计算任务，进而可以比较不同计算任务的复杂程度（所消耗的时间和空间资源），而计算复杂度问题是计算科学的核心问题之一。

▲ 量子图灵机Feynman路径示意图

量子图灵机的跃迁过程形成基构型上的一系列Feynman 路径Pα (如α = (α1, α2, · · · , αf ) 为一条路径的标识)，基构型|αf ⟩ 上的振幅Aαf 等于所有以|αf ⟩ 为终点的Feynman 路径振幅APα 之和。图中蓝色折线示意了从基构型|α0⟩ 到|αf ⟩ 的3 条不同Feynman 路径

尽管不同的计算模型（如确定性图灵机与量子图灵机）在问题的可计算性上是一致的，但它们对同一问题的计算效率并不相同。因此，不同计算模型在解决相同问题时所消耗的资源也就不尽相同。研究基于不同普适计算模型的计算复杂度之间的关系尤其重要。量子计算基于量子力学，其量子叠加特性使得它在解决某些问题时比经典计算机拥有更高的效率。量子计算的这一优势最早是费曼(Feynman)在1982年指出，并用以解决多体物理中经典模拟的希尔伯特空间随系统规模指数增长的难题（指数墙问题）。如果说Deutsch-Jozsa 算法第一次让人们在一个人工构造的问题上看到了量子计算的优势，那么，Shor算法就切实地让人们在一个实际的重大问题上看到了量子计算的颠覆性能力：它可在多项式时间内解决大数因式分解问题，相较于任何已知的经典算法都有指数加速。鉴于大数因式分解问题在RSA密钥系统中的核心作用，量子计算的价值得到了充分的展现。而随后Grover发现的以其名字命名的搜索算法，再次提供了量子计算相对于经典计算具有算力优势的经典案例。

▲ 变分量子本征值求解器（variational quantum eigensolver，VQE)算法流程图：QPU为量子处理单元，在量子系统上完成；而CPU为经典处理单元，在经典计算机上完成

除了算法优势，量子计算还解决了提升经典算力的另外两个瓶颈。一直以来，计算机算力的提高都依赖于微处理器芯片集成度的提高，集成度的提高遵循Intel公司的创始人之一Moore提出的以他名字命名的定律：在价格不变的情况下，芯片的集成度每18—24个月提高一倍。在过去的几十年间，这一定律都被很好地遵守。显然，这一趋势无法永远持续下去。一方面，随着元件集成度的提高，芯片单位体积内的散热将增加，进而限制集成度的上限；另一方面，当元件做到纳米甚至是埃的尺度时，微观客体的运行机制将服从量子力学（比如量子隧穿效应将不可避免），芯片将不再遵循经典理论（芯片设计理论基于经典理论）。而量子计算可以同时解决这两个方面的问题。量子计算原理上遵循量子力学，第二个问题自动解决。而对于计算机的热耗效应，美国科学家Landauer发现，热耗产生于计算过程中的不可逆操作，如果消除了计算过程中的不可逆操作，从物理上讲，就不存在计算的能耗下限。因此，可逆计算就可以解决热耗的问题。而量子计算中的操作是幺正变换，天然具有可逆性。

量子计算的算力优势最终需在具体的物理系统上实现。自离子阱系统作为实现量子计算的方式提出以来，超导系统、光学系统、量子点系统、中性原子系统以及拓扑系统等不同系统都被视为实现量子计算的潜力系统进行研究。虽然各个量子系统都有其自身的优势，但同时也存在内在的不足，迄今为止还没有一个能在所有DiVencenzo判据上都表现良好的系统。基于离子阱和超导约瑟夫森结的系统是现阶段相对成熟的系统，是实现普适量子计算的强有力候选。事实上，人们已经能在超导系统中实现中等规模的含噪声量子比特系统（NISQ），在此系统中，一些特定的采样问题（玻色采样和随机线路采样）已初步展示了量子计算相对于经典计算的优势。尽管已经取得了巨大的成就和进展，但要实现量子计算在重要问题上的应用以及普适量子计算，还需对量子比特进行编码，对噪声进一步压缩。总而言之，实现容错的普适量子计算仍还要解决一系列理论和技术难题。

（韩永建, 郭光灿著. 北京: 科学出版社, 2023.10）全面而系统地介绍了量子计算领域的基本理论、核心概念、关键方法和重要结论，并兼顾近期的前沿进展。本书的目的是为学习量子计算的研究生和科研工作者提供量子计算全面而系统的知识和技术（书中涉及理论及技术的Credit完全归属于原发现者），我们期望读者不仅能从中学到量子计算的相关知识，也能学到解决相关问题所需的典型技能，未来有能力解决科研中遇到的新问题。

本书共5 章。每一章都尽量做到自明且逻辑独立，既突出了每个章节的逻辑完整性，也强调了不同章节间内容上的联系，保证了量子计算学科的完整性和自洽性：

  • 第一章主要介绍了经典计算和量子计算的复杂性理论，并阐明计算复杂度与物理理论之间的关系；

  • 第二章主要介绍了基本的量子算法；

  • 第三章介绍了几个不同的量子计算模型以及它们与线路模型之间的等价性；

  • 第四章介绍了实现量子计算的DiVencinzo判据以及基于离子阱系统、超导系统和光学系统的量子计算；

  • 第五章介绍了量子纠错码以及容错量子计算的基本理论和方法。

由于本书篇幅较大，在使用本书进行学习和教学时，可根据自身的背景和目标进行选择性使用。

特别感谢中国科学技术大学周正威教授为第一章提供了部分讲义。本书在写作过程中得到了中国科学技术大学陈哲、陶思景、王以煊、张昊清、徐小惠等众多研究生的协助，在此表示感谢。中国科学技术大学林毅恒教授、周祥发副教授、吴玉椿副教授，清华大学魏朝晖副教授，中山大学李绿周教授，福建师范大学叶明勇教授，南京大学于扬教授、姚鹏晖副教授，中国工程物理研究院李颖研究员，国防科技大学陈平形教授，中国人民大学张威教授，中国海洋大学顾永建教授，电子科技大学李晓瑜副教授，合肥幺正量子科技有限公司贺冉博士等同仁对本书的书稿进行了阅读并提供了宝贵意见，一并表示感谢。

本书是2022 年度中国科学技术大学研究生教育创新计划项目优秀教材出版项目。

本文摘编自《量子计算导论（全2 册）》（韩永建, 郭光灿著. 北京: 科学出版社, 2023.10）一书“前言”，有删减修改，标题为编者所加。

（量子信息前沿丛书）

ISBN 978-7-03-076640-3

责任编辑：钱 俊 李香叶

本书全面而系统地介绍了量子计算领域的基本理论、核心概念、关键方法和重要结论，并兼顾近期的前沿进展。本书内容主要包括：经典和量子计算的复杂性理论、计算复杂度与物理理论间的关系；基本量子算法；不同量子计算模型及其与量子线路模型的等价；基于离子阱系统、超导系统及光学系统的量子计算物理实现；量子纠错码及容错量子计算。本书中的重要结论都给出了详尽的证明，使读者不仅能学到量子计算的相关知识，也能学到解决这类问题所需的典型技能，有能力解决未来科研中遇到的新问题。

本书适合量子科学与技术专业、物理专业及计算机专业的高年级本科生、研究生、大学教师和量子计算相关科技工作者阅读和参考。

（本文编辑：刘四旦）

一起阅读科学!

科学出版社│微信ID：sciencepress-cspm

专业品质 学术价值

原创好读 科学品位

科学出版社视频号

硬核有料 视听科学