[套装书]算法设计编程实验（第2版）+人人可懂的量子计算（2册）

3.2　求解不定方程和同余的实验范例 82
3.2.1　计算最大公约数和不定方程 82
3.2.2　计算同余方程和同余方程组 89
3.2.3　计算多项式同余方程 99
3.3　特殊的同余式的实验范例 102
3.3.1　威尔逊定理和费马小定理 102
3.3.2　伪素数 105
3.3.3　欧拉定理 112
3.4　积性函数的实验范例 116
3.4.1　欧拉φ函数φ(n) 116
3.4.2　莫比乌斯函数μ(n) 121
3.4.3　完全数和梅森素数 124
3.5　高斯素数的实验范例 129
3.6　相关题库 135
第4章　组合分析的编程实验 152
4.1　生成排列的实验范例 152
4.1.1　按字典序思想生成下一个排列 152
4.1.2　按字典序思想生成所有排列 154
4.2　排列组合计数的实验范例 156
4.2.1　一般的排列组合计数公式 156
4.2.2　两种特殊的排列组合计数公式 167
4.2.3　多重集的排列数和组合数 174
4.3　鸽笼原理与容斥原理的实验范例 178
4.3.1　利用鸽笼原理求解存在性问题 178
4.3.2　容斥原理应用实验 180
4.3.3　Ramsey定理的应用 188
4.4　Pólya计数公式的实验范例 190
4.5　生成函数与递推关系的实验范例 201
4.5.1　幂级数型生成函数 201
4.5.2　指数型生成函数 204
4.5.3　递推关系 207
4.6　快速傅里叶变换的实验范例 211
4.7　相关题库 216
第5章　贪心法的编程实验 229
5.1　体验贪心法内涵的实验范例 229
5.1.1　贪心法的经典问题 229
5.1.2　体验贪心法内涵 236
5.2　利用数据有序化进行贪心选择的实验范例 241
5.3　在综合性的P类问题中使用贪心法的实验范例 249
5.4　相关题库 255
第6章　动态规划方法的编程实验 265
6.1　线性DP的实验范例 266
6.1.1　初步体验线性DP问题 266
6.1.2　子集和问题 270
6.1.3　最长公共子序列问题 271
6.1.4　最长递增子序列问题 273
6.2　0-1背包问题 280
6.2.1　基本的0-1背包问题 280
6.2.2　完全背包 281
6.2.3　多重背包 285
6.2.4　混合背包 287
6.2.5　二维背包 292
6.2.6　分组背包 294
6.2.7　有依赖的背包 298
6.3　树形DP的实验范例 300
6.4　状态压缩DP的实验范例 305
6.5　单调优化1D/1D DP的实验范例 309
6.5.1　经典模型1：利用决策代价函数w的单调性优化 310
6.5.2　经典模型2：利用决策区间下界的单调性优化 313
6.5.3　经典模型3：利用最优决策点的凸性优化 318
6.6　相关题库 322
第7章　高级数据结构的编程实验 353
7.1　后缀数组的实验范例 353
7.1.1　使用倍增算法计算名次数组和后缀数组 353
7.1.2　计算最长公共前缀 356
7.1.3　后缀数组的应用 357
7.2　线段树的实验范例 370
7.2.1　线段树的基本概念和基本操作 370
7.2.2　线段树单点更新的维护 372
7.2.3　线段树子区间更新的维护 375
7.3　处理特殊图的实验范例 387
7.3.1　计算欧拉图 387
7.3.2　计算哈密顿图 393
7.3.3　计算最大独立集 402
7.3.4　计算割点、桥和双连通分支 406
7.4　相关题库 414
第8章　计算几何的编程实验 433
8.1　点线面运算的实验范例 433
8.1.1　计算点积和叉积 433
8.1.2　计算线段交 440
8.1.3　利用欧拉公式计算多面体 449
8.2　利用扫描线算法计算矩形的并的面积的实验范例 453
8.2.1　沿垂直方向计算矩形的并面积 453
8.2.2　沿水平方向计算矩形的并面积 457
8.3　计算半平面交的实验范例 460
8.3.1　计算半平面交的联机算法 461
8.3.2　利用极角计算半平面交的算法 466
8.4　计算凸包和旋转卡壳的实验范例 474
8.4.1　计算凸包 474
8.4.2　旋转卡壳实验 479
8.5　相关题库 482



---------------------------人人可懂的量子计算---------------------------


译者序
前言
致谢
第1章　自旋 …… 1
1.1　量子钟 …… 7
1.2　同一方向的测量 …… 7
1.3　不同方向的测量 …… 8
1.4　测量 …… 10
1.5　随机性 …… 11
1.6　光子与偏振 …… 13
1.7　小结 …… 17
第2章　线性代数 …… 19
2.1　复数与实数 …… 20
2.2　向量 …… 21
2.3　向量的图解 …… 22
2.4　向量的长度 …… 23
2.5　标量乘法 …… 23
2.6　向量加法 …… 24
2.7　正交向量 …… 25
2.8　bra-ket内积 …… 26
2.9　bra-ket与长度 …… 27
2.10　bra-ket与正交 …… 28
2.11　标准正交基 …… 30
2.12　向量的基表示 …… 31
2.13　有序基 …… 34
2.14　向量的长度 …… 35
2.15　矩阵 …… 36
2.16　矩阵运算 …… 39
2.17　正交矩阵与酉矩阵 …… 41
2.18　线性代数工具箱 …… 42
第3章　自旋与量子比特 …… 44
3.1　概率 …… 44
3.2　量子自旋的数学表示 …… 45
3.3　等价状态 …… 49
3.4　自旋方向与基 …… 51
3.5　装置旋转60° …… 54
3.6　光子偏振的数学模型 …… 55
3.7　偏振方向与基 …… 56
3.8　偏振滤波实验 …… 57
3.9　量子比特 …… 59
3.10　Alice、Bob与Eve …… 61
3.11　概率偏振与相干性 …… 64
3.12　Alice、Bob、Eve和BB84协议 …… 65
第４章　纠缠 …… 69
4.1　非纠缠量子比特 …… 70
4.2　非纠缠量子比特的计算 …… 72
4.3　纠缠量子比特的计算 …… 74
4.4　超光速通信 …… 77
4.5　张量积的标准基 …… 79
4.6　如何制备纠缠的量子比特 …… 80
4.7　使用CNOT门制备纠缠的量子比特 …… 82
4.8　纠缠的量子钟 …… 84
第5章　贝尔不等式 …… 87
5.1　不同基下的纠缠量子比特 …… 89
5.2　爱因斯坦与定域实在性 …… 93
5.3　爱因斯坦和隐变量 …… 95
5.4　纠缠的经典解释 …… 95
5.5　贝尔不等式 …… 97
5.6　量子力学的解释 …… 98
5.7　经典的解释 …… 100
5.8　测量 …… 105
5.9　量子密钥分发的Ekert协议 …… 106
第6章　经典逻辑、门和电路 …… 109
6.1　逻辑 …… 110
6.2　布尔代数 …… 112
6.3　功能的完备性 …… 115
6.4　门 …… 119
6.5　电路 …… 121
6.6　与非门是一个通用门 …… 123
6.7　门与计算 …… 123
6.8　存储 …… 126
6.9　可逆计算 …… 127
6.10　台球计算 …… 135
第7章　量子门和电路 …… 141
7.1　量子比特 …… 142
7.2　受控非门 …… 143
7.3　量子门 …… 145
7.4　作用于一个量子比特的量子门 …… 146
7.5　是否存在通用量子门 …… 149
7.6　非克隆定理 …… 149
7.7　量子计算与经典计算 …… 153
7.8　贝尔电路 …… 153
7.9　超密编码 …… 156
7.10　量子隐形传态 …… 160
7.11　纠错 …… 165
第8章　量子算法 …… 173
8.1　P与NP …… 174
8.2　量子算法是否比经典算法快 …… 177
8.3　查询复杂性 …… 178
8.4　Deutsch算法 …… 178
8.5　Hadamard矩阵的Kronecker积 …… 184
8.6　Deutsch-Jozsa算法 …… 188
8.7　Simon算法 …… 194
8.8　复杂性类 …… 206
8.9　量子算法 …… 209
第9章　量子计算的作用 …… 212
9.1　Shor算法与密码分析 …… 213
9.2　Grover算法与数据检索 …… 218
9.3　化学与模拟 …… 224
9.4　硬件 …… 226
9.5　量子霸权与平行宇宙 …… 231
9.6　计算 …… 232

.　　对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
　　对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
　　本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
　　我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
　　本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http://www.hzbook.com）下载。
　　感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授，Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，German University of Technology in Oman的Rudolf Fleischer教授，North South University的Abul L. Haque教授和Shazzad Hosain教授，International Islamic University Malaysia的Normaziah Abdul Aziz教授，以及香港理工大学的曹建农教授，他们为本书英文版书稿的试用和改进提供了以英语为母语或官方语言的平台。感谢Georgia Institute of Technology的Jiaqi Chen同学审阅英文版书稿的部分章节。
　　感谢巴黎第十一大学博士生张一博同学、香港中文大学博士生王禹同学和复旦大学已故教授朱洪先生，他们对于第2版的编写提出了建设性的意见。
　　感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授，台湾“东华大学”彭胜龙教授，西北工业大学姜学峰教授和刘君瑞教授，宁夏理工学院副校长俞经善教授，中国矿业大学毕方明教授，以及中国矿业大学徐海学院刘昆教授等。
　　感谢指出书稿中错误的西安电子科技大学朱微、张恩溶和中国矿业大学徐海学院贺小梅等同学。
　　特别感谢和我一起创建ACM-ICPC亚洲训练联盟的国内同仁，他们不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。这些年，我们并肩作战，风雨同舟，如莎士比亚《亨利五世》的台词：“今日谁与我共同浴血，他就是我的兄弟！”
　　由于时间和水平所限，书中肯定夹杂了一些缺点和错误，表述不当和笔误也在所难免，热忱欢迎学术界同仁和读者赐正。如果你在阅读中发现了问题，请通过电子邮件告诉我们，以便我们在课程建设和中、英文版再版时改进。我们的联系方式如下：
　　通信地址：上海市邯郸路220号复旦大学计算机科学技术学院吴永辉（邮编：200433）
　　电子邮件：yhwu@fudan.edu.cn
　　吴永辉王建德
　　2019年10月30日于上海
　　注：本书试题的在线测试地址如下：
　　在线评测系统 简称 网址
　　北京大学在线评测系统 POJ http://poj.org/
　　浙江大学在线评测系统 ZOJ http://acm.zju.edu.cn/onlinejudge/
　　http://zoj.pintia.cn/home
　　UVA在线评测系统 UVA http://uva.onlinejudge.org/
　　http://livearchive.onlinejudge.org/
　　Ural在线评测系统 Ural http://acm.timus.ru/
　　HDOJ在线评测系统 HDOJ http://acm.hdu.edu.cn/
　　
　　
　　---------------------------人人可懂的量子计算---------------------------
　　
　　
　　本书的目的是介绍量子计算，使得任何一个熟悉高中数学知识和愿意投入一点时间的人都能理解。我们将会学习量子比特、量子纠缠、量子隐形传态和量子算法，以及其他量子相关的主题。我们的目标不是对这些概念给出一些不明确的想法，而是使它们清晰明了。
　　量子计算经常出现在新闻中：中国通过隐形传态将一个量子比特从地球传送到一颗卫星上；Shor算法使我们目前的加密方法面临风险；量子密钥分发将使加密再次变得安全；Grover算法将加速数据检索。但这一切究竟意味着什么？这一切是如何运作的？所有这些都将在本书中得到解释。
　　不使用数学能做到这一点吗？如果我们想真正了解发生了什么，那就需要使用数学。量子力学的基本思想往往与直觉相悖。试图用文字来描述这些是行不通的，因为我们在日常生活中对它们没有经验。更糟糕的是，文字描述常常给人留下这样的印象：我们貌似理解了一些东西，而实际上我们还没有理解。好消息是，我们并不需要引入太多的数学知识。作为一名数学家，我的职责是尽可能地简化数学（坚持绝对的本质）并给出基本的例子来说明它的用法与含义。也就是说，这本书可能包含你以前从未见过的数学概念，而且和所有的数学知识一样，新的概念一开始可能看起来很奇怪。重要的是不要忽略这些例子，而且要仔细阅读计算的每一步。
　　量子计算是量子物理与计算机科学的完美融合，将20世纪物理学中一些最令人惊叹的观点融入一种全新的计算思维方式中。量子计算的基本单位是量子比特。我们将看到什么是量子比特以及测量量子比特时会发生什么。一个经典比特要么是0，要么是1。如果是0，我们测量它，得到0；如果是1，我们测量它，得到1。在这两种情况下，比特都保持不变。量子比特的情况则完全不同。一个量子比特可能是无限多个状态中的某一个——0和1的叠加态，但是当我们测量它时，和经典情况一样，我们只得到两个值中的一个——0或1。测量会改变量子比特，一个简单的数学模型可以精确地描述这一切。
　　量子比特还可能纠缠。当我们对其中一个进行测量时，会影响另一个的状态。这是我们在日常生活中没有经历过的，但我们的数学模型完美地描述了这种现象。
　　这三个概念——叠加、测量和纠缠——是量子力学的核心。一旦我们理解了这些概念，就能知道如何在计算中使用它们。这正体现了人类的聪明才智。
　　数学家通常认为：证明是美丽的，而且经常包含意想不到的见解。对于我们将要讨论的许多主题，我有完全相同的看法。贝尔定理、量子隐形传态和超密编码，这些都是珍宝。纠错线路和Grover算法更是相当惊人的。
　　读完本书，你应该理解了量子计算的基本概念，并会看到一些巧妙而漂亮的结构。同时，你还将认识到量子计算和经典计算并不是两个截然不同的学科。量子计算是计算的一种更基本的形式——任何经典计算机可以计算的都可以在量子计算机上计算。计算的基本单位是量子比特，而不是比特。从本质上讲，计算就是量子计算。
　　最后应该强调的是，本书是关于量子计算理论的介绍。它是关于软件的，而不是硬件的。虽然我们在某些地方简要地提到了硬件，偶尔也会讨论如何在物理上纠缠量子比特，但这些只是题外话。这本书讲的不是如何构建量子计算机，而是如何使用量子计算机。
　　以下是对这本书内容的简要描述。
　　第1章。经典计算的基本单位是比特。比特可以表示为处于两种可能状态之一的任何东西，标准例子是一个可以打开或关闭的电子开关。量子计算的基本单位是量子比特。这可以用电子的自旋或光子的偏振来表示，但自旋和偏振的性质对我们来说并不像开关打开或关闭那样熟悉。
　　我们先来看看自旋的基本性质。从奥托·斯特恩（Otto Stern）和瓦尔特·格拉赫（Walther Gerlach）的经典实验开始，他们在实验中研究了银原子的磁性。我们可以看到在不同方向上测量自旋会发生什么。测量会影响量子比特的状态。我们还会解释与测量相关的随机性。
　　该章的结论是，类似于自旋的实验可以用偏振滤光片和自然光来完成。
　　第2章。量子计算基于线性代数。幸运的是，我们只需要一小部分概念。该章介绍我们需要的线性代数知识，并说明在后面的章节中如何使用这些知识。
　　我们将介绍向量、矩阵、如何计算向量的长度以及如何判断两个向量是否垂直。首先介绍向量的初等运算，然后介绍矩阵是如何同时进行这些运算的。
　　起初这些知识的作用并不明显，但确实有用。线性代数是量子计算的基础。由于本书其余部分使用了这里介绍的数学知识，因此需要仔细阅读。
　　第3章。该章介绍前两章是如何联系在一起的。线性代数给出了自旋或偏振的数学模型，这使我们能够定义量子比特，并准确地描述测量时会发生什么。
　　接下来书中举了几个在不同方向上测量量子比特的例子。最后介绍量子密码学，并描述BB84协议。
　　第4章。该章描述两个量子比特纠缠的含义。使用文字很难描述纠缠，与之相对，使用数学描述则很简单。张量积是一种新的数学思想，这是将单量子比特组合成多量子比特最简单的方法。
　　虽然纠缠的数学描述很直观，但我们在日常生活中并不会接触到。当测量一对纠缠量子比特中的某一个时，会影响另一个。阿尔伯特·爱因斯坦（Albert Einstenin）不喜欢这种现象，并称之为“幽灵般的超距作用”。我们会看几个例子。
　　该章最后指出，我们不能使用纠缠来实现超光速通信。
　　第5章。我们看看爱因斯坦对纠缠的担忧，以及隐变量理论能否保持定域实在性。我们研究贝尔不等式的数学原理——这是一个显著的结果，它提供了一种实验方法来确定爱因斯坦的论点是否正确。虽然贝尔当时认为爱因斯坦的观点可能会被证明是正确的，但是爱因斯坦的观点是错误的。
　　阿图尔·埃克特（Artur Ekert）意识到，测试贝尔不等式的装置还可以用于生成密码学中使用的安全密钥，并同时测试是否存在窃听者。在该章的最后，我们描述了这种加密协议。
　　第6章。该章从计算的标准主题开始：比特、门和逻辑。然后简要地介绍可逆计算和爱德华·弗雷德金（Edward Fredkin）的想法。我们证明了Fredkin门和Toffoli门都是通用的——你可以仅使用Fredkin门（或Toffoli门）来构建一台完整的计算机。最后介绍Fredkin的台球计算机。尽管这并不是书中余下内容真正需要的，但它十足的独创性值得介绍。
　　这台计算机是由相互碰撞的球和很多墙组成的。它使人联想起粒子之间的相互作用。这激发了理查德·费曼（Richard Feynman）对量子计算的兴趣，费曼写了该领域最早的一些论文。
　　第7章。该章开始学习使用量子电路进行量子计算，并定义了量子门。我们将看到量子门如何作用于量子比特，并意识到我们一直在使用这种思想。我们只需要改变观点：不再认为正交矩阵作用于测量装置，而是作用于量子比特。我们还证明了一些有关超密编码、量子隐形传态、克隆和纠错的惊人结果。
　　第8章。这可能是最具挑战性的一章。我们会看到一些量子算法，并看到它们与经典算法相比计算的速度有多快。为了讨论算法的速度，我们需要引入复杂性理论中的思想。我们定义了查询复杂性后，就开始学习三个量子算法，并证明它们的查询复杂性比经典算法的更低。
　　量子算法揭示了正在解决的问题的基本结构，它不仅仅是量子并行的思想——把输入放进所有可能状态的叠加中。该章介绍了最后一部分数学知识——矩阵的Kronecker积。实际上，这部分知识的困难源于我们正在以一种全新的方式进行计算，而我们并没有使用这些新思想来解决问题的经验。
　　第9章。最后一章着眼于量子计算将对生活带来的影响。我们首先简要描述两个重要的算法，一个是彼得·肖（Peter Shor）发明的，另一个是洛夫·格鲁弗（Lov Grover）发明的。
　　Shor算法提供了一种将大数分解为质因数的方法。这似乎并不重要，但我们的互联网安全依赖于分解质因数是个难以解决的问题。能够分解大质数的乘积威胁到我们当前计算机之间的安全交易。可能还要等一段时间，我们才能拥有足够强大的量子计算机来分解目前正在使用的这些大数，但这一威胁是真实存在的，而且它已经迫使我们思考如何重新设计计算机之间的安全对话方式。
　　Grover算法适用于特殊类型的数据检索。我们展示了它是如何在一个小样例中工作的，并说明了它是如何在一般情况下工作的。Grover算法和Shor算法都很重要，不仅因为它们可以解决问题，还因为它们引入了新思想。这些基本思想正在被纳入新一代算法中。
　　学习算法之后，我们转个话题，简要地看一下如何使用量子计算来模拟量子过程。究其本质，化学就是量子力学。经典计算化学的工作原理是利用量子力学方程，并用经典计算机进行模拟。这些模拟是近似的，忽略了细节。这种方法在很多情况下都很有效，但在某些情况下就行不通了。在这种情况下，你需要这些细节，而量子计算机应该能够提供。
　　该章还简要地介绍了实际机器的构建。这是一个快速发展的领域，第一批机器正在出售，“云”上甚至有一台人人都可以免费使用的机器。看来我们很快就会进入量子霸权时代。（我们会解释这意味着什么。）
　　本书的结论是，量子计算不是一种新型的计算，而是对计算本质的发现。
　　

.　　这本关于量子计算和量子信息的书既简洁又严谨，手把手地帮助初学者掌握量子隐形传态、贝尔不等式、Simon算法等知识。如果再有朋友向我请教，我一定要向他们推荐此书！
　　——Scott Aaronson，得克萨斯大学教授，量子信息中心主任，著有Quantum Computing Since Democritus
　　“比特会被量子比特所取代吗?”在技术的地平线上，量子计算机的身影若隐若现。这本书为我们打开了一扇门，漫步于量子效应的长廊，近距离领略量子计算的锋芒。
　　——Alexander Keewatin Dewdney，西安大略大学计算机科学系教授