Reversible Logic Synthesis Based on Decision Diagram Variable Ordering
David Y. Feinstein and Mitchell A. Thornton
Reversible logic synthesis is important for the design of conventional logic systems such as adiabatic logic and also for quantum logic systems since all quantum logic gates are necessarily reversible in nature. A framework is presented that improves reversible logic synthesis by employing a dynamically determined variable order for quantum multiple-valued decision diagrams (QMDD). We demonstrate our approach through augmentation of the Miller-Maslov-Dueck (MMD) synthesis algorithm that processes the complete function specification in lexicographical order with our technique. We represent and minimize the complete specification with the QMDD and then synthesize the function specification based on the minimized variable order. The framework produces significantly smaller reversible circuits in many cases. Experimental results also show the effectiveness of using the QMDD size as a measure of the complexity of MVL and binary reversible circuits.
Keywords: Reversible logic synthesis; quantum multiple-valued decision diagrams