Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimization of Reversible Circuits Using Gate Pair Classification

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

Research on reversible logic gained momentum in the past decade owing to its utility in emerging areas such as quantum computing, optical computing and low power circuit implementation, etc. Reversible circuits synthesized using existing techniques often tend to be sub-optimal; thus, post-synthesis optimization techniques are usually employed to reduce the ‘circuit cost’, a metric used to compare the reversible circuits. In this paper, a set of optimization techniques is proposed to minimize the circuit cost. These techniques rely on classifying a pair of reversible gates in a given circuit based on their structural similarity. An algorithm that maps the classifications with the optimization techniques to improve the cost of a circuit is also proposed. Results obtained for a set of benchmark reversible circuits confirm that the proposed methodology performs better in terms of circuit cost when compared to those available in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

References

  1. Nielsen MA, Chuang IL. Quantum computation and quantum information. Cambridge: Cambridge University Press; 2010.

    Book  Google Scholar 

  2. Cuykendall R, Andersen DR. Reversible optical computing circuits. Opt Lett. 1987;12(7):542–4.

    Article  Google Scholar 

  3. Ciapurin I, Glebov L, Smirnov V. A scheme for efficient quantum computation with linear optics. Phys Rev Lett. 2001;86(22):51885191.

    Google Scholar 

  4. Gao W-B, et al. Experimental realization of a controlled-NOT gate with four-photon six-qubit cluster states. Phys Rev Lett. 2010;104(2):020501.

    Article  Google Scholar 

  5. Landauer R. Irreversibility and heat generation in the computing process. IBM J Res Dev. 1961;5(3):183–91. https://doi.org/10.1147/rd.53.0183.

    Article  MathSciNet  MATH  Google Scholar 

  6. Bennett CH. Logical reversibility of computation. IBM J Res Dev. 1973;17(6):525–32.

    Article  MathSciNet  Google Scholar 

  7. Wille R, Drechsler R, Osewold C, Garcia-Ortiz A. Automatic design of low-power encoders using reversible circuit synthesis. In: DATE ’12, 1036–1041 (EDA Consortium, San Jose, CA, USA, 2012). https://doi.org/10.5555/2492708.2492966.

  8. Saeedi M, Markov IL. Synthesis and optimization of reversible circuits—a survey. ACM Comput Surveys (CSUR). 2013;45(2):21.

    Article  Google Scholar 

  9. Wille R, Drechsler R. Towards a design flow for reversible logic. Berlin: Springer Science & Business Media; 2010.

    Book  Google Scholar 

  10. Maslov D, Dueck GW, Miller DM. Techniques for the synthesis of reversible Toffoli networks. ACM Trans Des Autom Electron Syst. 2007. https://doi.org/10.1145/1278349.1278355.

    Article  Google Scholar 

  11. Arabzadeh M, Saeedi M, Zamani MS. Rule-based optimization of reversible circuits. In: 15th Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE Press;2010. p. 849–54. https://doi.org/10.1109/ASPDAC.2010.5419684. 

    Google Scholar 

  12. Datta K, Sengupta I, Rahaman H. A post-synthesis optimization technique for reversible circuits exploiting negative control lines. IEEE Trans Comput. 2015;64(4):1208–14.

    Article  MathSciNet  Google Scholar 

  13. Datta, K. et al. Exploiting negative control lines in the optimization of reversible circuits. In: RC’13, 209–220 (Springer-Verlag, Berlin, Heidelberg, 2013). https://doi.org/10.1007/978-3-642-38986-3.

  14. Miller DM, Wille R, Drechsler R. Reducing reversible circuit cost by adding lines. In: 40th IEEE International Symposium on Multiple-Valued Logic (ISMVL), IEEE Press; 2010. p. 217–22. https://doi.org/10.1109/ISMVL.2010.48.

  15. Wille R, Soeken M, Drechsler R. Reducing the number of lines in reversible circuits. In: Design Automation Conference, IEEE Press; 2010. p. 647–52. https://doi.org/10.1145/1837274.1837439.

  16. Rice J, Fazel K, Thornton M, Kent K. Toffoli gate cascade generation using ESOP minimization and QMDD-based swapping. In: Proceedings of the Reed-Muller Workshop (RM2009), 2009; p. 63–72.

  17. Bandyopadhyay C, Rahaman H, Drechsler R. Improved cube list based cube pairing approach for synthesis of ESOP based reversible logic. In: Gavrilova, Marina L. et al., editors. Lecture Notes in Computer Science, Vol. 8911. Springer Berlin Heidelberg; 2014, p. 129–46.

  18. Datta K, Gokhale A, Sengupta I, Rahaman H. An ESOP-based reversible circuit synthesis flow using simulated annealing. In: R. Chaki et al., editors. Advances in Intelligent Systems and Computing, Vol. 305. Springer India; 2015, p. 131–44.

  19. Nayeem NM, Rice JE. A shared-cube approach to ESOP-based synthesis of reversible logic. Facta Univ-Ser Electron Energet. 2011;24(3):385–402.

    Article  Google Scholar 

  20. Soeken M, Roetteler M, Wiebe N, De Micheli G. Hierarchical reversible logic synthesis using LUTs. In: 54th ACM/EDAC/IEEE Design Automation Conference (DAC),IEEE Press; 2017. p. 1–6. https://doi.org/10.1145/3061639.3062261.

  21. Fazel K, Thornton M, Rice J. ESOP-based Toffoli gate cascade generation. In: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. IEEE Press; 2007. p. 206–9. https://doi.org/10.1109/PACRIM.2007.4313212

  22. Meuli G, Soeken M, Roetteler M, Wiebe N, De Micheli G. A best-fit mapping algorithm to facilitate ESOP-decomposition in Clifford+T quantum network synthesis. In: 23rd Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE Press; 2018. p. 664–9. https://doi.org/10.1109/ASPDAC.2018.8297398.

  23. Meuli G, Schmitt B, Ehlers R, Riener H, De Micheli G. Evaluating ESOP optimization methods in quantum compilation flows. Cham: Springer International Publishing; 2019. p. 191–206.

    MATH  Google Scholar 

  24. Toffoli T. Reversible computing. Berlin: Springer; 1980.

    Book  Google Scholar 

  25. Barenco A, et al. Elementary gates for quantum computation. Phys Rev A. 1995;52(5):3457.

    Article  Google Scholar 

  26. Wille R, Grosse D, Teuber L, Dueck G, Drechsler R. RevLib: an online resource for reversible functions and reversible circuits. In: 38th International Symposium on Multiple Valued Logic (ISMVL), IEEE Press; 2008. p. 220–5. https://doi.org/10.1109/ISMVL.2008.43.

  27. Maslov D, Dueck GW, Miller DM. Toffoli network synthesis with templates. IEEE Trans Comput Aided Des Integr Circ Syst. 2005;24(6):807–17. https://doi.org/10.1109/TCAD.2005.847911.

    Article  Google Scholar 

  28. Soeken M, Thomsen MK, Dueck GW, Miller DM. White dots do matter: rewriting reversible logic circuits. In: Dueck GW, Miller DM, editors. Reversible computation. Berlin: Springer Berlin Heidelberg; 2013. p. 196–208.

    Chapter  Google Scholar 

  29. Wille R, Soeken M, Otterstedt C, Drechsler R. Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: 18th Asia and South Pacific Design Automation Conference (ASP-DAC), IEEE Press; 2013. p. 145–50. https://doi.org/10.1109/ASPDAC.2013.6509587.

  30. Drechsler R, Finder A, Wille R. Improving ESOP-based synthesis of reversible logic using evolutionary algorithms. In: C. Di. Chio et al., editors. Lecture Notes in Computer Science,Vol. 6625. Springer Berlin Heidelberg; 2011, p. 151–61.

Download references

Author information

Authors and Affiliations

  1. Mediatek, Bangalore, India

    P. Sai Phaneendra

  2. EEE Department, BITS-Pilani, Hyderabad Campus, Hyderabad, India

    Chetan Vudadha & M. B. Srinivas

Authors
  1. P. Sai Phaneendra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chetan Vudadha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. B. Srinivas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. B. Srinivas.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Hardware for AI, Machine Learning and Emerging Electronic Systems” guest edited by Himanshu Thapliyal, Saraju Mohanty and VS Kanchana Bhaaskaran.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sai Phaneendra, P., Vudadha, C. & Srinivas, M.B. Optimization of Reversible Circuits Using Gate Pair Classification. SN COMPUT. SCI. 3, 40 (2022). https://doi.org/10.1007/s42979-021-00900-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-021-00900-5

Keywords

Search

Navigation