前言
量子计算是一个多学科领域。本书致力于利用一些量子力学奇妙的方面扩大我们的计算视野。通过介绍面向计算机科学领域的量子计算，本书将带领读者浏览这个引人入胜的尖端研究领域。本书以一种通俗易懂但又严谨的方式，采用了每个计算机科学的学者和学生都熟悉的方法和技术。读者无须具有任何高等数学或物理背景。前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教授:
noson@sci.brooklyn.cuny.edu
或者本书的译者，何红梅教授
maryhhe@yahoo.com
帮助我们改进这本书！
致谢
我们俩有幸在亚历克斯·海勒温文尔雅的指导下撰写了我们的博士论文。海勒教授写了以下请阅读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 qemulator Quack，也让我们在附录中使用它。我们很乐意使用这个MATLAB qemulator，且希望我们的读者也乐意。
除了写两个精彩的附录，我们友好的邻里图书管理员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章中探讨复数。
从单一状态到状态叠加
为了在这个世界上生存，人在婴儿时期必须明白每一个对象存在于一个独特的位置并处于一个明确定义的状态，即使我们不看着它。虽然这对于大物体来说是正确的，但量子力学告诉我们，对于非常小的物体，这是错误的。一个微观物体可以“模糊地” 一次存在不止一个地方。而不是一个物体处于一个位置或另一个位置，我们说它处于 “叠加态”，即在某种意义上，它同时在多个位置。不仅空间位置受制于这种 “朦胧”，其他熟悉的物理特性也是如此，如能量、动量，以及量子世界独有的某些属性，如 “自旋”。
我们实际上并没有看到状态的叠加。每次我们看，或更多正确地“测量”，状态的叠加，它“坍缩”成一个单一的明确定义的状态。然而，在我们测量它之前，它同时处于多态。有人对这些说法持怀疑态度是有道理的。毕竟怎么可能相信不同于每个婴儿都知道的事实？然而，我们将用某些实验表明这正是发生的情况。
从地方性到非地方性
现代科学的核心是这样一种观念，即物体只直接受附近物体或力量的影响。为了确定一个现象为什么会发生在某个地方，必须检查那个地方附近“附近” 是指任何足够接近以影响对象的东西，用物理术语来说，即过去的任何事情物体的光锥。的所有现象和力量。这被称为“局部性”，即物理定律以局部方式起作用。其中量子力学比较显著的方面之一是定律预测某些以非本地方式工作的效应。
两个粒子可以这种方式连接或“纠缠”，对其中一个执行的操作可以立即产生影响。
在光年之外的另一个粒子上，这种“幽灵般的远距离动作”，使用爱因斯坦丰富多彩的表达，是量子力学令人震惊的发现之一。
从确定性定律到概率定律
测量时，状态叠加会崩溃到哪个特定状态？而在物理学的其他分支中，定律是确定性的统计力学是一个例外。，即每个实验都有一个独特的结果，量子力学定律表明我们只能知道结果的概率。再次，这似乎是可疑的。它受到当时主要研究人员的质疑。爱因斯坦本人对此持怀疑态度并创造了丰富多彩的表达方式，通过“上帝不会掷骰子”来表达这一点。然而，反复的实验证实，概率量子力学的本质不再是问题。
从确定到不确定
量子力学定律也告诉我们对可以确定的关于物理系统的知识量存在固有的局限性。这种限制的主要例子是著名的“海森堡（Heisenberg）不确定性原理”。
量子世界还有其他一些我们不会探索的重要特征。这些不同的特点都是推动量子计算的力量，而不是对这些功能如何影响量子计算的历史回顾。让我们看看计算机科学的几个领域，看看上述特征是如何影响这些领域的从发起量子计算的主要论文中看到的量子计算的历史观点，见附录A。。
量子世界对计算机科学的影响
结构叠加的概念用于将比特的概念推广到其量子模拟、量子比特。而位可以处于两种状态中的任何一种，叠加将允许一个量子比特同时处于两种状态。将许多量子比特放在一起构成量子寄存器。这种叠加是量子计算实力的基础。量子计算机不是一次处于一种状态，可以同时处于多个状态。
在概括了比特的概念之后，操纵比特的门的概念将扩展到量子设置。我们将拥有操纵的量子门、量子比特。量子门必须遵循量子操作的动态。特别是某些量子操作是可逆的，因此某些量子门必须是可逆的碰巧可逆计算早于量子计算有很长的历史。这段历史将在适当的时候进行考察。。
算法
量子算法领域以一种基本的方式使用叠加。人们使用了量子世界的某个方面将一台量子计算机同时置于多个状态。人们可能将其视为大规模并行性。这需要特别注意: 我们无法衡量当计算机处于这种叠加状态时的情况，因为测量它会使它崩溃一个位置。我们的算法首先从量子计算机开始于一个单个状态。然后，我们巧妙地将其置于许多状态的叠加中。从那里，我们以特定的方式操纵量子比特。最后，（一些）量子位被测量。测量会将量子比特坍塌到期待的比特，这将成为我们的输出。
纠缠也将在量子计算中发挥作用。因为量子比特可以纠缠，通过测量其中一些，其他的会自动达到期待的状态。
考虑在无序数组中搜索特定对象。经典算法检查数组中的第一个元素，然后检查第二个元素，以此类推。当找到对象或到达数组末尾时，算法停止。
因此，对于具有n个元素的数组，在最坏的情况下，算法可以查看数组的n个元素。
现在想象一台使用叠加的计算机。相比于一台机器查看这个或那个元素，让它同时查看所有元素。这将使得计算机有惊人的加速。事实证明，这样的量子计算机将能够对n元数组查询时，在n次查询找到对象。这是第一个量子算法，被称为“Grover算法”。
另一种展示量子强大和有用性的算法是进行数字因式分解的Shor算法。一个数字的因式分解的算法涉及查看该数字的许多可能的因素，直到一个真实的因子被发现。Shor算法使用叠加（以及一些数论）同时查看许多可能的因素。Shor算法部分基于早期的量子算法创建用于解决稍微做作的问题。虽然这些早期的算法（Deutch、DeutchJoza和Simon的周期性算法）解决了人工问题，我们将研究它们，以便可以学习量子软件的不同技术设计。
编程语言
如果算法在实际应用中有用，则它们最终必须发展成具体的软件。使这一步成为可能的桥梁是编程。量子计算也不例外。该领域的研究人员已经开始设计量子编程语言，以使下一代程序员可能控制量子硬件，并实施新的量子算法。
我们将简要介绍一下编程语言（第一次，我们的计算机编程知识出现在一本量子计算教科书中），从量子汇编器开始并进入高级量子编程，特别是量子函数编程。
理论计算机科学
理论计算机科学的目标是将工程师所做的工作形式化，更重要的是，将工程师不能做的事情正式化。这样的分析通过描述和分类计算的理论模型进行。量子力学的叠加有一种模糊的不确定性，感觉计算机科学家使用过（当然，非确定性纯属虚构概念和叠加是物理世界的既定事实）。不确定性叠加将崩溃到哪个状态与概率有关。我们被引导将图灵机的定义推广到量子图灵机的定义。有了明确的定义，我们将能够对所有这些不同的想法进行分类和关联。
我们不仅对量子图灵机能做什么感兴趣，对效率问题也很感兴趣。这给我们带来了量子复杂性理论。将给出量子复杂性类别的定义，并将与其他众所周知的复杂性类别有关。
密码学
不确定性和叠加将用于公钥分发的量子版本协议。测量扰乱量子态的事实用于检测是否存在窃听（测量）通信的窃听者渠道。这种检测在经典密码学中不容易实现。而经典的公钥分发协议依赖于这样一个事实，即某些逆函数在计算上难以计算，量子密钥分布协议基于这样一个事实，即某些量子物理定律是正确的。这种力量使量子密码学如此有趣和强大。还有一个公钥协议在基上使用纠缠方法。与密码学相关的是隐形传态。在瞬移中，系统传送的是一种状态，而不是消息。隐形传输协议使用纠缠可以在宇宙中分离粒子。
量子密码学最令人惊奇的部分是它不仅是一种理论好奇心。事实上，当前已经有实际商用的量子密码学。
信息论
没有提及信息，我们将无法讨论压缩、传输、存储等话题。信息论，现在是一个成熟的领域，由克劳德·香农（Claude Shannon） 在20世纪40年代发明，他还开发了一系列在计算机科学和工程中使用的技术和想法。因为这本书涉及量子计算，所以我们必须要问: 有没有令人满意的量子信息概念？ 通过量子比特流编码的信息内容是什么？ 事实证明，这样的概念是存在的。如同经典信息与秩序的度量（所谓的信号源的熵）有关，量子信息与量子熵的概念配对。我们将主要通过一些例子探索量子领域的秩序和信息如何不同于熟悉的概念，以及如何利用这些差异实现数据存储、传输和压缩方面的新成果。
硬件
没有量子计算机，量子计算就没有未来。我们要识别实施量子机器背后的挑战，特别是一种嵌入量子世界本质的东西: 退相干。我们还将描述期望的、有用的、必须展示的、量子机器的理想特征。我们将展示一些关于量子硬件的提案。这里的重点不是关于技术细节的（这是一本写给计算机科学家的书，而不是量子工程手册）。相反，我们的目标是传达这些提案的要点，以及目前评估的成功机会。
马少平2023年2月10日
