Efficient construction of QMDDs for irreversible, reversible, and quantum functions

Philipp Niemann, Alwin Zulehner, Robert Wille, Rolf Drechsler

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

In reversible as well as quantum computation, unitary matrices (so-called transformation matrices) are employed to comprehensively describe the respectively considered functionality. Due to the exponential growth of these matrices, dedicated and efficient means for their representation and manipulation are essential in order to deal with this complexity and handle reversible/quantum systems of considerable size. To this end, Quantum Multiple-Valued Decision Diagrams (QMDDs) have shown to provide a compact representation of those matrices and have proven their effectiveness in many areas of reversible and quantum logic design such as embedding, synthesis, or equivalence checking. However, the desired functionality is usually not provided in terms of QMDDs, but relies on alternative representations such as Boolean Algebra, circuit netlists, or quantum algorithms. In order to apply QMDD-based design approaches, the corresponding QMDD has to be constructed first—a gap in many of these approaches. In this paper, we show how QMDD representations can efficiently be obtained for Boolean functions, both reversible and irreversible ones, as well as general quantum functionality.

Original languageEnglish
Title of host publicationReversible Computation - 9th International Conference, RC 2017, Proceedings
EditorsHafizur Rahaman, Iain Phillips
PublisherSpringer Verlag
Pages214-231
Number of pages18
ISBN (Print)9783319599359
DOIs
StatePublished - 2017
Externally publishedYes
Event9th International Conference on Reversible Computation, RC 2017 - Kolkata, India
Duration: 6 Jul 20177 Jul 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Reversible Computation, RC 2017
Country/TerritoryIndia
CityKolkata
Period6/07/177/07/17

Fingerprint

Dive into the research topics of 'Efficient construction of QMDDs for irreversible, reversible, and quantum functions'. Together they form a unique fingerprint.

Cite this