基于新型量子逻辑门库的最优NCV三量子电路快速综合算法  

Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library

作　　者：李志强[1] 陈汉武[2] 刘文杰[2] 薛希玲[2] 肖芳英[2] 

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

出　　处：《电子学报》2013年第4期690-697,共8页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61070240;No.60572071;No.61170321);江苏省高校自然科学基金(No.10KJB520021)

摘　　要：许多量子电路综合算法由于指数级时间与空间复杂度,只能用可逆逻辑门综合3量子逻辑电路,仅有少数算法实现用量子非门,控制非门,控制V门与控制V+门(NCV)综合3量子逻辑电路,主要方法是将电路综合问题简化为四值逻辑综合问题.本文提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优3量子逻辑电路上等价,因此又可将四值逻辑综合问题进一步简化为更易求解的二值逻辑综合问题,使用基于完备Hash函数的3量子电路快速综合算法,快速生成全部最优的3量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果Maslov2007的近127倍.Owing to the exponential nature of the memory or run-lLrne complexity,many existing methods can only synthe- size 3-qubit logic circuits using quantum logic gate library, however, a few can optimally synthesize 3-qubit logic circuits for quan- tum NOT, CNOT, Controlled-V and Controlled-V ＋ （NCV）gates, the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis. This paper proposes using NCV gates to create a new quantum logic gate library, which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic syn- thesis to easily solved two-valued logic synthesis. We present a 3-qubit efficient synthesis algorithms based on perfect hash function, which can quickly construct all optimal 3-qubit circuits--the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.

关 键 词：可逆逻辑 NCV门库 多值逻辑 完备Hash函数 量子代价 

分 类 号：TN911.23[电子电信—通信与信息系统]