基于Hash表的量子可逆逻辑电路综合的快速算法  

Fast Algorithms for Synthesis of Quantum Reversible Logic Circuits Based on Hash Table

作　　者：李志强[1,2] 陈汉武[1] 徐宝文[1] 刘文杰[1,3] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]扬州大学信息工程学院,江苏扬州225009 [3]南京信息工程大学计算机科学与技术系,南京210044

出　　处：《计算机研究与发展》2008年第12期2162-2171,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60572071);国家自然科学基金重大研究计划基金项目(90412014);江苏省自然科学基金项目(BK2007104,BK2008209);江苏省高校自然科学基金项目(06KJB520137)~~

摘　　要：量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的491.5倍、365.13倍.Quantum reversible logic circuits are basic elements of quantum computer. The quantum computer can be constructed by cascading and combining the quantum gates. Synthesis of quantum reversible logic circuits automatically constructs the desired quantum reversible logic circuits with minimal quantum cost. By absorbing all kinds of ideas of synthesis of reversible logic circuits, a novel and efficient algorithm is presented, which can construct optimal quantum reversible logic circuits with various types of gates and quantum costs by constructing minimal perfect Hash function. A universal algorithm is proposed, which can automatically construct all kinds of quantum gate libraries through the permutations of quantum lines, to ensure the realization of the automation of quantum circuit synthesis. Judging by the internationally recognized reversible functions of three variables, the algorithm presented not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm, which synthesizes circuit with minimum length or at minimum cost, is 49. 15 and 365. 13 times that of currently best result respectively.

关 键 词：量子电路优化 HASH表 可逆逻辑电路 量子代价 量子计算 

分 类 号：TP387[自动化与计算机技术—计算机系统结构]