Effect of Negative Control Lines on the Exact Synthesis of Reversible Circuits

Synthesis of reversible circuits has emerged as an important research area. Applications in the domain of quantum computation and low-power design benefit directly from the achieved improvements. Besides heuristic methods, also exact synthesis received significant attention. Here, circuits realizing the desired functions e.g. with a minimal number of gates are determined. However, only Toffoli gates with positive control lines have been considered so far. In this paper, we study the effect of negative control lines on the exact synthesis of reversible circuits. For this purpose, we extend an existing approach so that the larger degree of freedom is considered. Through experimental evaluations, the precise effect of negative control lines on the minimal circuit sizes for reversible functions is investigated. Furthermore, we also evaluate the effect of this on the respective run-times. In fact, we can observe that, although the search space theoretically increases, minimal circuits sometimes can be generated even faster than without the explicit consideration of negative control lines.