Minimization of Quantum Multiple-valued Decision Diagrams Using Data Structure Metrics
David Y. Feinstein, Mitchell A. Thornton and D. Michael Miller
This paper describes new metrics for size minimization of the data structure referred to as quantum multiple-valued decision diagrams (QMDD). QMDD are used to represent the matrices describing reversible and quantum gates and circuits. We explore metrics related to the frequency of edges with non-zero weight for the entire QMDD data structure and their histograms with respect to each variable. We observe some unique regularity particular to the methodology of the QMDD. We develop new heuristics for QMDD dynamic variable ordering (DVO) that are guided by the proposed metrics. An exhaustive sifting procedure was implemented for benchmark circuits with up to ten variables to obtain the optimal minimization, demonstrating the effectiveness of the proposed minimization techniques based on data structure metrics.
Keywords: Quantum multiple-valued decision diagrams, quantum logic, reversible logic, sifting, data structure metrics, decision diagram minimization.