An Improved Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits
Takashi Hirayama, Ryo Endo, Katsuhisa Yamanaka · 2024
This paper presents an improved lower bound, denoted as$v$, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. The previous lower bound$\sigma-lb$used the characteristic vectors of reversible functions to formulate the theory of lower bounds. We carefully investigate cofactors of reversible functions to refine the characteristic vectors, and obtain a new theoretical basis for improving lower bounds. We show that the proposed lower bound$v$is better than the previous lower bound$\sigma-lb$by making both mathematical and experimental comparisons. Although the gain of refinement is not so significant in the experiments, an improvement of lower bounds is valuable as a theoretical achievement.