On the Q in QMDDs: Efficient representation of quantum functionality in the qmdd data-structure

The Quantum Multiple-valued Decision Diagram (QMDD) data-structure has been introduced as a means for an efficient representation and manipulation of transformation matrices realized by quantum or reversible logic circuits. A particular challenge is the handling of arbitrary complex numbers as they frequently occur in quantum functionality. These numbers are represented through edge weights which, however, represent a severe obstacle with respect to canonicity, modifiability, and applicability of QMDDs. Previously introduced approaches did not provide a satisfactory solution to these obstacles. In this paper, we propose an improved factorization scheme for complex numbers that ensures a canonical representation while, at the same time, allows for local changes. We demonstrate how the proposed solution can be exploited to improve the data-structure itself (e.g. through variable re-ordering enabled by the advanced modifiability) and how applications such as equivalence checking benefit from that.