Decision Diagrams and Reversible Computation (Abstract of Invited Talk)

摘要

Decision diagrams have attracted a great deal of attention for thirty years in computer science and technology, because those data structures are useful to efficiently manipulate many kinds of discrete structures, which are the fundamental mathematical models for solving various practical problems. Also for reversible computation systems, decision diagrams are sometimes used as key techniques for solving problems. In this invited talk, we overview the decision diagrams related to reversible computation. First we start with BDD and ZDD as classical models of logic and set. Next we review QMDD (Quantum Multiple-valued Decision Diagrams) and DDMF (Decision Diagrams for Matrix Functions) for dealing with special logic functions computed by quantum logic circuits. We then discuss πDD (Permutation Decision Diagrams) for manipulating permutation, which is closely related to reversible computation. We review some previous work on reversible circuit design using πDDs, and also show our recent work related to reversible computation.