Complexity Analysis for Garbage-Free Reversible Computation of Boolean Functions with Variable Ancilla

Reversible computation is a fundamental concept in quantum circuits and low-power design. As the demand for powerful and energy-efficient computing grows, novel design methods for reversible circuits become critical for achieving high performance with low power consumption. Current reversible circuit synthesis methodologies fall into two classes, each minimizing a different parameter in circuit complexity, but often result in relatively high values in another parameter. Post-synthesis optimizations moderate complexity parameters, basically by trading off between them. However, these optimizations depend on specific gate patterns and may not always meet design constraints effectively. This paper proposes a novel recursive decomposition scheme for large Boolean functions using a single-target gate model in reversible circuit synthesis. The proposed scheme systematically and efficiently manages the trade-off between reversible circuit complexity measures, offering gradually varying parameters at each level in the recursion. The scalability of the proposed approach is presented as a comprehensive complexity analysis for the mathematical model. Rather than providing a globally optimal solution, this approach offers a range of solutions, allowing designers to choose the most suitable option based on specific design constraints.