Techniques for the synthesis of reversible Toffoli networks

ABSTRACT

We present certain new techniques for the synthesis of reversible networks of Toffoli gates, as well as improvements to previous methods. Gate count and technology oriented cost metrics are used. Two new synthesis procedures employing Reed-Muller spectra are introduced and shown to complement earlier synthesis approaches. The previously proposed template simplification method is enhanced through the introduction of a faster and more efficient template application algorithm, an updated classification of the templates, and the addition of new templates of sizes 7 and 9. A resynthesis approach is introduced wherein a sequence of gates is chosen from a network, and the reversible specification it realizes is resynthesized as an independent problem in hopes of reducing the network cost. Empirical results are presented to show that the methods are efficient in terms of the realization of reversible benchmark specifications.

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. A., 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. R&D, 17, 525--532.
• 4: Cory, D. G., Laflamme, R., Knill, E., Viola, L., Havel, T. F., Boulant, N., Boutis, G., Fortunato, E., Lloyd, S., Martinez, R., Negrevergne, C., Pravia, M., Sharf, Y., Teklemariam, G., Weinstein, Y. S., and Zurek, W. H. 2000. NMR-Based quantum information processing: achievements and prospects. Wiley Inter Science.
• 5: Feynman, R. 1985. Quantum mechanical computers. Optic. News, 11, 11--20.
• 6: Gershenfeld, N. and Chuang, I. L. 1980. Quantum computing with molecules. Scientific American.
• 7: Häffner, H., Hänsel, W., Roos, C. F., Benhelm, J., Chek-al-kar, D., Chwalla, M., Körber, T., Rapol, U. D., Riebe, M., Schmidt, P. O., Becher, C., Gühne, O., Dür, W., and Blatt, R. 2005. Scalable multiparticle entanglement of trapped ions. Nature, 438, 643--646.
• 8: 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]
• 9: 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]
• 10: Landauer, R. 1961. Irreversibility and heat generation in the computing process. IBM J. R&D, 5, 183--191.
• 11: Lee, S., Lee, S., Kim, T., Lee, J., Biamonte, J., and Perkowski, M. 2006. The cost of quantum gate primitives. J. Multiple-Valued Logic Soft Comp., 12(5--6).
• 12: Lomont, C. 2003. Quantum circuit identities. Arxiv quant-ph/0307111.
• 13: Maslov, D. and Dueck, G. W. 2004. Reversible cascades with minimal garbage. IEEE Trans. Comput. Aid. Des., 23, 11, 1497--1509.
• 14: Maslov, D., Dueck, G., and Scott, N. 2005a. Reversible logic synthesis benchmarks page. http://www.cs.uvic.ca/~dmaslov/.
• 15: Maslov, D., Dueck, G. W., and Miller, D. M. 2005b. Toffoli network synthesis with templates. IEEE Trans. Comput. Aid. Des. 24, 6, 807--817.
• 16: D. Maslov , C. Young , D. M. Miller , G. W. Dueck, Quantum Circuit Simplification Using Templates, Proceedings of the conference on Design, Automation and Test in Europe, p.1208-1213, March 07-11, 2005 [doi>10.1109/DATE.2005.249]
• 17: Merkle, R. C. 1993a. Reversible electronic logic using switches. Nanotechn., 4, 21--40.
• 18: Merkle, R. C. 1993b. Two types of mechanical reversible logic. Nanotechn., 4, 114--131.
• 19: Miller, D. M. 2002. Spectral and two-place decomposition techniques in reversible logic. In Proceedings of the 45th IEEE Midwest Symposium on Circuits and Systems. 493--496.
• 20: Mishchenko, A. and Perkowski, M. 2002. Logic synthesis of reversible wave cascades. In Proceedings of the International Workshop on Logic and Synthesis, pp. 197--202.
• 21: Negrevergne, C., Mahesh, T. S., Ryan, C. A., Ditty, M., Cyr-Racine, F., Power, W., Boulant, N., Havel, T., Cory, D. G., Laflamme, R. 2006. Benchmarking quantum control methods on a 12-qubit system. Physic. Rev. Lett..
• 22: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 23: Patel, K. N., Markov, I. L., and Hayes, J. P. 2004 Efficient Synthesis of Linear Reversible Circuits. In Proceedings of the International Workshop on Logic and Synthesis, 470--477.
• 24: Peres, A. 1985. Reversible logic and quantum computers. Phys. Rev. A, 32, 3266--3276.
• 25: Schrom, G. 1980 Ultra-low-power CMOS technology. PhD thesis, Technische Universität Wien, 1998.
• 26: Shende, V. V., Prasad, A. K., Markov, I. L. and Hayes, J. P. 2003. Synthesis of reversible logic circuits. IEEE Trans. Comput. Aid. Des. 226, 723--729.
• 27: Aditya K. Prasad , Vivek V. Shende , Igor L. Markov , John P. Hayes , Ketan N. Patel, Data structures and algorithms for simplifying reversible circuits, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.4, p.277-293, October 2006 [doi>10.1145/1216396.1216399]
• 28: Mitchell Aaron Thornton , D. Michael Miller , Rolf Drechsler, Spectral Techniques in VLSI CAD, Kluwer Academic Publishers, Norwell, MA, 2001
• 29: Toffoli, T. 2001. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Computer Science.
• 30: Tsai, I. M. and Kuo, S. Y., 2001. Quantum boolean circuit construction and layout under locality constraint. In IEEE Conference on Nanotechnology, 111--116.
• 31: Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., and Chuang, I. L. 2006. Experimental realization of Shor's quantum factoring algorithm using Nuclear Magnetic Resonance. Nature, 414: 883--887.
• 32: Zhirnov, V. V., Kavin, R. K., Hutchby, J. A., and Bourianoff, G. I. 2003. Limits to binary logic switch scaling---a Gedanken model. Proc. IEEE, 91 11, 1934--1939.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
      B.6.3 Design Aids

Keywords:
circuit optimization, quantum computing, reversible logic synthesis