An Extension of Transformation-based Reversible and Quantum Circuit Synthesis

Transformation-based synthesis is a well established systematic approach to determine a circuit implementation from a reversible function specification. Due to the inherent bidirectionality of reversible circuits the basic method can be applied in a bidirectional manner. In the approaches to date, gates are added either to the input side or the output side of the circuit on each iteration. In this paper, we introduce a new variation where gates may be added at both ends during a single iteration when this is advantageous to reducing the cost of the circuit. Experimental results show the advantage of the new approach over previous transformation-based synthesis methods and that the additional computation is justified by the possibility of improved circuit costs.