Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Tools for Quantum and Reversible Circuit Compilation Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

REVS: A Tool for Space-Optimized Reversible Circuit Synthesis

verfasst von : Alex Parent, Martin Roetteler, Krysta M. Svore

Erschienen in: Reversible Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Computing classical functions is at the core of many quantum algorithms. Conceptually any classical, irreversible function can be carried out by a Toffoli network in a reversible way. However, the Bennett method to obtain such a network in a “clean” form, i.e., a form that can be used in quantum algorithms, is highly space-inefficient. We present REVS, a tool that allows to trade time against space, leading to circuits that have a significantly smaller memory footprint when compared to the Bennett method. Our method is based on an analysis of the data dependency graph underlying a given classical program. We report the findings from running the tool against several benchmarks circuits to highlight the potential space-time tradeoffs that REVS can realize.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Designing Parity Preserving Reversible Circuits
Nächstes Kapitel Towards VHDL-Based Design of Reversible Circuits
Literatur
1.
2.
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison Wesley, London (2007)MATH
3.
4.
5.
Buhrman, H., Tromp, J., Vitányi, P.: Time and space bounds for reversible simulation. In: Orejas, F., Spirakis, P.G., Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 1017–1027. Springer, Heidelberg (2001). doi:10.​1007/​3-540-48224-5_​82 CrossRef
6.
Pebble games and complexity. Ph.D. thesis, Electrical Engineering and Computer Science, UC Berkeley, Technical report: EECS-2013-145 (2013)
7.
Chattopadhyay, A., Pal, N., Majumder, S.: Ancilla-quantum cost trade-off during reversible logic synthesis using exclusive sum-of-products (2014). arxiv:​1405.​6073
8.
Goldschmidt, O., Hochbaum, D.S., Hurkens, C.A.J., Yu, G.: Approximation algorithms for the \(k\)-clique covering problem. SIAM J. Disc. Math. 9(3), 492–509 (1996)MathSciNetCrossRefMATH
9.
Green, A., LeFanu Lumsdaine, P., Ross, N., Selinger, P., Valiron, B.: Quipper: a scalable quantum programming language. In: PLDI 2013 (2013)
10.
Heckey, J., Patil, S., Javadi Abhari, A., Holmes, A., Kudrow, D., Brown, K.R., Franklin, D., Chong, F.T., Martonosi, M.: Compiler management of communication and parallelism for quantum computation. In: ASPLOS 2015, pp. 445–456. ACM (2015)
11.
JavadiAbhari, A., Patil, S., Kudrow, D., Heckey, J., Lvov, A., Chong, F.T., Martonosi, M.: ScaffCC: scalable compilation and analysis of quantum programs. Parallel Comput. 45, 2–17 (2015)CrossRef
12.
Lange, K.J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. J. Comput. Syst. Sci. 60(2), 354–367 (2000)MathSciNetCrossRefMATH
13.
Lin, C.-C., Jha, N.K.: RMDDS: Reed-Muller decision diagram synthesis of reversible logic circuits. ACM J. Emerg. Technol. Comput. Syst. 10(2), 14 (2014)CrossRef
14.
15.
Maslov, D., Miller, D.M., Dueck, G.W.: Techniques for the synthesis of reversible Toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12(4), 42 (2007)CrossRef
16.
17.
Mishchenko, A., Brayton, R., Chatterjee, S.: Boolean factoring and decomposition of logic networks. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 38–44. IEEE Press (2008)
18.
19.
Muchnick, S.S.: Compiler Design and Implementation. Morgan Kaufmann, San Francisco (1997)
20.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
21.
22.
23.
Perumalla, K.S.: Introduction to Reversible Computing. CRC Press, Boca Raton (2014)
24.
Saeedi, M., Markov, I.L.: Constant-optimized quantum circuits for modular multiplication and exponentiation. Quantum Information and Computation 12(5&6), 361–394 (2012)MathSciNetMATH
25.
Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits - a survey. ACM Comput. Surv. 45(2), 21 (2013)CrossRefMATH
26.
Shafaei, A., Saeedi, M., Pedram, M.: Reversible logic synthesis of \(k\)-input, \(m\)-output lookup tables. In: DATE 2013, pp. 1235–1240 (2013)
27.
Soeken, M., Robert Wille, R., Hilken, Ch., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: Proceedings of ASP-DAC 2012 (2012)
28.
Syme, D., Granicz, A., Cisternino, A.: Expert F\(\#\) 3.0. Apress Publishing, New York (2012)CrossRef
29.
Thomsen, M.K.: A functional language for describing reversible logic. In: Forum on Specification and Design Languages, pp. 135–142. IEEE (2012)
30.
Viamontes, G.F., Markov, I.L., Hayes, J.P.: Quantum Circuit Simulation. Springer, Heidelberg (2009)CrossRefMATH
31.
Wille, R., Drechsler, R.: BDD-based synthesis of reversible logic for large functions. In: Proceedings of DAC 2009, pp. 270–275 (2009)
32.
Wille, R., Drechsler, R.: Towards a Design Flow for Reversible Logic. Springer, Dodrecht (2010)CrossRefMATH
33.
Wille, R., Offermann, S., Drechsler, R.: SyReC: a programming language for synthesis of reversible circuits. In: Specification Design Languages (FDL), pp. 1–6 (2010)
34.
Wille, R., Soeken, M., Drechsler, R.: Reducing the number of lines in reversible circuits. In: Proceedings of DAC 2010, pp. 647–652 (2010)
35.
Wille, R., Soeken, M., Miller, D.M., Drechsler, R.: Trading off circuit lines and gate costs in the synthesis of reversible logic. Integration 47(2), 284–294 (2014)
36.
Yokoyama, T., Glück, R.: A reversible programming language and its invertible self-interpreter. In: PEPM 2007, pp. 144–153 (2007)
Metadaten
Titel
REVS: A Tool for Space-Optimized Reversible Circuit Synthesis
verfasst von
Alex Parent
Martin Roetteler
Krysta M. Svore
Copyright-Jahr
2017
Buch
Reversible Computation

Print ISBN: 978-3-319-59935-9

Electronic ISBN: 978-3-319-59936-6

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-59936-6_7

Premium Partner

    Bildnachweise