论文部分内容阅读
随着量子计算与量子信息的深入发展,量子可逆电路的应用越来越多。可逆电路实现的是一个双射的可逆逻辑函数功能。由于它的可逆计算的功能,可逆电路不仅能够应用在量子计算,它同样可以应用在低功耗CMOS、纳米技术以及光计算等领域,因此量子可逆逻辑电路的研究对于量子计算与量子信息的发展具有重要的意义。
探讨以较小的代价(最少的可逆门)自动高效地构造量子可逆逻辑电路,是可逆逻辑电路综合研究的重点。目前,各种量子逻辑电路综合算法,都存在量子逻辑电路规模小、综合代价过高、优化时空复杂度高等一系列问题,还不能满足未来量子计算和量子信息以及其他领域对量子可逆逻辑电路要求。本文采用扩展的通用Toffoli门(EGT)作为基本门库,综合出全部三量子最优电路;然后以三量子最优电路为基础,提出了一种新颖的四量子可逆逻辑综合方法;接着通过三条规则(消去、合并和移动)对电路进行优化,通过真值表输出端置换的思想,综合四量子可逆逻辑函数,以减少EGT门的数量;最后对四量子电路综合方案进行递推拓展,提出两种任意量子可逆逻辑电路综合的新方法:①基于三量子最优电路的多量子电路综合,②基于二分法思想的多量子电路综合。
选用EGT门库综合出全部的三量子电路,共40320个,与传统选用TOF门库综合相比,电路最大长度减少了2个门(从8减少到6个门),平均长度减少了21.98%(从5.87减少到4.58个门)。四量子电路综合方法是先将一个四量子电路的函数表示成真值表的形式;通过线拓扑变换和对换演算,将四量子电路映射函数的真值表分解成2块相互独立的三量子电路映射函数的真值表;查找相应的最优三量子电路,直接生成相关电路;最后将对换演算的电路并入该电路,经过局部优化即可生成最终电路。分析结果表明,用这种方法综合四量子电路平均需13.16个EGT门,最多只需要20个EGT门。与同类算法相比,大幅减少EGT门的数量,同时还避免了时空复杂度太大的问题,便于经典计算机实现。使用输出端置换思想改进四量子电路综合方案,分析结果表明,平均EGT门的数量减少了16.81%(从13.16减少到10.95个门),进一步降低电路综合的代价。