电子学报 ›› 2013, Vol. 41 ›› Issue (4): 690-697.DOI: 10.3969/j.issn.0372-2112.2013.04.011

• 学术论文 • 上一篇    下一篇

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

李志强1, 陈汉武2, 刘文杰2, 薛希玲2, 肖芳英2   

  1. 1. 扬州大学信息工程学院,江苏扬州 225009;
    2. 东南大学计算机科学与工程学院,江苏南京 210096
  • 收稿日期:2011-04-06 修回日期:2012-11-07 出版日期:2013-04-25
    • 作者简介:
    • 李志强 男.1974年5月出生,江苏姜堰人.扬州大学副教授,硕士生导师,2011年在东南大学计算机科学与工程学院获工学博士学位,主要从事量子计算、可逆电路综合等方面的研究工作. E-mail:zqli@yzu.edu.cn 陈汉武 男.1955年11月出生,南京人.东南大学教授、博士生导师.2000年3月获日本国立山口大学大学院理工学研究科智能情报专业理工学博士学位.主要从事量子计算、信息论等方面的研究工作. E-mail:hw_chen@seu.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.61070240,No.60572071,No.61170321); 江苏省高校自然科学基金 (No.10KJB520021)

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

LI Zhi-qiang1, CHEN Han-wu2, LIU Wen-jie2, XUE Xi-ling2, XIAO Fang-ying2   

  1. 1. College of Information Engineering, Yangzhou University, Yangzhou, Jiangsu 225009, China;
    2. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China
  • Received:2011-04-06 Revised:2012-11-07 Online:2013-04-25 Published:2013-04-25
    • Supported by:
    • National Natural Science Foundation of China (No.61070240, No.60572071, No.61170321); Natural Science Foundation of the Jiangsu Higher Education Institutions of China (No.10KJB520021)

摘要: 许多量子电路综合算法由于指数级时间与空间复杂度,只能用可逆逻辑门综合3量子逻辑电路,仅有少数算法实现用量子非门,控制非门,控制V门与控制V+门(NCV)综合3量子逻辑电路,主要方法是将电路综合问题简化为四值逻辑综合问题.本文提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优3量子逻辑电路上等价,因此又可将四值逻辑综合问题进一步简化为更易求解的二值逻辑综合问题,使用基于完备Hash函数的3量子电路快速综合算法,快速生成全部最优的3量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果Maslov 2007的近127倍.

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

Abstract: Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum 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 synthesis 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.

Key words: reversible logic, NCV gate library, multiple-valued logic, perfect hash function, quantum cost

中图分类号: