An Improved Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

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.