Abstract
In this paper, we study reversible circuits as cascades of multi-target Toffoli gates. This new type of gates allows to shift parts of a gate to the preceding gate within a circuit provided that a certain independence condition holds. It turns out that shifts decrease the so-called waiting degree such that shifting as long as possible always terminates and yields shift-reduced circuits. As the main result, we show that shift-reduced circuits are unique canonical representatives of their shift equivalence classes. Canonical circuits are optimal with respect to maximal and as-early-as-possible parallelism of targets within gates.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bennett, C.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)
Chen, J.-L., Zhang, X.-Y., Wang, L.-L., Wei, X.-Y., Zhao, W.-Q.: Extended Toffoli gate implementation with photons. In: Proceeding of the 9th International Conference on Solid-State and Integrated-Circuit Technology, pp. 575–578. ICSICT (2008)
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation part I: basic concepts and double pushout approach. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1: Foundations, pp. 163–245. World Scientific, Singapore (1997)
Drechsler, R., Finder, A., Wille, R.: Improving ESOP-based synthesis of reversible logic using evolutionary algorithms. In: Di Chio, C., et al. (eds.) EvoApplications 2011, Part II. LNCS, vol. 6625, pp. 151–161. Springer, Heidelberg (2011)
Kreowski, H.-J.: Transformation of derivation sequences in graph grammars. Proceeding of Conference Fundamentals of Computation Theory (Poznan-Kornik, Sept. 1977). LNCS, vol. 56, pp. 275–286. Springer, Heidelberg (1977)
Kreowski, H.-J.: Manipulationen von Graphmanipulationen. Ph.D. thesis, Techni-sche Universität Berlin , Fachbereich Informatik (1978)
Kreowski, H.-J.: An axiomatic approach to canonical derivations. In: Proceedings of IFIP World Computer Congress, IFIP-Transactions, vol. A-51, pp. 348–353. North-Holland (1994)
Soeken, M., Thomsen, M.K.: White dots do matter: rewriting reversible logic circuits. In: RC 2013 Proceedings of the 5th International Conference on Reversible Computation, pp. 196–208, RC 2013, Springer, Heidelberg (2013)
Toffoli, T.: Reversible computing. In: de Bakker, W., van Leeuwen, J. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 85, pp. 632–644. Springer, Heidelberg (1980)
Wille, R., Soeken, M., Otterstedt, C., Drechsler, R.: Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 145–150. IEEE (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Kreowski, HJ., Kuske, S., Lye, A. (2016). Canonical Multi-target Toffoli Circuits. In: Dediu, AH., Janoušek, J., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2016. Lecture Notes in Computer Science(), vol 9618. Springer, Cham. https://doi.org/10.1007/978-3-319-30000-9_46
Download citation
DOI: https://doi.org/10.1007/978-3-319-30000-9_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29999-0
Online ISBN: 978-3-319-30000-9
eBook Packages: Computer ScienceComputer Science (R0)