电子学报 ›› 2012, Vol. 40 ›› Issue (5): 1045-1049.DOI: 10.3969/j.issn.0372-2112.2012.05.030

• 科研通信 • 上一篇    下一篇

基于二分法量子可逆逻辑电路综合

杨忠明1, 陈汉武1, 王冬1,2   

  1. 1. 东南大学计算机科学与工程学院, 江苏南京 210096;2. 河南大学计算机中心, 河南开封 415002
  • 收稿日期:2010-05-19 修回日期:2011-11-18 出版日期:2012-05-25
    • 基金资助:
    • 国家自然科学基金 (No.60873101,No.61170321)

Qubits Reversible Logic Circuits Synthesis Based on Bisection Method

YANG Zhong-ming1, CHEN Han-wu1, WANG Dong1,2   

  1. 1. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China;2. Computer Center, Henan University, Kaifeng, Henan 415002, China
  • Received:2010-05-19 Revised:2011-11-18 Online:2012-05-25 Published:2012-05-25

摘要: 为了能以较小的代价自动高效地构造量子可逆逻辑电路,提出了一种新颖的量子可逆逻辑电路综合方法.该方法通过线拓扑变换和对换演算,利用递归思想,将n量子电路综合问题转换成单量子电路综合问题,从而完成电路综合,经过局部优化生成最终电路.该算法综合出全部的3变量可逆函数,未优化时平均需6.41个EGT门,优化后平均只需5.22个EGT门;理论分析表明,综合n量子电路最多只需要n2n-1个EGT门.与同类算法相比,综合电路所用可逆门的数量大幅减少.同时该算法还避免了时空复杂度太大的问题,便于经典计算机实现.

关键词: 可逆逻辑, 电路综合, 多量子, 二分法, 量子计算

Abstract: In order to efficiently automatically construct quantum reversible logic circuits with low cost,a novel method for quantum circuit's synthesis is proposed.Through the line topology transformation and truth table permutation,it converts an n-qubit circuit synthesis problem into single quantum circuit synthesis using traditional recursive thought.Then directly generate relevant circuit.After optimization,the quantum reversible logic circuit is synthesized finally.All 3-qubit reversible logic circuits have been synthesized by this method.The average number of EGT gates is only 6.41,and the number is down to 5.22 after optimization.Experimental results show that the number of gates to construct reversible logic circuits is less than other methods.For any n-qubit binary logic function,the number of EGT gates is less than n2n-1.Meanwhile,it voids the exponential nature of the memory or run-time complexity,and is very simple to implement in classical computer.

Key words: reversible logic, circuit's synthesis, multi-qubits, bisection method, quantum computing

中图分类号: