Reversible logic synthesis with Fredkin and Peres gates

ABSTRACT

Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis tool, to include additional gate types. While classic RMRLS can synthesize functions using NOT, CNOT, and n-bit Toffoli gates, our work details the inclusion of n-bit Fredkin and Peres gates. We find that these additional gates reduce the average gate count for three-variable functions from 6.10 to 4.56, and improve the synthesis results of many larger functions, both in terms of gate count and quantum cost.

REFERENCES

• 1: Abhinav Agrawal , Niraj K. Jha, Synthesis of Reversible Logic, Proceedings of the conference on Design, automation and test in Europe, p.21384, February 16-20, 2004
• 2: Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A. 52, 3457--3467.
• 3: Bennett, C. H. 1973. Logical reversibility of computation. IBM J. Res. Dev. 17, 6, 525--532.
• 4: Cuykendall, R. and Andersen, D. R. 1987. Reversible optical computing circuits. Optics Lett. 12, 7, 542--544.
• 5: de Vos, A. 1994. Proposal for an implementation of reversible gates in CMOS. Int. J. Electron. 76, 293--302.
• 6: Dueck, G. W., Maslov, D., and Miller, D. M. 2003. Transformation-based synthesis of networks of Toffoli/Fredkin gates. In Proceedings of the IEEE Canadian Conference on Electrical and Computer Engineering, 211--214.
• 7: Fredkin, E. and Toffoli, T. 1982. Conservative logic. J. Theor. Phys. 21, 219--253.
• 8: Gupta, P., Agrawal, A., and Jha, N. K. 2006. An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 25, 11(Nov.), 2317--2330 (tool available for download: http://www.princeton.edu/~cad/).
• 9: William N. N. Hung , Xiaoyu Song , Guowu Yang , Jin Yang , Marek Perkowski, Quantum logic synthesis by symbolic reachability analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996790]
• 10: Kazuo Iwama , Yahiko Kambayashi , Shigeru Yamashita, Transformation rules for designing CNOT-based quantum circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514026]
• 11: Pawel Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996789]
• 12: Landauer, R. 1961. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5 (Jul.), 183--191.
• 13: Margolus, N. 1988. Physics and computation. Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA.
• 14: Dmitri Aleksandrovich Maslov , Gerhard W. Dueck, Reversible logic synthesis, University of New Brunswick, Fredericton, N.B., Canada, 2003
• 15: Maslov, D. and Dueck, G. W. 2004. Reversible cascades with minimal garbage. IEEE Trans. Comput. Aided. Des. Integr. Circ. Syst. 23, 11 (Nov.), 1497--1509.
• 16: Maslov, D., Dueck, G. W., and Scott, N. 2007. Reversible logic synthesis benchmarks page. http://www.cs.uvic.ca/~dmaslov/.
• 17: Maslov, D., Dueck, G. W., and Miller, D. M. 2005. Toffoli network synthesis with templates. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 24, 6 (Jun.), 807--817.
• 18: Dmitri Maslov , Gerhard W. Dueck , D. Michael Miller, Fredkin/Toffoli Templates for Reversible Logic Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.256, November 09-13, 2003 [doi>10.1109/ICCAD.2003.73]
• 19: Miller, D. M. 2002. Spectral and two-place decomposition techniques in reversible logic. In Proceedings of the IEEE Midwest Symposium on Circuits and Systems, vol. 2,493--496.
• 20: D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775915]
• 21: Peres, A. 1985. Reversible logic and quantum computers. Phys. Rev. A 32, 3266--3276.
• 22: Marek Perkowski , Malgorzata Chrzanowska-Jeske , Alan Mishchenko , Xiaoyu Song , Anas Al-Rabadi , Bart Massey , Pawel Kerntopf , Andrzej Buller , Lech Jozwiak , Alan Coppola, Regular Realization of Symmetric Functions Using Reversible Logic, Proceedings of the Euromicro Symposium on Digital Systems Design, p.245, September 04-06, 2001
• 23: Shende, V. V., Prasad, A. K., Markov, I. L., and Hayes, J. P. 2003. Synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 22, 6 (Jun.), 710--722.
• 24: Smolin, J. A. and Divincenzo, D. P. 1996. Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate. Phys. Rev. A 53, 2855--2856.
• 25: Tommaso Toffoli, Reversible Computing, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.632-644, July 14-18, 1980

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Design

Keywords:
Quantum computing, reversible logic