周 林，郭 兵

四川大学 计算机科学与技术，成都 610065

在20 世纪60 年代，学者们发现在逻辑电路中丢失的信息是导致计算机发热的原因之一[1]。为了解决计算复杂度与能量消耗的问题，自费曼提出量子计算的概念以来，其发展得到了国内外学者的重视。量子计算提供了解决NP 问题的思路，比如实现质因数分解的shor 算法[2]，对现代密码学体系造成了冲击。

量子比较器是量子算法实现的重要组成部分。在量子同态加密算法[3]、量子最大值算法[4]、量子排序算法[5]，量子字符串搜索算法[6]等常用算法中，都使用了量子比较器进行比较操作。量子比较器使用广泛，一个性质良好的比较器会为量子算法的物理实现提供基础性的帮助。

量子代价（quantum cost）是一个量子电路需要的单比特门与双比特门的数量，通常用来度量构造一个量子电路的代价[7]；垃圾输出（garbage output）是量子计算机输出的无用的比特。由于目前量子电路的物理实现困难，退相干时间短，因此量子代价与垃圾输出是衡量一个量子电路好坏的重要指标。本文通过对量子可逆门和基础布尔代数的研究，提出一种基于改进TR 门级联的量子比较器构造方法，该方法对量子代价与垃圾输出都有明显的优化。

1 相关工作

1.1 可逆门

量子计算机是由包含导线和基本量子门构成的，可以携带和操纵量子信息的电路[8]。量子门是可逆的，满足酉性变换性质。常用的可逆门有V 门、NOT 门、CNOT门、TR门[9]、Peres门[10]、Toffoli门等。

V门、V†门和NOT门都是单量子比特门，量子代价（quantum cost）为1，其中V†指V门的共轭转置。……