Efficient Construction of QMDDs for Irreversible, Reversible, and Quantum Functions

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.