基于真值表演算的量子可逆逻辑电路综合

摘要

随着量子计算与量子信息的深入发展，量子可逆电路的应用越来越多。可逆电路实现的是一个双射的可逆逻辑函数功能。由于它的可逆计算的功能，可逆电路不仅能够应用在量子计算，它同样可以应用在低功耗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个门），进一步降低电路综合的代价。

目录

文摘

英文文摘

第一章 绪论

1.1 研究意义

1.2 研究现状

1.2.1 量子可逆电路的合成

1.2.2 量子可逆电路的优化

1.3 论文工作与组织结构

1.3.1 论文工作

1.3.1 论文组织结构

第二章 可逆逻辑综合基础

2.1 量子逻辑门

2.2 可逆逻辑函数

2.3 可逆逻辑电路

2.4 可逆逻辑电路综合代价

2.5 小结

第三章 基于EGT门库的三量子最优电路综合

3.1 快速综合基本思想

3.2 关键技术的实现

3.1.1 Hash函数的构造

3.1.2 最小长度整体综合算法

3.1.3 读取Hash表中所求量子电路的算法

3.3 基于EGT门库的三量子电路综合

3.4 实验结果

3.5 小结

第四章 基于真值表演算的四量子电路综合

4.1 四量子电路综合方案

4.1.1 真值表中两元素互换规则

4.1.2 多位比特位不同的两元素互换

4.1.3 不同比特位的提取(配合NOT门)

4.2 算法实现

4.3 算法分析

4.4 电路优化

4.4.1 优化规则

4.4.2 优化规则的使用算法

4.5 实验结果

4.6 小结

第五章 基于输出端置换的四量子电路综合

5.1 输出端置换的基本思想

5.2 输出端置换方法的应用

5.3 实验结果及分析

5.3.1 三量子最优电路综合的改进

5.3.2 四量子电路综合的改进

5.4 小结

第六章 多量子可逆逻辑电路综合

6.1 基于三量子最优电路的多量子电路综合

6.1.1 基本思想

6.1.2 综合过程

6.1.3 算法分析

6.2 基于二分法思想的多量子电路综合

6.2.1 基本思想

6.2.2 综合过程

6.2.3 算法分析

6.3 算法比较分析

6.4 小结

第七章 总结与展望

7.1 工作总结

7.2 展望

致谢

参考文献

在校期间发表文章