基于位运算的量子可逆逻辑电路快速综合算法3-扬州大学.PDF

计算机科学 2008Vol35 №3 　 基于位运算的量子可逆逻辑电路快速综合算法 ) 1 ,2 1 1 李志强 　陈汉武 　李文骞 ( ) 1 ( ) 2 东南大学计算机科学与工程学院　南京 2 10096 　 扬州大学信息工程学院　扬州 225009 　 摘 　要 　量子可逆逻辑电路是构建量子计算机的基本单元 。本文结合可逆逻辑电路综合的多种算法 ,根据可逆逻辑 电路综合的本质是置换问题 ,巧妙应用位运算构造高效完备的 Ha sh 函数 ,提出了基于 Ha sh 表的新颖高效的量子可 逆逻辑电路综合算法 ,可使用多种量子门, 以极高的效率生成最优的量子可逆逻辑电路 ,从理论上实现制造量子电路 的成本最低 。按照国际同行认可的 3 变量可逆函数测试标准 ,该算法不仅能够生成全部最优电路 ,而且运行速度远远 超过其它算法 。实验结果表明 ,该算法按最小长度标准综合电路的平均速度是 目前最好结果的 69 . 8 倍 。 关键词 　量子电路优化 , 位运算 , 完备 Ha sh 函数 , 可逆逻辑电路 　 Speedy Algorithm f or Synthesis of Quantum Reversible Logic Circuits Based on Bit Operation L I ZhiQiang1 ,2 　CH EN HanWu1 　L I WenQian1 ( School of Comp ut er Science Engineering , Sout hea st U niver sit y , N anj ing 2 10096) 1 ( College of Infor mation Engineering , Yangzhou U niver sit y , Yangzhou 225009) 2 　 Abstract 　Quant um rever sible logic circuit s are ba sic element s of con st ructing quant um comp ut er . Thi s p ap er ab sorb s all kinds of idea s of synt hesi s of rever sible logic circuit s. Given t hat t he essence of synt hesizing rever sible lo gic circuit s i s p ermut ation , we u se bit op eration to con st ruct t he novel and p erfect Hash function and p resent an efficient algorit hm which can con st ruct op timal quant um rever sible lo gic circuit s wit h variou s t yp es of gat es by u sing t he Hash t able and p roduce quant um circuit s wit h minimal co st in t heory . J udging by t he int ernationally recognized rever sible function s o