Application of the Maximum Weighted Matching to Quantum Cost Reduction in Reversible Circuits

J. Jegier (Orange Labs, Poland), P. Kerntopf (Univ. of Lodz, Poland)

We applied the maximum weighted matching (PMWM) method, well-known from the graph theory, to reduction of quantum cost (QC) in reversible sub-circuits with a common target line. In this way, possibility of application of the PMWM method to optimization of QC is showed for the first time in literature on reversible circuit synthesis. Experimental results have shown that this approach leads to substantial reduction of QC.