写在全书之前想说的话

本书的写作纯属偶然。我从2012年开始面对本科生开设量子计算的新生研讨课，旨在科普量子计算与量子信息的知识，传播、普及计算机科学发展的新领域、新知识和新思维。课程安排了4个系列的科普讲座：量子计算机杂谈、量子安全通信杂谈、量子可逆逻辑电路设计杂谈、量子容错计算杂谈。除了量子计算机杂谈的内容以外，其余三个杂谈的内容都包含在我们研究室2004年以来主要的学习和研究内容之中。

开设这门新生研讨课的初衷，一是给新生科普计算机科学技术发展的前沿，通过介绍量子、量子比特、量子信息、量子计算、量子通信、量子计算机的入门常识，以此打开学生们关注量子科技、量子计算机发展的新视野，点燃他们对量子科技的兴趣，并使他们具备阅读量子科技相关科普文献的基本能力；二是那个年头“计算思维”的热潮似乎正裹挟着整个计算机学界，我无法脱俗，我潜意识地期待在教学过程中实践培养“计算思维”的一种教学模式。就是想把量子计算的思维、方法和相关理论的基本内容通过课程告诉学生，期待影响他们今后在软件设计或算法构建中的思维。教学实践后我亲身体会或了解到，第一个想法基本可以实现，因为从课堂的研讨和课后的作业中可以感觉到大多数选课的新生通过短短的32个学时的学习和讨论，对量子计算与量子信息会萌发出兴趣，至少他们在课程学习结束后会比一般的学生更加关注量子信息科技的新进展，从他们口中说出的关于某些科普新闻报道的评论更加科学或靠谱、用词也更加准确了。但第二个目标是我的心太大了，原因当然在于我。我是半路出家做了一点量子信息和量子计算相关的基础研究，实践阅历不足，没有功底和能力将量子信息与量子计算理论背后的、计算机专业需要的思维和方法很好地凝练出来，然后通过课程朴素地告诉学生。但我又想，我虽然笨拙，却已通过授课将这粒有益的种子播在了一些学生的思维里，我期待着这粒种子会在今后某一恰当的时候突然发芽、开花、结出可口的果子。

课程开设之初，因为课程内容是基于“量子”讨论信息和计算的内容，不在我们的宏观现实和宏观思维之中，现实中除去专业从事相关领域研究的人，我们从小到大几乎都未接受过相关教育，哪怕是科普教育，因此当课程挂上选课网，选课的学生因为课程名中出现“量子”会感到或陌生或畏惧而拒绝，也有少数学生会因为或陌生或好奇，想了解、想学习。其实学生们和我一样，我是半路出家，我能够理解。因此我会在每一轮、每一次的讲稿和PPT中更新内容，将相关的最新的国内外各种新闻媒体的文字、图片和视频报道融入到授课中去，想与时俱进地主动讲好这4个讲座中的每一个故事。

在量子可逆逻辑电路设计杂谈的讲座中，想通过量子可逆逻辑电路设计中一个非常简单的、但学生们却从未见过的物理问题（已知逻辑函数的值求解逻辑电路），启发学生运用一些简单数学方法解决问题，让学生亲身感受到什么是现实问题、什么是数学模型，亲身触摸到“物理模型-数学模型-解决方案”间的关系，在学生的思维里种下这粒种子，并让学生们意识到数学的普适性意义。在教学中，通过课堂互动和学生研讨的环节，我发现大多数同学可以较快地掌握一些基本概念并能够大致理解问题（已知逻辑函数的值求解逻辑电路），了解把问题的物理模型抽象成逻辑门输入/输出数值间的数字问题，通过选择恰当的数学工具（真值表、矩阵与代数演算、置换等）讲解，再把数字问题转换成数学问题，然后建立问题求解的数学模型，再基于数学工具的运算规则加工数字，最终达成问题的解决方案，最后将解决方案的文字与计算公式转换成算法。一般的学生此时能够完成问题求解的代数计算，条件好的学生能够进一步给出采用基本方法的程序设计结果。对于条件更好的学生进一步推荐“解决方案-算法设计-程序实现”的实践环节，活用数据结构与程序设计中的技巧，真正体会科学计算程序设计的乐趣。因为有这样的教学活动体会，我确实曾经想过把相关内容以数学建模为主线归纳小结成讲义。

说到本书的写作纯属偶然，其实还受到一件事的触发。某一日同学聚会，有同学问我有没有适合数学建模程序竞赛题目的建议，此时我的头脑中真的突然闪现这个想法：量子可逆逻辑电路综合可以成为一个好的命题内容，还可以作为程序设计语言课程设计的选题之一。首先命题者如若善于表达，量子可逆逻辑电路综合的问题是易于表述且目标明确的，问题本身有助于数学建模与代数优化，程序实现时能够采用多种程序设计和数据结构的技巧达到提高自动生成逻辑电路的效率。再者就是3量子可逆逻辑电路有开放的标准数据，4量子可逆逻辑电路全体的综合依然是一个技术上的开放问题，因此无论是竞赛还是课程设计的结果都可以得到公平、公正和是否创新的评判。原本想写，有一些积累，遇上这一件事触发，于是就写出了这本书。

新兴学科量子信息论与量子计算理论的基础是量子力学原理，本书的撰写过程中涉及一些量子信息和量子计算的概念及其表达方法，又因我们的教育和研究背景是计算机科学与应用，加之编写的动因突发，且希望一气呵成，时间仓促、修养不足，因此本书难免有疏漏和不当之处，敬请读者批评指正。

回头看，成就本书的编撰，要感谢我的多位博士研究生:李志强、肖芳英、李文骞、王冬,以及万四爽、安博、杨忠明等硕士，感谢他（她）们早期的多年努力的结果，特别是李志强为本书编撰提供了大量翔实的材料，以及基于Hash函数的3量子全部40320个可逆逻辑电路的计算结果。同时感谢谈佳宁博士为全书提供规范的全部可逆逻辑电路图。

陈汉武2017年3月31日

量子可逆逻辑的研究源于可逆计算机的研究。20世纪中叶，人们发现集成电路芯片的能耗导致计算机系统发热，既限制了芯片集成度，又影响到计算机的运行速度。IBM的科学家R.Landaue指出，集成电路芯片的能耗主要源于芯片中门电路的信号演算不可逆操作。因此，降低芯片能耗、抑制发热的关键是将不可逆操作变为可逆操作。在信息领域，众所周知：经典计算机的本质是一个通用图灵机，是不可逆的，但所有不可逆通用图灵机都对应一个可逆图灵机，且两者的计算能力和计算效率完全相同，C.Bennett对此有严格证明。由于量子门与酉算子对应，量子逻辑门是可逆的，因此可以用可逆逻辑的设计方法综合量子逻辑电路。由于量子可逆逻辑门电路理论上不丢失信息，因此不存在热耗散，从而在理论上可以有效地解决集成芯片的能耗与发热的问题。C.Bennett证明：只要是可逆门构造的网络，能量零损耗是可能的。量子可逆逻辑综合技术已逐步广泛地应用于量子计算、低功耗CMOS电路、纳米技术、光计算、加密技术等一些科技领域，随着科学技术与电子工业工艺的进步，量子可逆逻辑的研究将会逐步进入更多学科的研究领域，将会变得越来越活跃、越来越重要。

随着量子可逆逻辑研究的深入，会涉及一些量子计算和量子信息处理的新思维和新方法，也会对计算机科学技术的发展起到促进的作用。量子逻辑门的代数抽象为可逆算子，最近30年来，研究者们提出了多种可逆量子门，除单个量子逻辑非门外，还有若干多量子可逆门，例如控制非门、Toffoli门、Fredkin门以及Peres门等。若干量子可逆门的级联与综合可构成基本量子电路，量子电路是构建量子设备与量子计算机的基本元素，因此研制性能优良的量子逻辑门、量子可逆逻辑电路既可解决芯片能耗导致发热的问题，又可提高芯片的集成度与运行速度。量子可逆逻辑电路的设计与综合的方法与规则也是构建未来低功耗电路科技的基础。不仅如此，研究量子可逆逻辑的综合理论、量子可逆逻辑电路的自动生成技术、量子可逆逻辑电路的错误检测与定位技术，也有助于基于量子计算问题解决方案的算法的量子线路描述与算法正确性验证的研究。虽然量子可逆逻辑综合的研究工作如此有意义，但作为大学本科生或研究生的科普读物，本书只是重点讲述一些基本内容，例如，如何根据给定的量子门完成可逆逻辑函数对应的可逆逻辑电路的代数计算，进一步，如何根据要求设计问题求解的算法，完成自动生成门阵列最短、量子代价最小的量子可逆电路的程序设计。

本书共六章内容：

第一章主要介绍量子信息与量子计算的基本知识，以为什么要研究量子可逆逻辑电路为引子，讲解量子可逆逻辑电路从设计问题的数学建模到算法设计的基本过程。

第二章介绍量子可逆逻辑电路设计中两个关键的代数定义以及可逆逻辑门的定义及其运算规则。

第三章介绍基于真值表数学建模的可逆逻辑电路综合方法，汉明距离求解方法和两个基于真值表的量子逻辑电路综合算法：二分法与图解法，以及案例的代数求解。

第四章介绍基于代数建模的可逆逻辑电路综合方法，以及一个完整可再实现的基于RM代数建模的量子可逆逻辑门电路综合算法与程序实现。

第五章介绍基于置换群建模的可逆逻辑电路综合方法，基于28个对换元素组成的3量子可逆逻辑电路的快速综合方法，以及一个完整可再实现的基于Hash表的量子逻辑电路综合算法与程序实现，同时给出3量子40320个使用NCT门的全部量子可逆逻辑门电路的代数计算结果。

第六章介绍4量子比特可逆逻辑电路综合方法，并给出一个完整可再实现的基于Hash表及其多种优化元素的4量子逻辑电路综合的算法与程序实现。最后给出我们的算法关于4量子置换（15，2，3，12，5，9，1，11，0，10，14，6，4，8，7，13）的计算结果：电路A是Maslov的结果，B是我们的计算结果，两个可逆逻辑电路完成相同的信号变换。

本书各章节的主要内容和案例均选自东南大学计算机学院量子计算与量子信息研究室研究生早期发表在《计算机学报》《软件学报》《计算机研究与发展》《电子学报》《通信学报》以及《东南大学学报》上的研究论文。特别是第四章的4.3节和第五章的5.3节，以及第六章相关部分的核心内容是取自于李志强博士的相关论文及其博士学位论文的有关章节，通过围绕主线编撰后完成。全书由陈汉武执笔撰写。由于撰写本书的目的在于对学生的新科学的教育启蒙和兴趣培养，期待通过一个现实的物理问题的数学建模演绎出不同的求解方法，通过不同的解决方案让学生了解数学作为工具在问题解决过程中的作用，同时理解问题解决方案中数学建模的意义和内涵，通过举一反三培养学生的计算思维与数学建模的意识和能力。期待更多愿意动手的学生通过学习和讨论，结合程序设计与数据结构的教学，能够完成相关算法的程序实现。

陈汉武2017年3月13日

第一章为什么要研究量子可逆逻辑电路？1

1.1集成电路产业大事记、摩尔定律与芯片集成度及其可预见的

发展极限1

1.2不可逆逻辑门、不可逆电路与计算机硬件的能耗与降温3

1.3理论上量子可逆门电路可以解决以上两个瓶颈问题4

1.4可逆逻辑门、可逆逻辑门集合的稠密子集5

1.5量子比特与张量乘积6

1.6量子态的叠加与并行计算11

1.7量子态叠加与量子态纠缠物理现象的代数表达式13

1.8量子可逆逻辑电路的基本概念、发展简史与问题解决的基本方法15

1.9物理模型，数学模型，学习的任务16

第二章量子可逆逻辑电路代数演算中的基本定义20

2.1可逆函数、可逆逻辑门与可逆逻辑门电路的基本定义20

2.2量子逻辑门及其演算21

第三章真值表方法24

3.1逻辑函数与真值表及其运算规则24

3.2用真值表求解可逆逻辑门电路的汉明距离方法28

3.3基于真值表的二分法可逆逻辑电路综合算法31

3.31相关概念与约定32

3.32以3量子为例解说二分电路综合算法33

3.33算法分析36

3.34优化36

3.35实验计算结果37

3.4基于真值表的图表示法可逆逻辑电路综合算法39

3.41相关概念与约定40

3.42算法描述43

3.43优化48

3.44实验计算结果和分析51

35基于真值表的图表示法可逆逻辑电路综合算法的4量子可逆

函数综合举例53

第四章代数方法59

4.1逻辑代数与逻辑电路59

4.2基于RM方法求解逻辑函数的可逆逻辑电路60

4.3用RM方法求解可逆逻辑门电路例题63

44一个基于RM方法的量子可逆逻辑电路综合的算法67

4.41三个基本定义69

4.42三个优化规则71

4.43基于RM的量子可逆逻辑门电路综合方法73

4.44基于RM的量子可逆逻辑电路综合的快速算法78

4.45算法结果与分析83

第五章置换群方法88

5.1用置换群建模的相关基础知识88

5.11映射函数f(x)的置换表示88

5.12置换里的映射和置换群上的乘积运算89

5.13置换中的换位运算与一个置换的换位表达91

5.23量子比特的换位元素组与量子可逆逻辑电路的综合方法93

53基于Hash表的量子逻辑电路综合算法98

5.31基本概念（Fredkin门和Peres门的定义）99

5.32基于最小完备Hash函数的量子可逆逻辑电路综合算法102

5.33基于位运算的Hash函数量子可逆逻辑电路综合算法112

5.34实验结果与分析119

第六章4量子可逆逻辑电路综合算法122

6.1基本概念123

6.2量子可逆逻辑电路综合的新算法132

6.21最小长度整体综合算法133

6.22量子电路序列生成算法135

6.3实验结果与分析137

附录A138

附录B模板及其模板优化技术147

附录CHash表的逻辑结构与物理构造155

综合练习156

量子可逆逻辑电路综合论文列表1598,