Reversible Circuit Synthesis Method Using Sub-graphs of Shared Functional Decision Diagrams.

The article focuses on a reversible circuit synthesis method that uses sub-graphs of shared functional decision diagrams (SFDDs) to reduce the number of lines—equivalent to quantum bits (qubits)—required in reversible circuits for quantum computing. By exploiting the longest dominant-active paths (LDAPs) within SFDDs and applying template root matching to reuse circuit lines labeled with primary variables, the method achieves circuits with line counts often equal to the known minimum of \(n + m - s\), where \(n\) and \(m\) are the numbers of inputs and outputs, respectively, and \(s\) is the number of roots matching a specific template. Experimental comparisons with previous functional decision diagram (FDD)-based, quantum multiple-valued decision diagram (QMDD)-based, and lookup table (LUT)-based synthesis methods show that this approach significantly reduces the number of lines in most cases, albeit sometimes at the cost of increased quantum gate count (quantum cost). The method aids the physical realization of quantum circuits by addressing qubit limitations but is limited in scalability due to its reliance on a global SFDD data structure; future work includes improving scalability and circuit quality through further optimizations.