Greedy Algorithm for Optimizing NCT-Based Reversible Circuits Using Optimization Rules
Khaled El-Wazan, Mohamed Hosny Abdo Osman, Ahmed Younes · 2025
Reversible circuit synthesis is critical for quantum computing, but existing methods suffer from high gate counts that increase error susceptibility. This paper introduces a permutation group-driven greedy algorithm that reduces primitive quantum gates systematically in reversible circuits built from NOT, Feyn-man, and Toffoli (NCT) gates. By exploiting the algebraic structure of reversible functions, the proposed method applies iterative gate cancellation and substitution rules to minimize circuit depth. Experiments on NCT-based reversible circuits using IBM's Qiskit demonstrate substantial reductions in primitive quantum gates.