A cycle-based synthesis algorithm for reversible logic

ABSTRACT

Several algorithms have been proposed for the synthesis of reversible circuits. In this paper, a cycle-based synthesis algorithm for reversible logic, based on the NCT library, has been proposed. In other words, direct implementation of a single 3-cycle, a pair of 3-cycles and a pair of 2-cycles have been explored and used to propose an efficient Toffoli-based synthesis algorithm for reversible circuits. The synthesis algorithm decomposes a given large cycle into a set of single 3-cycles, pairs of 3-cycles and pair of 2-cycles and synthesizes the resulted cycles directly. Our experimental results show that the proposed synthesis algorithm can outperform the available 2-cycle-based approach about 34% on average. In addition, several discussions for the generalization of the proposed method to the 2^m-cycles are given.

REFERENCES

• 1: R. Landauer, "Irreversibility and Heat Generation in the Computing Process," IBM Journal, Vol. 5, pp. 183--191, 1961.
• 2: G. Schrom, "Ultra-Low-Power CMOS Technology," PhD Thesis, Technischen Universitat Wien, 1998.
• 3: E. Knill, R. Laamme, and G. J. Milburn, "A Scheme for Efficient Quantum Computation with Linear Optics," Nature, pp. 46--52, 2001.
• 4: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 5: Mehdi Saeedi , Morteza Saheb Zamani , Mehdi Sedighi, Moving forward: a non-search based synthesis method toward efficient CNOT-based quantum circuit synthesis algorithms, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 6: V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, "Synthesis of Reversible Logic Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 22, No. 6, pp. 710--722, 2003.
• 7: A. Barenco et al., "Elementary gates for quantum computation," Physical Review A, Vol. 52, pp. 3457--3467, 1995.
• 8: A. Slomson, "An Introduction to Combinatorics," CRC Press, 1991.
• 9: D. Maslov, and D. M. Miller, "Comparison of the Cost Metrics for Reversible and Quantum Logic Synthesis," arXiv:quant-ph/0511008 v3, 2006.
• 10: Mehdi Saeedi , Morteza Saheb Zamani , Mehdi Sedighi, On the Behavior of Substitution-based Reversible Circuit Synthesis Algorithms: Investigation and Improvement, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.428-436, March 09-11, 2007 [doi>10.1109/ISVLSI.2007.72]
• 11: P. Gupta, A. Agrawal, N. K Jha, "An Algorithm for Synthesis of Reversible Logic Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, Issue 11, pp. 2317--2330, 2006.
• 12: D. Maslov, G. W. Dueck, D. M. Miller, C. Negrevergne, "Quantum Circuit Simplification and Level Compaction," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, in press, 2008.
• 13: Daniel Große , Xiaobo Chen , Gerhard W. Dueck , Rolf Drechsler, Exact sat-based toffoli network synthesis, Proceedings of the 17th ACM Great Lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy [doi>10.1145/1228784.1228812]
• 14: Vivek V. Shende , Aditya K. Prasad , Igor L. Markov , John P. Hayes, Reversible logic circuit synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.353-360, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774625]