量子可逆电路的研究现状

张黎明 郭玲

摘要： 随着量子技术的发展，量子可逆电路构造方法的应用越来越多。本文通过描述对其发展做了概括说明，并提出了现状研究的不足之处，以及未来研究的方向，为量子技术的发展提供了平台。

关键词： 量子门量子可逆电路量子多值逻辑通用门库

近30年来，人们已提出了多种量子门，如Toffoli门［１］，Fredkin门，Peres门等，并给出了量子门的代数特征。如何使用指定量子门库中的量子门自动生成量子代价较小的量子可逆逻辑电路，其本质就是量子可逆逻辑电路综合技巧问题。Shende将可逆电路综合转化为置换问题，并提出三量子可逆逻辑电路综合最优算法；Yang在此基础上利用GAP软件实现了三量子最小长度和最小代价可逆逻辑电路综合算法。然而目前大多数算法只是在综合三量子电路时效果很好，随着综合量子比特数的增加，综合量子可逆逻辑电路的时空复杂度将进一步增加。在综合四量子电路时，Yang等人利用广度优先搜索和双向综合技术，使用CNP量子门库可综合最长为12的四量子偶置换最优电路，这已是较好结果；李等人使用CNP量子门库，在广度优先搜索的基础上，巧妙构造哈希函数并利用线置换和向变换进行无损压缩可快速生成最大长度为16的最优四量子偶置换电路，这是目前已知的最好结果。目前人们还未设计出通用高效的多量子电路综合算法，这是量子电路设计中急需解决的重要问题之一，因为它的设计实现不仅可以降低制造量子电路的成本，而且能提高多量子可逆电路设计的效率。

目前比较有代表性的量子可逆电路构造方法有以下几种［２］。

穷举法、RM方法、群论分解方法、探索法，通过比较知穷举法综合结果好，能达到最优，但时间空间开销大；真值表和RM方法构造巧妙，综合速度快，但结果不尽理想，需要辅以优化；群论方法新颖高效，算法收敛迅速（有限步结束），但构造复杂，较为繁琐，需要的门库规模大；其他方法也均是在综合的效果和效率之间寻求一个平衡点，这个平衡点如何选取，则应该以实践中的具体需求情况为依据。

构建量子可逆逻辑电路主要有构造与优化两个过程，有些算法是先构造再优化，还有一些算法则是构造与优化同时进行。通常所得到的量子电路并不是最优电路，如何有效地优化电路，成为量子电路领域的另一个研究重点。Iwama、Maslov、Maslov等都对电路优化程度作出了杰出贡献。

目前对量子二值逻辑可逆电路综合算法的研究较多，但对于多值逻辑量子电路综合技术的研究较少［３］。其中的原因主要有：第一，人们已习惯于经典计算中的二值逻辑，利用多值逻辑进行计算不符合人们常规的思维和计算方式；第二，对于多值逻辑的理解与应用本身就是困难的，涉及多值逻辑理论及群、环、域等代数理论，量子可逆电路的设计又具有相当难度，规模较大，复杂性较高，其中又要解决量子的自然属性（如消相干现象等）对计算的负面影响。所以将多值逻辑应用于量子电路，设计具有相当复杂性的多值逻辑量子电路也是困难的。然而，量子具有多种可观测的属性，例如光子的偏振方向，电子的自旋方向，电子所处于的能级等，因而具有多个复杂的自由度，利用多能级描述量子位也更自然。由于量子实验物理的发展进步及测量技术的不断完善，对于量子在各个属性上的测量的精准度大大提高，使得量子高维基态（即多值逻辑量子态）的应用成为可能。另一方面，量子多值逻辑的应用能够极大提高量子并行计算的能力（理论上比二值逻辑更强大），并可在存储和处理量子信息时提供更大的灵活性，又可以无辅助位的方式用两位量子门和一位量子门建立多量子电路，使得多量子电路的物理实现成为可能。对多值量子可逆逻辑电路综合的研究正在兴起。

量子可逆电路本质上是置换电路［４］，在此基础上可根据一些特定功能构造量子专用电路，专用电路的设计实现及应用可加速运行算法，并对量子寄存器或量子芯片等的设计作出一些贡献。目前已设计出量子全加器、量子全减器及受控集成量子加减电路，它们是构建量子计算机的基本单元。在量子纠错编码和容错计算中可根据纠错码的生成矩阵和校验矩阵，分别生成编码电路和解码电路。2005年何等人通过分解蝴蝶矩阵和转置矩阵独立实现了基于Haar小波多尺度分析的完整量子电路。2006年Cheng等人用Bitonic方法快速构造大规模的量子排序电路，给出的线路模型清晰地反映出算法消耗资源的情况。2007年Khan等人给出了利用三值逻辑Feynman和Toffoli门实现的三值逻辑全加器，基于此又实现了带有部分前瞻的三值逻辑并行加法器，并展示了将此电路用作并行减法器的方法。2008年Khan提出综合量子四值逻辑加法/减法器的递归电路。之后Khan又提出量子四值逻辑比较器，比较器是著名的Grover量子搜索算法的关键功能模块—Oracle的组成部分，也是基于比较的各种算法及控制器的基本模块。当然，由于量子电路设计的复杂性，目前综合出的专用电路还不多，并且给出的大多数的电路并非最简形式。

尽管对于量子可逆电路的研究已取得了一些成果，但目前对于构建量子可逆电路的量子门及通用门库的研究还不深入，对于量子可逆电路的生成方法和优化方法的研究还处于起步阶段。对其中的一些问题，如多值逻辑的嵌入与应用，电路优化策略，综合算法复杂性的深入分析与证明等，只是进行了初步的探索。虽出现了一些解决方案，但并不十分成熟，还有一些领域未曾涉及，所以需要进一步深入研究。

参考文献：

［1］李志强，陈汉武，徐宝文等.基于Hash表的量子可逆逻辑电路综合的快速算法［J］.计算机研究与发展，2008，vol.45-2：2162-2171.

［2］何雨果，孙吉贵.基于Haar小波的多尺度分析量子电路［J］.科学通报，2005，vol.50-20：2314-2316.

［3］苏汝铿.量子力学［M］.北京：高等教育出版社，2002.

［4］吴楠，宋方敏.量子计算与量子计算机［J］.计算机科学与探索，2007，vol.1-1：1-16.