面向计算机科学家的量子计算

要想学好量子计算，首先要熟悉关于量子世界的一些基本事实。 在本介绍中，一些独特的功能介绍了量子力学，以及它们影响我们即将讲述的故事的方式

量子计算是一个多学科领域。 本书致力于利用一些 量子力学奇妙的方面扩大我们的计算视野。通过介绍面向计算机科学领域的量子计算， 本书将带领读者浏览这个引人入胜的尖端研究领域。本书以一种通俗易懂但又严谨的方式，采用了每个计算机科学的学者和学生都熟悉的方法和技术。读者无需具有任何高等数学或物理背景。前四章介绍的背景知识，包括复数，复向量空间，从经典计算到量子计算的飞跃， 和基础量子理论。在随后的七章，作者分别从计算机科学的特定角度来描述量子计算的不同方面，比如：计算机体系结构， 算法，编程语言，理论计算机科学，密码学，信息理论和硬件。本书为计算机科学专业的学生和研究人员提供循序渐进的示例，两百多个练习和相应的答案，以及应用量子计算思想的编程练习。

第1章复数1
1.1基本定义1
1.2复数的代数3
1.3复数的几何7

第2章复向量空间17
2.1  n作为主要示例17
2.2定义、属性和示例20
2.3基和维度28
2.4内积和希尔伯特空间34
2.5特征值和特征向量39
2.6厄米矩阵和酉矩阵40
2.7向量空间的张量积43

第3章从经典计算到量子计算的飞跃48
3.1经典确定性系统48
3.2概率系统51
3.3量子系统58
3.4装配系统65

第4章基础量子理论70
4.1量子态70
4.2可观察量78
4.3测量86
4.4动力学88
4.5组装量子系统90

第5章体系结构95
5.1比特和量子比特95
5.2经典的逻辑门100
5.3可逆门104
5.4量子门109第6章算法118
6.1Deutsch算法118
6.2DeutschJozsa算法125
6.3Simon的周期性算法131
6.4Grover的搜索算法138
6.5Shor的因子分解算法145

第7章编程语言157
7.1量子世界中的编程157
7.2量子汇编编程158
7.3面向更高层次的量子编程165
7.4量子计算机之前的量子计算170
〖1〗〖2〗面向计算机科学家的量子计算〖1〗目录
第8章理论计算机科学171
8.1确定性和非确定性计算171
8.2概率计算176
8.3量子计算180

第9章密码学188
9.1经典密码学188
9.2量子密钥交换I: BB84协议192
9.3量子密钥交换Ⅱ: B92协议197
9.4量子密钥交换Ⅲ: EPR协议198
9.5量子隐形传态200

第10章信息论205
10.1经典信息和香农熵205
10.2量子信息与冯·诺依曼熵207
10.3经典和量子数据压缩213
10.4纠错码218

第11章硬件221
11.1量子硬件: 目标和挑战221
11.2实现量子计算机Ⅰ: 离子阱225
11.3实现量子计算机Ⅱ: 线性光学227
11.4实现量子计算机Ⅲ: 核磁共振和超导体228
11.5量子产品的未来229附录A量子计算的历史参考书231
A.1阅读科学文章231
A.2计算模型232
A.3量子门232
A.4量子算法和实现233
A.5量子密码学234
A.6量子信息234
A.7更多里程碑？235

附录B选择的练习答案236

附录C量子计算MATLAB实验257
C.1玩转MATLAB257
C.2复数和矩阵257
C.3量子计算260

附录D及时了解量子新闻: 网络上的和文献中的量子计算263
D.1及时了解热门新闻263
D.2与科学文献保持同步264
D.3与时俱进的最佳方式265

附录E选定的学生演讲主题266
E.1复数267
E.1.1复数的历史267
E.1.2复平面几何267
E.1.3黎曼球体和莫比乌斯变换267
E.2复向量空间268
E.2.1计算机图形学中的矩阵268
E.2.2向量空间的历史268
E.3从经典到量子的飞跃268
E.3.1惠更斯原理和波动力学268
E.3.2量子橡皮擦268
E.4基本量子理论269
E.4.1解释量子理论269
E.4.2EPR悖论269
E.4.3贝尔定理269
E.4.4KochenSpecker 定理270
E.4.5薛定谔的猫270
E.5架构270
E.5.1麦克斯韦妖、朗道尔原理和信息物理学270
E.5.2经典可逆计算271
E.5.3更多量子门和通用量子门271
E.6算法271
E.6.1概率算法271
E.6.2隐藏子群问题271
E.6.3经典因式分解算法272
E.6.4傅里叶变换272
E.7编程语言272
E.7.1SQRAM: 成熟的量子汇编器272
E.7.2QCL和Q: 比较272
E.7.3函数式量子编程: QML273
E.8理论计算机科学273
E.8.1素性测试273
E.8.2量子有限自动机273
E.8.3量子Oracle计算273
E.9密码学274
E.9.1RSA274
E.9.2量子认证274
E.10信息论274
E.10.1量子游戏274
E.10.2复合系统的量子熵274
E.10.3量子纠错码275
E.11硬件275
E.11.1退相干和经典世界的出现275
E.11.2现有量子硬件方法的比较275
E.11.3量子密码学的当前实现275

参考文献276

量子计算是一个多学科领域。本书致力于利用一些量子力学奇妙的方面扩大我们的计算视野。通过介绍面向计算机科学领域的量子计算，本书将带领读者浏览这个引人入胜的尖端研究领域。本书以一种通俗易懂但又严谨的方式，采用了每个计算机科学的学者和学生都熟悉的方法和技术。读者无须具有任何高等数学或物理背景。前4章介绍的背景知识，包括复数、复向量空间、从经典计算到量子计算的飞跃和基础量子理论。随后的7章分别从计算机科学的特定角度描述量子计算的不同方面，如计算机体系结构、算法、编程语言、理论计算机科学、密码学、信息论和硬件。本书为计算机科学专业的学生和研究人员提供循序渐进的示例、200多个练习和相应的答案，以及应用量子计算思想的编程练习。量子计算是一个交叉学科领域引人入胜的新领域，涉及计算机科学、数学和物理学，努力利用量子力学的一些不可思议的方面以拓宽我们的计算视野。本书介绍了量子计算中一些最令人兴奋和有趣的话题。一路走来，将会有一些关于我们生活的宇宙中的惊人事实，以及关于信息和计算的概念。
本书与目前大多数其他关于量子计算的可用书籍有不同的风格。首先，本书不要求读者有很多数学或物理背景。计算机科学课程二年级或以上的任何人都可以阅读本书。我们专门为计算机科学家编写了这本书，并相应地对其进行了调整: 数学复杂度最低要求是，离散结构的第一门课程，以及健康的好奇心。因为本书是专门为计算机人员编写的，所以在整本书中除有许多练习外，还添加了许多编程练习。这些练习提供一个有趣的方式来学习相关的材料，并使得读者获得对该主题的真实感受。
有微积分恐惧症的读者知道导数和积分几乎没有出现在我们的文本中会很高兴。我们尽量避免微分、积分和所有高等数学，仔细选择那些对量子计算的基本介绍至关重要的主题。因为我们专注于量子计算的基础，所以可以将自己限制在有限维所需要的数学。令人惊讶的是，量子计算的最大份额可以在没有复杂的高等数学的情况下完成。
尽管如此，我们还是要强调这是一本技术教科书。
该领域的大多数书籍都提供了关于量子力学的所有内容启蒙。许多书籍要求读者对经典力学有一定的了解，本书没有这些要求。我们只讨论基本理解，量子计算本身只是一个研究领域所需的东西，尽管我们引用了更多关于高级主题的学习资源。
有人认为量子计算仅在物理学范畴内。其他人则认为该主题纯粹是数学。而我们强调的是量子计算的计算机科学方面。
我们无意让这本书成为量子计算的终结。有几个话题甚至没有触及，还有几个话题只是简要介绍它们的内容。在撰写本书时，量子计算的圣经是 Nielsen 和 Chuang的优秀作品［1］——《量子计算和量子信息》。他们的书中包含了当时几乎所有已知的量子计算。我们希望本书可以作为那本书的预读本。
本书的特点
这本书几乎是完全独立的。我们不要求读者拥有大量技能，甚至对于复数的主题，高中所学的复数概念已经给予了相当全面的评价。
这本书包含许多已解决的问题和易于理解的描述。我们不只是介绍理论，我们还通过几个例子解释它。这本书还包含许多练习，强烈推荐读者尝试完成练习。
我们还加入了大量的编程练习。这些是可以在笔记本电脑上进行的动手练习，以更好地理解概念（这也是一个很好的学习方法）。需要指出，这里的练习完全与编程语言无关。学生应该用自己最熟悉的语言编写程序。我们也不要求编程规范。如果声明式编程是你最喜欢的方法，那就去用它。如果面向对象编程是你的游戏，那就使用它。编程练习建立在彼此之上。上一次编程练习中创建的功能在以后的练习中可以使用并修改。此外，在附录C中，我们展示了如何用MATLAB制作一个小型量子计算仿真器，或如何使用现成的仿真器。（之所以选择MATLAB，是因为它非常易于构建快速而基本的原型，这要归功于其大量的内置数学工具）
本书似乎是第一个以重要的方式来处理量子编程语言。到目前为止，只有一些关于这个话题的研究论文和综述文献。第 7 章描述了这个不断扩展的领域的基础知识。也许一些读者将会受到启发，为量子编程做出贡献！
〖1〗〖2〗面向计算机科学家的量子计算〖1〗前言本书还包含几个附录，它们对进一步学习是很重要的。
 附录A带领读者浏览量子计算领域的主要论文。这篇参考书目文章由Jill Cirasella撰写，她毕业于布鲁克林学院，是图书馆的计算科学专家。Jill除拥有硕士学位，还拥有图书馆和信息科学专业的逻辑学硕士学位，她的硕士论文是关于经典和量子图的算法。这种独特的双背景使她有资格提出建议，有能力进一步描述阅读材料。
 附录B包含课文中一些练习的答案。其他解决方案也可以在本书的网页上找到。我们强烈敦促学生自己做练习，然后将他们的答案与我们的答案进行核对。
 附录C使用MATLAB和已建立的行业标准展示本书中描述的大部分数学运算。MATLAB 有许多用于操作复杂矩阵的例程: 我们简要回顾最有用的矩阵并展示读者使用免费提供的MATLAB量子仿真器Quack，快速而毫不费力地完成一些量子计算实验。
 附录D同样由Jill Cirasella撰写，描述了如何使用在线资源来跟随量子计算的发展。量子计算是一个快速发展的领域，附录D提供了查找相关信息和公告的指南。
 附录E是学生可能演讲的主题列表。这里不仅简要介绍学生在课堂上可能演讲的不同主题，还提供了一些寻找演讲材料的方法。
本书的组织结构
本书以两章数学预备知识开始。第1章介绍复数的基础知识，第2章介绍复向量空间。虽然第1章的大部分内容在高中已经学过，但我们认为有必要复习一下。第2章的大部分内容对于学过线性代数课程的学生来说是已知的。我们故意没有将这些章节放入本书的附录部分，因为数学对理解到底发生了什么是必需的。读者可以放心地跳过前两章，也可以略读这些章节，然后再返回这两章参考，使用索引和目录查找特定主题。
第3章温和地介绍了一些在整个文本的其余部分可能遇到的概念。使用简单的模型和简单的矩阵乘法，我们展示了量子力学的一些基本概念，然后在第4章中正式展开。第5章介绍量子计算的一些基本架构。在这里可以看到量子比特的概念（一般化的量子比特）和逻辑门的量子模拟。
一旦理解了第5章，读者就可以放心地继续选择阅读第6～11章。每章的标题均取自计算机科学系一门典型的课程。这些章节从给定课程的角度着眼于量子计算的那个子领域。这几章彼此独立。我们鼓励读者研究与自己喜欢的课程相对应的特定章节。首先学习你喜欢的主题，然后从那里再继续阅读其他章节。
本书中最难解决的问题之一是如何将两个量子系统组合起来，或“纠缠”的量子系统。这个系统的数学运算在第2.7节中已经介绍。图0.1各章的依赖关系
但在第3.4节中又进一步提出，并在第4.5节中再次介绍。读者可以把这些部分关联在一起阅读。图0.1总结了各章的依赖关系。
本书可以采取多种方式用作课程教材。我们希望导师自己找方法。以下三个计划供参考:
(1) 提供一定深度的课程，可能涉及以下内容: 第1～5章。在此背景下，深刻学习第6章（“算法”）。至少可以花一个学期的三分之一时间学习第6章。之后，学生对整个量子计算会有一个很好的感觉。
(2) 如果喜欢广度，则可以从每部分中挑选一个或两个高阶章节学习。
(3) 对于更高级的课程（需要线性代数和一些数学复杂性的知识），建议学生自己阅读第1～3章，然后从第4章开始学习本书其余的大部分内容。
如果本书作为课程教材，我们强烈建议学生进行演讲。附录E中提到了选择的主题。
尽管我们试图在本书中包含尽量多的主题，但不可避免地，有些主题不得不排除。由于篇幅原因，我们省略了以下内容:
 第8章中许多复杂的证明;
 关于预言机计算的结果;
 （量子）傅里叶变换的细节，以及最新的硬件实现。
我们为进一步研究这些主题以及其他主题提供参考，并贯穿本书始终。
辅助资源
本书链接:
http://spider.sci.brooklyn.cuny.edu/～noson/qctext.html
该网页包含
 定期更新书籍;
 链接到有关量子计算的有趣书籍和文章;
 附录B中未解决的某些习题的答案，以及勘误表。
鼓励读者将所有更正发送至原作者，Yanofsky教授:
[email protected]
或者本书的译者，何红梅教授
[email protected]
帮助我们改进这本书！
致谢
我们俩有幸在亚历克斯·海勒温文尔雅的指导下撰写了我们的博士论文。海勒教授写了以下请阅读Bass等的文献的1349页［2］.关于他的老师Samuel（Sammy）Eilenberg和Sammy的数学:
正如我所理解的那样，Sammy 认为数学的最高价值在于，不是在似是而非的深度，也不是在克服压倒性的困难，而是提供明确的清晰度来阐明潜在的秩序。
为揭示数学结构的潜在秩序而进行的永无止境的斗争一直是海勒教授永恒的目标，他竭尽全力传递他的思想给他的学生。我们从他清晰的数学视野和观点中获益良多，也看到体现在一个人身上的最佳状态——古典而沉思的生活理念。我们永远感激他。
在纽约期间，我们也有幸与世界上重要的逻辑学家之一——Rohit Parikh 教授互动，他对该领域的开创性贡献相匹配于他持久的承诺——促进年轻研究人员的工作。除了为我们打开迷人的前景，Parikh 教授不止一次鼓励我们遵循新的思想方向。非常感谢他的指导。
我们都获得了纽约城市大学研究生院的数学系博士学位。我们感谢他们为我们提供了一个温暖友好的环境来学习，并学习到了真正的数学。第一作者还感谢整个布鲁克林学院大家庭，特别是计算机和信息科学系对这项工作的支持和大力帮助，以及布鲁克林学院和研究生中心的几位教职员工。
欢迎阅读和评论本书的部分内容: Michael Anshel, David Arnow, Jill Cirasella, Dayton Clark, Eva Cogan, Jim Cox, Scott Dexter, Edgar Feldman, Fred Gardiner, Murray Gross, Chaya Gurwitz, Keith Harrow, Jun Hu, Yedidyah Langsam, Peter Lesser, Philipp Rothmaler, Chris Steinsvold, Alex Sverdlov, Aaron Tenenbaum, Micha Tomkiewicz, Al Vasquez, Gerald Weiss, and Paula Whitlock。他们的评论成就了这本书。谢谢你们！
很幸运有很多布鲁克林学院的学生和研究生中心阅读并评论早期的草稿: Shira Abraham, Rachel Adler, Ali Assarpour, Aleksander Barkan, Sayeef Bazli, Cheuk Man Chan, Wei Chen,Evgenia Dandurova, Phillip Dreizen, C. S. Fahie, Miriam Gutherc, Rave Harpaz, David Herzog, Alex Hoffnung, Matthew P. Johnson, Joel Kammet, Serdar Kara, Karen Kletter, Janusz Kusyk, Tiziana Ligorio, Matt Meyer, James Ng, Severin Ngnosse, Eric Pacuit, Jason Schanker, Roman Shenderovsky, Aleksandr Shnayderman, Rose B. Sigler, Shai Silver, Justin Stallard, Justin Tojeira, John Ma Sang Tsang, Sadia Zahoor, Mark Zelcer, and Xiaowen Zhang。感谢他们的帮助。
许多人参与审查了部分或全部文本: Scott Aaronson, Stefano Bettelli, Adam Brandenburger, Juan B. Climent, Anita Colvard, Leon Ehrenpreis, Michael Greenebaum, Miriam Klein, Eli Kravits, Raphael Magarik, John Maiorana, Domenico Napoletani, Vaughan Pratt, Suri Raber, Peter Selinger, Evan Siegel, Thomas Tradler, and Jennifer Whitehead。他们的批评和有益意见深受赞赏。
感谢 Peter Rohde 创建并向所有人提供他的 MATLAB qemulator Quack，也让我们在附录中使用它。我们很乐意使用这个MATLAB qemulator，且希望我们的读者也乐意。
除了写两个精彩的附录，我们友好的邻里图书管理员Jill Cirasella始终用一封电子邮件提供有用的建议和支持，谢谢Jill！
非常感谢剑桥大学出版社的编辑 Heather Bergman，她从一开始就相信我们的项目，指导我们完成这本书，并在所有问题上提供无尽的支持。没有她，这本书不会存在。谢谢Heather！我们有幸让一位真正出色的编辑多次检查大部分文本。Karen Kletter 是一位好朋友，做得非常出色。我们也欣赏每次我们递给她修改过的草稿时，她都没有否定我们的工作。
当然，所有的错误都是我们自己导致的。
如果没有我女儿 Hadassah 的帮助，这本书是不可能写成的。
她增加了我写这本书的意义、目的和快乐。
N.S.Y
我亲爱的妻子罗斯 （Rose），以及我们的两只奇妙而不知疲倦的猫Ursula and Buster，在漫长的写作过程中缓解了我的压力。写作和编辑的痛苦时光: 我对他们表示感谢和爱。（Ursula是一个科学家猫，会读这本书。Buster会用它有力的爪子把它撕碎。）
M.A.M
译者感谢
我们非常感谢Noson S. Yanofsky教授——原作的第一作者，感谢他给了我们本书的电子版，这大大减轻了我们翻译工作者的负担。在翻译后期，他将纠错表发给我们，帮助我们提高了翻译的质量。当然，其中肯定还有被忽略的错误。我们将继续核查并纠正发现的任何错误。我们也感谢读者对本书感兴趣。如果读者发现错误，也请联系我们，并给予指正。还要感谢清华大学出版社的老师的指导和帮助!
何红梅,朱振环
简介〖*2〗量子世界的特征要想学好量子计算，首先要熟悉关于量子世界的一些基本事实。在本介绍中，通过一些独特的功能介绍了量子力学，以及它们影响我们即将讲述的故事的方式本简介不适合介绍技术细节。一些概念包含在文本中，其中一些只能在量子力学教科书中找到。第4章结尾有一些简单而详细的量子物理学介绍。。
从实数到复数
量子力学与大多数其他科学分支的不同之处在于它使用复数的基本方法。最初创建复数作为数学好奇心: i=-1是多项式方程x2=-1确认的“虚构”解。随着时间的推移，一整座数学大厦用这些“虚构”的数字构成。复数一直孤独地让数学家忙了几个世纪，而物理学家却成功地忽略了这些抽象创作。然而，随着对波力学的系统研究，情况发生了变化。
引入傅里叶分析后，研究人员了解到，紧凑型表示波的方法是使用复数函数。已经证明，这是在量子理论中使用复数的重要一步。早期的量子力学主要基于波动力学。
乍一看，我们似乎没有在“实数”世界中体验复数。一个杆的长度是实数，而不是复数。今天外面的温度是73，而不是(32-14i)°。化学过程的时间量需要32.543秒，而不是14.65i秒。有人可能想知道复数在任何物理世界的讨论中担任什么角色。很快就会变成显然，它们在量子力学中发挥着重要的，甚至是必不可少的作用。我们将在本书的第1章和第2章中探讨复数。
从单一状态到状态叠加
为了在这个世界上生存，人在婴儿时期必须明白每一个对象存在于一个独特的位置并处于一个明确定义的状态，即使我们不看着它。虽然这对于大物体来说是正确的，但量子力学告诉我们，对于非常小的物体，这是错误的。一个微观物体可以“模糊地” 一次存在不止一个地方。而不是一个物体处于一个位置或另一个位置，我们说它处于 “叠加态”，即在某种意义上，它同时在多个位置。不仅空间位置受制于这种 “朦胧”，其他熟悉的物理特性也是如此，如能量、动量，以及量子世界独有的某些属性，如 “自旋”。
我们实际上并没有看到状态的叠加。每次我们看，或更多正确地“测量”，状态的叠加，它“坍缩”成一个单一的明确定义的状态。然而，在我们测量它之前，它同时处于多态。有人对这些说法持怀疑态度是有道理的。毕竟怎么可能相信不同于每个婴儿都知道的事实？然而，我们将用某些实验表明这正是发生的情况。
从地方性到非地方性
现代科学的核心是这样一种观念，即物体只直接受附近物体或力量的影响。为了确定一个现象为什么会发生在某个地方，必须检查那个地方附近“附近” 是指任何足够接近以影响对象的东西，用物理术语来说，即过去的任何事情物体的光锥。的所有现象和力量。这被称为“局部性”，即物理定律以局部方式起作用。其中量子力学比较显著的方面之一是定律预测某些以非本地方式工作的效应。
两个粒子可以这种方式连接或“纠缠”，对其中一个执行的操作可以立即产生影响。
在光年之外的另一个粒子上，这种“幽灵般的远距离动作”，使用爱因斯坦丰富多彩的表达，是量子力学令人震惊的发现之一。