基于预评价的量子电路线性最近邻综合算法

王艺臻, 管致锦,2*, 管海宇

(1 南通大学信息科学技术学院, 江苏 南通 226019;2 江苏省专用集成电路重点实验室, 江苏 南通 226019)

0 引 言

量子电路综合源于对量子计算机的研究。随着量子信息技术的发展,量子逻辑综合的问题得到越来越多的关注。在量子电路逻辑综合问题的研究中,不只是为了找到量子电路有效的级联方法,同时还要求综合结果中尽可能找到实现量子电路具有的最低量子代价和最少量子门数。

在量子计算技术实现过程中,受到诸多实际限制。流行的一些量子技术要求只有相邻的量子位才能产生相互影响[1],量子位被约束到沿着某一阵列,并且仅在相邻位置之间的量子位彼此交互,这种结构称为线性最近邻(Liner nearest neighbor,LNN)[2]结构。

为了满足量子技术的LNN 约束,构建LNN 架构的量子电路。迄今为止,已有几种将非LNN 架构量子电路转化为LNN 架构量子电路的方法[2-5]。在非LNN 架构的量子电路中可以通过添加交换门以达到目标位和控制位相近邻的目的,或使用换线操作来构造线性最近邻结构的量子电路,Chakrabarti 等[3]运用寻求最短路径的方法对量子电路线顺序的重排序来求解LNN 架构的量子电路。为了降低由于线性最近邻增加的量子代价,Saeedi 等[4]提出了一种模板匹配的思路以消除量子电路中的冗余交换门,达到减少量子电路的量子代价的目的;对于在非LNN 架构的量子电路中,通过添加大量的交换门使其转换为线性最近邻架构的量子电路中,在此过程中优化交换门的数量也是降低量子代价的方法之一。如何在实现LNN 结构的量子电路中添加交换门的数量最少、量子电路的量子代价最小,是相关研究最关注的问题。

为了构造LNN 架构下的最优量子电路,本文完成的工作主要包括:(1)为了降低电路的最近邻代价(Nearest neighbor cost,NNC),使用量子电路最优评估算法对整个电路线的顺序进行全排列,找出最近邻代价最小的量子电路;(2)为了使原始的量子电路达到线性最近邻结构,需要在(1)的基础上完成效果最佳的添加交换门方法,实现对量子电路线性最近邻结构的转换,方便电路的物理实现;(3)为了降低量子电路的量子代价,使添加的交换门数量尽可能少,提出了解决量子电路优化问题的相关算法。

1 基本概念与相关理论

1.1 量子逻辑综合

量子逻辑综合[4],就是用给定的量子逻辑门,按照量子电路无扇出、无反馈、满足量子电路实现技术要求等约束条件和限制,实现相应的量子电路,并使得在某种统一代价模型条件下优化量子电路,使其量子代价尽可能小。

1.2 量子逻辑门

组成量子电路的基本元素是量子逻辑门。在量子电路的计算模型中,一个量子门(或称量子逻辑门)是一个基本的操作,基本的量子门来自相应的量子门库。此处采用的量子门库为NCV 门库[5]。由文献[6]可知,由NOT 门、CNOT 门、controlled-V 门、controlled-V+门构成的NCV 门库对一般量子电路是完备的,即可以使用NCV 门库构造任意量子电路。

NCV 门库包含一个单量子通用逻辑门(NOT 门)、一个双量子通用逻辑门(CNOT 门)、两个双量子通用量子门(controlled-V 门,controlled-V+门),如Fig.1 所示。

1.3 量子代价

量子计算的时间取决于量子电路中门的数量以及实现每个门所需物理操作的数量,将其称为量子代价[6]。外部环境的干扰会导致量子系统的退相干,所以量子计算必须在有限的相干时间内完成。这就要求量子电路的量子代价最小化,实现某一特定功能的量子代价最小的电路称为最优电路[7]。

此处采用NCV-111 量子代价标准[8],即认为NCV 门库中每个门的量子代价都为1,由NCV 门库构造的电路的量子代价是电路中门的数量,也就是电路的深度。

图1 NCV 门库Fig.1 NCV gate library

1.4 量子电路

量子电路由量子门和其相应的信息通路构造而成。n量子比特电路可以表示成n条水平线的形式,从上往下依次记为l1,l2,··· ,ln;量子门按照从左到右在电路中的位置(可用从左到右的垂线表示)依次执行,该位置分别记为h1,h2,··· ,hm。

用Un(c,t,k)表示n水平线的电路(n输入/输出电路)中的一个量子门,其中U表示门的类别,n表示n水平线的量子电路,c表示其控制位所在的水平线,t表示其目标位所在的水平线,k表示门所在电路从左到右的位置(即垂线)。Fig.2 为一个含有m个量子门的n量子比特电路图,其中虚线框中的门可表示为Un(j,i,k)。不带有任何量子门的电路称为恒等电路。

图2 电路中量子门的位置表示Fig.2 Representation of location of gate in circuits

1.5 交换门

交换门即SWAP 门,是一个有两目标位、没有控制位的量子门,记为交换门的作用是交换量子电路中平行线的位置,即在量子电路中经过SWAP 门作用后的两目标位的量子比特状态发生了交换。添加交换门可以使量子电路中某些非近邻量子门转化为近邻量子门,但同时也会使原来的电路平行线顺序被打乱,也可能会增加电路的量子代价。

一个交换门可以通过三个二量子位的最近邻量子门实现,如Fig.3 所示。由此可知,一个交换门的量子代价相当于三个二量子位的量子门的量子代价,即量子代价为3。因此,一般量子电路通过添加交换门转换为线性最近邻电路时,为了降低电路的量子代价,需要尽可能减少交换门使用的数量[9,10],或者通过相关规则[11]消除冗余的交换门。

在n条量子比特量子电路中,如果存在交换门S(li,lj,k)和S(li,lj,k+1),称这两个交换门为冗余交换门对。如果两个交换门为冗余交换门对,则该冗余交换门对可以从该量子电路中移除,如Fig.4 所示。

图3 SWAP 门的最近邻实现Fig.3 The nearest neighbor implementation of SWAP gate

1.6 全局换线

由NCV 门库构成的量子电路中,在对量子电路的输入/输出值没有影响的前提条件下,把对于量子电路水平线之间的顺序交换的一组操作称为全局换线。全局换线操作可以对量子电路中的所有量子门产生影响,或拉近量子门目标位与控制位的距离,或拉远量子门目标位与控制位距离,即缩小或增大量子门的NNC 代价值。

定理1 在由NCV 门库构成的量子电路中,单个非近邻量子门转换为近邻量子门时所添加交换门的最少数量等于该非近邻量子门的NNC 代价值。Fig.5 是一个非近邻量子门添加最小数量的交换门转换为近邻量子门的示例。

添加交换门的最小数量与非近邻量子门NNC 代价值之间的关系为

式中Sc为添加交换门的最小数量,Gnnc为单个量子门的NNC 代价。

证明:

在由NCV 门库构成的量子电路中,若存在一个非近邻量子门Un(li,lj,k),则|i-j| ＞1。由交换门的定义可知,需要至少添加|i-j|-1 个交换门,使得该非近邻量子门转换为近邻量子门,即所添加交换门的最小数量为|i-j|-1,根据非近邻量子门的NNC 代价的定义,该非近邻量子门的NNC 代价值为|i-j|-1。

由上述分析可知,NCV 门库构成的量子电路中,单个非近邻量子门转换为近邻量子门时所添加的交换门最少数量等于该非近邻量子门的NNC 代价值。

定义1在由NCV 门库构成的量子电路中,若存在某一量子门可以通过比较i和j的数值大小关系,来确定该量子门的高/低量子位。如果i＜j,那么li表示低量子位,lj表示高量子位;如果i＞j,那么lj表示低量子位,li表示高量子位;如果i=j,那么该量子门为NOT 门,NOT 门不存在高/低量子位。

图4 SWAP 门的化简Fig.4 Simplification of SWAP gate

图5 最小的SWAP 门添加数量Fig.5 The minimal number of additive swap gates

定义2阶梯结构,在量子电路中若存在x个交换门满足jx=i(x+1)关系,把交换门构成的这种结构称为阶梯结构,如Fig.6 所示。

图6 SWAP 门构成的阶梯结构Fig.6 Ladder structure of SWAP gate

在由NCV 门库构成的量子电路中,单个非近邻量子门在转换成近邻量子门时,该量子门的某一量子位在添加交换门时,将非近邻量子门转换成近邻量子门时所添加的最少交换门个数称为阶梯层数。在由NCV 门库构成的量子电路中,单个非近邻量子门在转换成近邻量子门时只允许在高/低量子位的一侧添加交换门的操作称为阶梯型添加交换门,阶梯型添加交换门的数量取决于阶梯层数。阶梯型添加交换门方法又可以分为上阶梯添加交换门方法和下阶梯添加交换门方法,如Fig.7 所示。

规则由NCV 门库构成的量子电路中,对单个非近邻量子门的某一量子位添加交换门构成阶梯结构时,如果可以与量子电路中已存在的交换门构成冗余交换门对,那么可以将冗余交换门对从量子电路中移除,且此时该量子位处于量子位相消状态;如果不能与量子电路中已存在的交换门构成冗余交换门对,则该量子位处于量子位关闭状态。

图7 添加SWAP 门到上阶梯结构(a)和下阶梯结构(b)的方法Fig.7 Methods of adding SWAP gate to upper ladder structure(a)and lower ladder structure(b)

2 基于预评价的线性最近邻量子逻辑综合算法

2.1 综合算法

所提出综合算法从两个方面优化最近邻量子电路。一方面,在换线过程中使量子电路的量子门尽量保持近邻结构,综合评估量子电路的线性最近邻代价值和混乱值最优结果,从而使添加的交换门尽可能少。提出了一种启发式算法来评估量子电路NNC 代价值与混乱值和的最小结果集合,在这个结果集中的量子电路,本身就具有线性最近邻代价小、混乱值小的特点。由定理1 知,对结果集中的量子电路添加交换门时交换门的个数必然也会小。另一方面,对非近邻量子门添加交换门操作时,考虑该量子门在当前量子电路中所处的环境,使新添加的交换门尽可能多地与量子电路中已存在的交换门产生冗余交换门对,然后再消除该冗余交换门对,以达到减少量子电路中交换门的目的。

图8 电路划分示意图Fig.8 Schematic diagram of circuit division

对于一个已知的非近邻量子电路,以电路中从左到右第一个非近邻量子门为中轴,该非近邻量子门左侧的量子电路级联网络为Nl(不包括该非近邻量子门);该非近邻量子门右侧的量子电路部分为Nr(包括该非近邻量子门);Nm是为了使Nl与Nr两个局部量子电路级联起来所需要的一组只含交换门的量子电路。Fig.8 是按照这种依据划分量子电路结构的一个局部实例。混乱值是指Nl与Nr两部分量子电路级联所需要的一组只含交换门量子电路Nm的交换门个数,最小混乱值是指Nm结构中交换门个数的最小数值。

具体算法描述如下:

第一步:初始化Nl为空、Nm为空、Nr=N。

第二步:扫描,由量子电路Nr的输入端开始,寻找量子电路的第一个非近邻量子门(即量子电路中第一个近邻代价不为0 的量子门),若存在则设为gl,执行第三步,否则执行第七步。

第三步:以该量子门gl为界,gl左侧的量子电路为Nl(不包括gl),gl与其右侧的量子电路部分为Nr。

第四步:换线,对量子电路Nr进行非重复全局换线操作,产生量子电路集合Nr(i)和交换门组集合Nm(i),i表示集合中的第几个元素,下同。

第五步:近邻化,把量子电路集合Nr(i)中的第一个非近邻门gl(i)转化为近邻门,采用添加交换门算法处理,算法处理完成后将i值相同的Nm(i) 与Nr(i)量子电路级联。

第六步:计算并选择qc值,每次近邻化操作,计算Nr(i)量子代价qc(i) 的值;最终选择使得相应qc(i)值最小的Nr(i)作为Nr(如果是多个量子代价最小值,选择其中一个),然后转至第二步。

第七步:整理,对已经构造好的线性最近邻量子电路进行最终的冗余交换门排查检测,消除量子电路中一些冗余的交换门。

第八步:算法结束。

2.2 量子电路最优评估算法

由NCV 门库构成的量子电路中,在量子电路输入/输出真值保持不变的前提条件下,通过启发式算法(多次利用全局换线操作)对量子电路NNC 代价值与混乱值的和进行评估,求出最小结果集。

具体算法描述如下:

第一步:初始化,计算量子电路Nr的NNC 代价值,运用最小混乱值算法求出Nm结构的最小混乱值;将上述两个值求和记为SUM,SUM 为最小值标记变量。

第二步:换线,对量子电路Nr进行一次全局换线操作。

第三步:计算,计算量子电路Nr的NNC 代价值,运用最小混乱值算法求出Nm结构的最小混乱值;将上述两个值求和记为SUM(i),i代表量子电路Nr进行的第i次非重复的换线操作。

第四步:比较,将每次计算出的SUM(i)值与最小值SUM 标记变量进行比较,如果SUM(i)的值小于或者等于该标记变量,那么将SUM(i)值相对应的Nl(i)、Nm(i)、Nr(i)局部量子电路一同暂时存入最优结果集栈中,并且将SUM(i)的值赋值给最小值SUM 标记变量,然后执行第五步;如果SUM(i)的值大于该标记变量,直接执行第五步。

第五步:判断循环是否结束,判断量子电路Nr是否完成了全部的换线操作,如果换线操作全部完成则循环结束执行第六步,否则执行第四步。

第六步:将最优结果集栈中的Nl、Nm、Nr局部量子电路从栈中取出并级联起来记为L(i)。

第七步:算法结束。

2.3 求最小混乱值算法

为了找到一种合适的Nm结构去级联Nl与Nr,以解决量子电路线序的重新排布问题并计算出Nm的混乱值,此处给出一种求最小混乱值算法。最小混乱值算法基于“逆序数”的思想,已知两种线数相同的任意线序集origin、target,在这两个线序集中,线序重新排布能且仅能通过添加SWAP 门完成,当origin线序重新排布为target 线序时至少需要添加t个门,t即最终结果,即为最小混乱值。算法的主要思想即t值的计算,设理想的电路线顺序用数组target[n]表示,当前的电路线顺序用数组origin[n]表示,计算所得线序中单个元素的逆序数用数组t[n]表示,逆序数结果之和记为t,即为最小混乱值。

具体算法描述如下:

第一步:从n=0 开始,读取origin[n]的元素。

第二步:判断读取的元素是否为origin[n]的最后一个元素,如果不是最后一个元素,执行第三步;否则执行第五步。

第三步:将origin[n]在target[n]数组中的位置信息存储在t[n]中。

第四步:删除target[n]数组中该位置上的元素(后续位置元素前移);执行第二步。

第五步:删除target[n]中全部元素;计算t[n]中所有元素和,记为t。

第六步:算法结束。

例如:origin[n] = {d,c,b,a},target[n] = {a,b,c,d},origin[0] =d,origin[n]中第一个元素编号为0,查找d在target[n]中位置为3,即t[0] = 3,然后将origin[0]对应的字母d从target[n]中删除,对剩余的元素重新从0 开始编号,这是一次完整的操作。按照上述方法不断地进行查找与删除,直到读取完origin[n]最后一个元素,此时target[n]中的元素将被完全删除,t[n]中的所有元素求和记为t,t即为最小混乱值。

2.4 添加交换门算法

提出了一种对非近邻量子门添加交换门的方法,可以准确地计算出每一个非近邻量子门是否具有可以删除的冗余交换门对,并能计算出可以删除多少对冗余交换门对。利用添加交换门算法就可以得到添加最少的交换门,从而得到量子代价最小的量子电路。

在算法中,尽可能在对非近邻量子门添加交换门的同时,与该量子电路中已经存在的交换门组合成一种冗余交换门对,这样不但可以在对该非近邻量子门添加交换门时减少一个交换门代价,还能消除该量子电路中的一个原有交换门。

Nm结构中的交换门与添加交换门算法中添加的交换门,可以产生一些冗余交换门对,将其从量子电路中移除,可以达到降低量子代价的目的。

具体算法描述如下:

第二步:判断低量子位的量子状态,如果处于量子关闭状态,执行第五步。

第三步:计算其量子位相消层数i,添加相应的i个交换门,并消除这i组冗余交换门对,更新gl量子门近邻代价nl的值。

第四步:判断当前nl的值是否为0,如果是则转第七步。

第五步:判断高量子位的量子状态,如果处于量子关闭状态,执行第六步;否则,执行第三步。

第六步:根据nl的值,添加必要的最少的交换门,使非近邻量子门变成近邻化。

第七步:算法结束。

3 实验结果及分析

为了验证算法的有效性和可行性并对算法的实际性能进行分析,所提出算法均使用标准C++语言实现。测试环境为64 位Windows 7 操作系统,Intel(R)Core(TM)i5-2450M CPU@2.50 GHz 处理器,内存为4 GB。使用revlib[12]中的benchmark 电路进行测试,测试数据共31 组,分别涵盖3～8 线的量子电路,测试数据中量子门数量在0～50 之间。Table 1 给出了此处的实验结果与具有代表性的文献[7]的对比分析。表中Benchmark 为标准量子电路名称,n为量子电路线数,Gate 为量子门的数量(不包含一元量子门),S为在量子电路线序不变的前提条件下普通构造LNN 架构添加交换门的数量,s-1 为参考文献[7]中的算法为构造LNN 架构添加的交换门数量,s-2 为所提出算法构造LNN 架构添加的交换门数量,%s-1 为参考文献[7]中的算法为构造LNN 架构添加的交换门数量的优化率,%s-2 为所提出算法构造LNN 架构添加的交换门数量的优化率,Time-1 为参考文献[7]在CPU 内运行时间(单位为s),Time-2为所提出算法CPU 内运行时间(单位为s),%t为所提出算法相比参考文献[7]算法在CPU 内运行时间的优化率,qc为量子电路的量子代价值,○表示参考文献[7]中没有做到实验,而本文做的一些量子电路优化实验。

表1 实验对比结果Table 1 Experimental comparison results

从Table 1 中可以看出,所提出算法在8 线以内,CPU 运行时间都在“s”数量级以内,算法在运行时间上的优化效果显著,平均时间优化率达到99.9%以上。从对量子电路添加交换门数量的对比分析发现,在相同的24 测试数据中,有4 组实验数据添加交换门数量比文献[7]少(其中1 组实验数据添加交换门数量比文献[7]少3 个;2 组实验数据添加交换门数量比文献[7]少6 个;1 组实验数据添加交换门数量比文献[7]少11 个);10 组实验数据添加交换门数量与文献[7]相同;10 组实验数据添加交换门数量比文献[7]略高(其中3 组实验数据添加交换门数量比文献[7]多1 个;4 组实验数据添加交换门数量比文献[7]多2 个;3 组实验数据添加交换们数量比文献[7]多3 个)。

Fig.9 为所提出算法与文献[7] 中算法在构建不同规模量子电路的LNN 架构过程中减少插入的SWAP 门数量的对比图,横轴代表量子电路的规模,纵轴代表该算法相较于普通方法构造LNN 架构降低添加的SWAP 门数量;如图例中所示,点型柱状图代表所提出算法的实验结果,网格型柱状图代表文献[7]中算法的对比结果。从图中可以看出,对于3 线量子线路,所提出算法降低的SWAP 门数量略低于文献[7];对于4 ～5 线的量子电路,所提出算法降低的SWAP 门数量高于文献[7];相比于文献[7]只能处理5 线以内的量子电路,所提出算法适用的量子电路规模为4 ～8 线,且随着量子电路规模的增加,所提出算法在构建LNN 架构过程中减少插入的SWAP 门数量呈上升趋势,相较于文献[7]具有明显优势。结合Table 1 中的数据进行分析,所提出算法添加交换门数量的优化率稳定且优化效果良好,平均优化率达到为62.41%,算法可以处理的量子门数量级别也可以更高;在搜索空间呈指数增长的前提条件下,所提出算法的CPU 运行时间也具有明显优势。

所提出算法可以应用于包含MCT 门或Toffoli 门的级联电路,虽然其解决的问题是针对NCV 门库构成的二量子位量子电路,但算法的适用性已经做了相应扩展,可以满足对revlib 中所有数据测试要求。在NCV-111 量子代价标准[8]基础上研究量子电路线性最近邻问题,近邻化过程中算法的量子代价的变化,取决于近邻化过程中添加的交换门数量。近邻化过程中插入的交换门数量最小,其量子代价亦即最小。近邻化过程中,也可以使用如Fig.3 所示CNOT 门的组合方式替代SWAP 门,每个CNOT 门的量子代价是交换门量子代价的1/3,但由于所提出算法改造后使用CNOT 门组合进行近邻化,每次需要使用3个CNOT 门,所以量子代价总体上不会发生变化。

图9 降低SWAP 门数对比图Fig.9 Swap gate reduction comparison chart

4 结 论

提出了一种将非近邻量子门转换为最近邻状态添加交换门的方法,算法将近邻化过程中新添加的交换门尽可能与原量子电路中已经存在的交换门组成“冗余交换门对”,通过准确计算出非近邻量子门是否具有可以删除的冗余交换门对以及可以删除冗余交换门对的数量,得到近邻化过程中所需添加的最少的交换门数。这种方法在降低新添加的交换门数量的同时消除电路中原有的交换门,能够以较短的时间花费得到量子代价最小的最近邻量子电路。由于应用启发式算法时将一些量子电路线序以中间变量的形式保存在内存中,在大规模量子电路线性最近邻过程中,占用内存过大,搜索时间较长。希望在下一步工作中减少内存空间占用率,缩小运行时间。