改进TR门级联的量子比较器设计

2021-10-14周林，郭兵

计算机工程与应用 2021年19期

周林，郭兵

四川大学计算机科学与技术，成都 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门的共轭转置。它们的酉矩阵可以表示为：

CNOT门是两量子比特门，由一个控制比特和一个目标比特组成，作用是根据控制比特的值选择翻转目标比特。当控制比特为|1>时，CNOT门将会对目标比特施行NOT变换，对于输入A、B实现A、A⊕B输出，量子代价为1。由单比特门和双比特门可以构造N比特门。TR门和Peres门都是三量子比特门，它们都可由两个V门、一个V†门和一个CNOT 门构造，量子代价均为4。TR门对于输入A、B、C分别实现A、A⊕B、ABˉ⊕C的输出。Peres 门对于输入A、B、C分别实现A、A⊕B、AB⊕C的输出。Toffoli 门也是一个三输出可逆门，量子代价为5。不同的可逆门有不同的代价，图1 展示了常用可逆门的构造方法及其量子代价[11]。

图1 可逆门及其代价Fig.1 Reversible gate and quantum cost

1.2 其他比较器设计

文献[12]提出了基于多目标扩展通用Toffoli门的设计，该方法从最高位向最低位进行比较，直接得到比较结果。其只需要2n-2 个辅助比特，优点在于简单直观，同时节约了量子比特。其中n位通用Toffoli门的构造量子代价比较高昂，学者Maslov[13]指出n+1 比特通用Toffoli门需要32n-120的量子代价以及一个垃圾比特。

文献[14]提出了基于流水线的设计，其包含了一系列的比较单元（cell），每个cell 比较两个比特之间的大小。单位cell 使用了Toffoli 门、CNOT 门和NOT 门生成，cell的量子代价为39且输出了8个垃圾比特。

文献[15]提出了基于树结构的设计，将需要比较的比特分别置于叶节点，比较结果从叶节点传递向根节点，最终由根节点汇总结果。该方案叶节点使用TR 门设计，对于n位通用比较器，该设计需要18n-9 的量子代价，同时生成6n-6 垃圾比特。

2 量子比较器设计

2.1 基本思想

假设需要比较的两个数为A与B，都由n+1 个比特表示。Ai表示A的从低位到高位的第i个比特，Bi同理，则使用gi表示Ai>Bi的真值，同理li表示Ai

其中，·表示交运算，⊕表示异或运算，利用真值表很容易验证上式的正确性，接下来考虑组合多个比特的情况。使用Gi表示从低位到高位截取第0 到第i个比特的A与B的大小比较，即当Gi=1 时，A0～i>B0～i，故若Gn=1 意味着A>B。同理定义Li与Ei，便将比较大小的问题转化为了求解Gn、Ln与En的问题。写出迭代式：

其中，+表示或运算。分析上式（4），当gi为1 时，意味着Ai>Bi，按照高位比较原则，Gi为1；当gi的值为0，说明Ai≤Bi，若关系为小于，则Gi为0，若关系为等于，则需要比较Gi-1的值，若Gi-1为1，则Gi为1。式（5）分析同理，对于式（6）则显然当A与B的所有位都相等时，两个数相等。

根据式（1）～（6），便得到了整个迭代关系。由于量子电路中实现或运算代价较高，因此可以考虑将或运算化简为异或运算。有结论[16]：

这很容易证明。由于gi·ei=0，因此式（4）、（5）在i>0时可写作：

一般的不需要将三个值全部求出来，根据式（10）可以很容易从任意两个值得到第三个值。

根据式（7），由于L·G=0，因此上式可以很容易推导出来。

2.2 线路实现

利用TR 门构造单比特比较器，根据式（1）和（2）将TR门的输出后面添加一个CNOT门进行组合，便可得到单比特比较器，将其封装，记为TR1门如图2所示。TR1门同时实现了li、gi，且构造该门使用了5个量子比特。

图2 TR1门实现Fig.2 TR1 gate implementation

同理利用三个CNOT 门与TR 门可以构造需要的门，记为TR2 门，得到一个三输出电路。每个输出分别代表着ei、li与gi如图3所示。这样使用7个量子比特构造了一个完整的单比特比较三输出电路。

图3 TR2门实现Fig.3 TR2 gate implementation

2.3 代价分析

首先考虑2 bit 的情况。文献[12]基于多目标的扩展通用Toffoli 门的设计，2 bit 比较器使用了4 个扩展Toffoli门，量子代价为70，垃圾输出为4；对于文献[14]流水线设计，2 bit比较器量子代价为39，垃圾输出为8；对于文献[15]基于树的设计，量子代价为27，垃圾输出为6；对比本文使用的方法如图2 所示，量子代价为20，垃圾输出为1。2 bit比较如表1所示。

表1 2 bit比较器Table1 2 bit comparator

关系式（8）（9）可以使用Toffoli 门实现，然而由于Toffoli 门需要5 量子代价，故选择Peres 门实现，量子代价只需要4。根据式（8）（9），如此便可以构造迭代关系如图4所示。

图4 迭代式实现Fig.4 Iterative implementation

对于任意比特比较器来说，整个电路可以通过迭代式构造。由于当i=0 时G0=g0,L0=l0，为了节约量子代价，因此，在比较第一个量子比特时使用TR1 代替TR2，此后根据式（8）（9）迭代式构造电路，最终通过式

（10）得到所有比较关系。完整电路实现如图5所示。

图5 比较器电路图Fig.5 Circuit diagram of comparator

考虑nbit的情况。对于文献[12]，量子代价主要来自于扩展多目标Toffoli 门的设计。由于原文没有给出该门的电路图，无法准确计算量子代价。因此，本文根据文献[13]的对于扩展多目标Toffoli门的实现，估计该方法所需的量子代价。可知没有垃圾比特的扩展多目标Toffoli 需要的量子代价是指数级别的。根据图5 可得，本文方法总量子代价=(TR1+(n-1)×TR2+2n×4)=15n-2，总垃圾输出=3n-2。因此得到如表2 所示结果。