Skip to main content
Top

2017 | OriginalPaper | Chapter

Improving Synthesis of Reversible Circuits: Exploiting Redundancies in Paths and Nodes of QMDDs

Authors : Alwin Zulehner, Robert Wille

Published in: Reversible Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In recent years, reversible circuits have become an established emerging technology through their variety of applications. Since these circuits employ a completely different structure from conventional circuitry, dedicated functional synthesis algorithms have been proposed. Although scalability has been achieved by using approaches based on decision diagrams, the resulting circuits employ a significant complexity measured in terms of quantum cost. In this paper, we aim for a reduction of this complexity. To this end, we review QMDD-based synthesis. Based on that, we propose optimizations that allow for a substantial reduction of the quantum costs by jointly considering paths and nodes in the decision diagram that employ a certain redundancy. In fact, in our experimental evaluation, we observe substantial improvements of up to three orders of magnitudes in terms of runtime and up to six orders of magnitudes (a factor of one million) in terms of quantum cost.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
A path to the currently considered node can only traverse the first or the fourth edge of other nodes, because they already establish the identity structure.
 
2
We utilized the methods available at RevKit [14] for logic minimization.
 
Literature
1.
go back to reference Amarù, L.G., Gaillardon, P., Wille, R., Micheli, G.D.: Exploiting inherent characteristics of reversible circuits for faster combinational equivalence checking. In: Design, Automation and Test in Europe, pp. 175–180 (2016) Amarù, L.G., Gaillardon, P., Wille, R., Micheli, G.D.: Exploiting inherent characteristics of reversible circuits for faster combinational equivalence checking. In: Design, Automation and Test in Europe, pp. 175–180 (2016)
2.
go back to reference Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. CAD Integr. Circ. Syst. 32(6), 818–830 (2013) Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. CAD Integr. Circ. Syst. 32(6), 818–830 (2013)
4.
go back to reference Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact multiple control Toffoli network synthesis with SAT techniques. IEEE Trans. CAD 28(5), 703–715 (2009)CrossRef Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact multiple control Toffoli network synthesis with SAT techniques. IEEE Trans. CAD 28(5), 703–715 (2009)CrossRef
6.
go back to reference Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Design Automation Conference, pp. 318–323 (2003) Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Design Automation Conference, pp. 318–323 (2003)
7.
go back to reference Miller, D.M., Thornton, M.A.: QMDD: a decision diagram structure for reversible and quantum circuits. In: International Symposium on Multi-Valued Logic, p. 6 (2006) Miller, D.M., Thornton, M.A.: QMDD: a decision diagram structure for reversible and quantum circuits. In: International Symposium on Multi-Valued Logic, p. 6 (2006)
8.
go back to reference Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffolli gates. In: International Symposium on Multi-Valued Logic, pp. 288–293 (2011) Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffolli gates. In: International Symposium on Multi-Valued Logic, pp. 288–293 (2011)
9.
go back to reference Mishchenko, A., Perkowski, M.: Fast heuristic minimization of exclusive-sums-of-products. In: International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 242–250 (2001) Mishchenko, A., Perkowski, M.: Fast heuristic minimization of exclusive-sums-of-products. In: International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 242–250 (2001)
10.
go back to reference Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2000)MATH Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2000)MATH
11.
go back to reference Niemann, P., Wille, R., Miller, D.M., Thornton, M.A., Drechsler, R.: QMDDs: efficient quantum function representation and manipulation. IEEE Trans. CAD 35(1), 86–99 (2016)CrossRef Niemann, P., Wille, R., Miller, D.M., Thornton, M.A., Drechsler, R.: QMDDs: efficient quantum function representation and manipulation. IEEE Trans. CAD 35(1), 86–99 (2016)CrossRef
12.
go back to reference Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Reversible logic circuit synthesis. In: International Conference on CAD, pp. 353–360 (2002) Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Reversible logic circuit synthesis. In: International Conference on CAD, pp. 353–360 (2002)
13.
go back to reference Soeken, M., Dueck, G.W., Miller, D.M.: A fast symbolic transformation based algorithm for reversible logic synthesis. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 307–321. Springer, Cham (2016). doi:10.1007/978-3-319-40578-0_22 CrossRef Soeken, M., Dueck, G.W., Miller, D.M.: A fast symbolic transformation based algorithm for reversible logic synthesis. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 307–321. Springer, Cham (2016). doi:10.​1007/​978-3-319-40578-0_​22 CrossRef
14.
go back to reference Soeken, M., Frehse, S., Wille, R., Drechsler, R.: RevKit: a toolkit for reversible circuit design. In: Workshop on Reversible Computation, pp. 69–72 (2010). RevKit is available at http://www.revkit.org Soeken, M., Frehse, S., Wille, R., Drechsler, R.: RevKit: a toolkit for reversible circuit design. In: Workshop on Reversible Computation, pp. 69–72 (2010). RevKit is available at http://​www.​revkit.​org
15.
go back to reference Soeken, M., Tague, L., Dueck, G.W., Drechsler, R.: Ancilla-free synthesis of large reversible functions using binary decision diagrams. J. Symb. Comput. 73, 1–26 (2016)MathSciNetCrossRefMATH Soeken, M., Tague, L., Dueck, G.W., Drechsler, R.: Ancilla-free synthesis of large reversible functions using binary decision diagrams. J. Symb. Comput. 73, 1–26 (2016)MathSciNetCrossRefMATH
16.
go back to reference Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: ASP Design Automation Conference, pp. 85–92 (2012) Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: ASP Design Automation Conference, pp. 85–92 (2012)
17.
go back to reference Somenzi, F.: CUDD: CU decision diagram package release 3.0. 0. (2015) Somenzi, F.: CUDD: CU decision diagram package release 3.0. 0. (2015)
18.
go back to reference Wille, R., Drechsler, R., Osewold, C., Ortiz, A.G.: Automatic design of low-power encoders using reversible circuit synthesis. In: Design, Automation and Test in Europe, pp. 1036–1041 (2012) Wille, R., Drechsler, R., Osewold, C., Ortiz, A.G.: Automatic design of low-power encoders using reversible circuit synthesis. In: Design, Automation and Test in Europe, pp. 1036–1041 (2012)
19.
go back to reference Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: International Symposium on Multi-Valued Logic, pp. 220–225 (2008). RevLib is available at http://www.revlib.org Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: International Symposium on Multi-Valued Logic, pp. 220–225 (2008). RevLib is available at http://​www.​revlib.​org
20.
go back to reference Wille, R., Keszocze, O., Hillmich, S., Walter, M., Ortiz, A.G.: Synthesis of approximate coders for on-chip interconnects using reversible logic. In: Design, Automation and Test in Europe (2016) Wille, R., Keszocze, O., Hillmich, S., Walter, M., Ortiz, A.G.: Synthesis of approximate coders for on-chip interconnects using reversible logic. In: Design, Automation and Test in Europe (2016)
21.
go back to reference Zulehner, A., Wille, R.: Taking one-to-one mappings for granted: Advanced logic design of encoder circuits. In: Design, Automation and Test in Europe (2017) Zulehner, A., Wille, R.: Taking one-to-one mappings for granted: Advanced logic design of encoder circuits. In: Design, Automation and Test in Europe (2017)
Metadata
Title
Improving Synthesis of Reversible Circuits: Exploiting Redundancies in Paths and Nodes of QMDDs
Authors
Alwin Zulehner
Robert Wille
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-59936-6_18

Premium Partner