New Bounds for Quick Computation of the Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits

Takashi HIRAYAMA, Rin SUZUKI, Katsuhisa YAMANAKA, Yasuaki NISHITANI

Summary :

We present a time-efficient lower bound κ on the number of gates in Toffoli-based reversible circuits that represent a given reversible logic function. For the characteristic vector s of a reversible logic function, κ(s) closely approximates σ-lb(s), which is known as a relatively efficient lower bound in respect of evaluation time and tightness. The primary contribution of this paper is that κ enables fast computation while maintaining a tightness of the lower bound, approximately equal to σ-lb. We prove that the discrepancy between κ(s) and σ-lb(s) is at most one only, by providing upper and lower bounds on σ-lb in terms of κ. Subsequently, we show that κ can be calculated more efficiently than σ-lb. An algorithm for κ(s) with a complexity of 𝓞(n) is presented, where n is the dimension of s. Experimental results comparing κ and σ-lb are also given. The results demonstrate that the two lower bounds are equal for most reversible functions, and that the calculation of κ is significantly faster than σ-lb by several orders of magnitude.

• Publication: IEICE TRANSACTIONS on Information Vol.E107-D No.8 pp.940-948
• Publication Date: 2024/08/01
• Publicized: 2024/05/10
• Online ISSN: 1745-1361
• DOI: 10.1587/transinf.2023LOP0003
• Type of Manuscript: Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)

1.  Introduction

Quantum computing has gained the interest of many researchers due to its promising high-performance computing as well as its potential low-energy consumption. The synthesis of reversible logic circuits is a fundamental part of the quantum logic field [2]. Figure 1 shows an example of a 4-bit reversible circuit, consisting of five gates \(G_1, G_2, \ldots, G_5\). NOT, CNOT, and Toffoli gates are typically used to synthesize reversible logic circuits [3]-[6]. Fredkin and SWAP gates are also known [7]-[9] as other types of reversible logic gates. Figure 2 shows an example of Toffoli gates. The standard Toffoli with three bits, as depicted in Fig. 2 (c), is often generalized to \(k\)-bit Toffoli such as Fig. 2 (d). In this sense, NOT and CNOT can be regarded as 1-bit and 2-bit Toffoli gates, respectively. A \(k\)-bit Toffoli gate has \((k-1)\) control lines \(x_1,x_2, \ldots, x_{k-1}\), denoted by \(\bullet\), and a single target line \(x_k\), denoted by \(\oplus\). The target line maps \(x_k\) to \(x_k \oplus x_1 x_2 \cdots x_{k-1}\) while the remaining lines propagate their signals without change. That is, a Toffoli gate inverts the value of the target line if all the control lines are assigned to 1. The set of these 1-, 2-, \(\ldots, k\)-bit Toffoli gates is referred to as the general Toffoli library. We discuss the reversible logic synthesis with the general Toffoli library.

Fig. 1  Example of a reversible circuit.

Fig. 2  Example of Toffoli gates.

The gate count (GC) is one of the most widely-used cost metrics for reversible logic circuits. There are many other technology-specific cost metrics [10]-[12], including the number of elementary gates, quantum cost, delay, depth, etc. However, their relevance will change depending on future developments in quantum technologies. For this reason, GC is commonly used as a fundamental cost metric. Although different gates require different resources in a more precise sense, this metric approximately reflects the complexity of circuits.

The upper and lower bounds on the GC have both theoretical and practical significance as a measure of the complexity of reversible circuits. Many studies have investigated upper [13], [14] and lower bounds for various classes of functions. Maslov et al. [15], Shende et al. [16], Soeken et al. [17], and Zakablukov [18] presented bounds on the GC of reversible circuits for the class of all \(n\)-input reversible functions under different constraints of ancillae, garbage outputs, gate types, etc. Popescu et al. [19] and Maslov [20] analyzed the bounds on the number of particular gate types in the NOT-CNOT-Toffoli library. Saeedi et al. [21] discussed the upper bounds for the classes of functions with various lengths of cycles.

For individual reversible functions, a circuit simplified by a heuristic synthesizer [3]-[5], [7], [9], [22], [23] can be seen as an upper bound for the exact minimum circuit. In this context, a lot of methods to determine upper bounds for given functions have already been studied.

Compared to upper bounds, works for the lower bounds for individual reversible functions are fewer. We deal with fully-specified \(n\)-variable reversible functions, and their circuit realization with the general Toffoli library without adding ancillae or garbage lines. Regarding the lower bounds for given functions, some bounds have been proposed based on the Positive Polarity Reed-Muller expressions [24], [25]. This type of bounds has practical applications as well as theoretical significance. They can be used to evaluate the complexity of functions in heuristic synthesis algorithms [26] or to reduce the search space in branch-and-bound algorithms [27]. For these applications, not only is the tightness of the bound essential, but low-cost computation is also crucial because the bound calculation is repeated extensively throughout the execution of algorithms.

\(\sigma\text{$-$}lb(\boldsymbol{s})\), presented in the literature [25], is a lower bound on the GC of Toffoli-based reversible logic circuits of a given reversible logic function, where \(\boldsymbol{s}\) is its characteristic vector. Although the bound \(\sigma\text{$-$}lb(\boldsymbol{s})\) is tighter than the other ones proposed so far, its computation time is an obstacle to its application to synthesis algorithms of reversible circuits. Basically, the calculation of \(\sigma\text{$-$}lb(\boldsymbol{s})\) involves an exhaustive search within an \(n\)-ary tree, where \(n\) denotes the dimension of the vector \(\boldsymbol{s}\). For a characteristic vector \(\boldsymbol{s}\) of a reversible function, the depth of the \(n\)-ary tree is proportional to \(n\) in maximum. It follows that the time complexity of the computation is roughly \(\mathcal{O}(n^{cn})\), where \(c\) is a constant. As such, the computation of \(\sigma\text{$-$}lb(\boldsymbol{s})\) is time-consuming. In this paper, we investigate the upper and lower bounds on \(\sigma\text{$-$}lb(\boldsymbol{s})\) and present a new lower bound \(\tilde{\sigma}(\boldsymbol{s})\) and its faster version \(\kappa(\boldsymbol{s})\). The value of \(\kappa(\boldsymbol{s})\) is almost the same as \(\sigma\text{$-$}lb(\boldsymbol{s})\); the discrepancy between \(\kappa(\boldsymbol{s})\) and \(\sigma\text{$-$}lb(\boldsymbol{s})\) is at most one only. Meanwhile, \(\kappa(\boldsymbol{s})\) can be calculated quickly from \(\boldsymbol{s}\) with a time complexity of \(\mathcal{O}(n)\).

The paper is organized as follows. Section 2 introduces the necessary preliminaries. It reviews the previous lower bound \(\sigma\text{$-$}lb\) and gives our new lower bound \(\tilde{\sigma}\). To make a theoretical comparison, Sects. 3 and 4 present bounds on \(\sigma\text{$-$}lb\) in terms of \(\tilde{\sigma}\). In Sect. 5, a fast version of \(\tilde{\sigma}\) is proposed and termed \(\kappa\). The experimental results are reported in Sect. 6. We conclude in Sect. 7.

2.  Preliminaries

To discuss lower bounds on the gate count (GC) of reversible circuits, we define a characteristic vector \(\boldsymbol{\varLambda}(F)\) of a reversible function \(F\) by using positive polarity Reed-Muller expressions (PPRMs) and then briefly refer to the previous lower bound \(\sigma\text{$-$}lb\) [25]. Similar to “\(\boldsymbol{\varLambda}\),” we employ boldface to denote arithmetic functions that produce a vector.

It is known that any logic function can be uniquely represented by PPRM [28], [29]. For example, the logic function \(x_1\bar{x}_2 + x_2\) is written as \(x_1 \oplus x_2 \oplus x_1x_2\) in PPRM, where “\(\oplus\)” denotes the EXOR operation.

Definition 1: Let \(x^0\) and \(x^1\) denote \(1\) and \(x\), respectively. The logical expression in the form:

\[\begin{equation*} \bigoplus_{0 \le i \le 2^n-1} a_{i} \cdot x_{n}^{i_{n}} x_{n-1}^{i_{n-1}} \cdots x_{1}^{i_{1}} \tag{1} \end{equation*}\]

is a positive polarity Reed-Muller expression (PPRM), where \((i_{n}, i_{n-1}, \ldots, i_1)\) is the binary representation of \(i\), and \(a_i \in \{0,1\}\) is a constant. \(\tag*{◻}\)

Definition 2: A multiple-output logic function \(F: \{0,1\}^n \rightarrow \{0,1\}^n\) is reversible if and only if \(F\) is bijective. The number of product terms in the PPRM of a single-output logic function \(f\) is denoted by \(\tau(f)\). Suppose that \(F\) is a reversible function of \(n\) input variables \((x_1, x_2, \ldots, x_n)\) and \(n\) output functions \((f_1, f_2, \ldots, f_n)\). \(\boldsymbol{\varLambda}(F)\) is defined as the vector \([\tau(x_1 \oplus f_1), \tau(x_2 \oplus f_2), [0] \ldots, \tau(x_n \oplus f_n)]\) and is called the characteristic vector of \(F\). \(\tag*{◻}\)

\(\tau(x_i \oplus f_i)\) is called the Hamming distance in the Reed-Muller spectrum between \(x_i\) and \(f_i\) [26].

Example 1: Let \(F\) be the reversible function of the circuit in Fig. 1, in which the output functions are represented in PPRM form as \(f_1 = x_1 \oplus x_4, f_2 = x_2 \oplus x_1x_3 \oplus x_4 \oplus x_1x_4 \oplus x_3x_4, f_3 = x_3 \oplus x_1x_3 \oplus x_1x_2x_3 \oplus x_4 \oplus x_1x_4 \oplus x_2x_4 \oplus x_1x_2x_4 \oplus x_3x_4 \oplus x_2x_3x_4, f_4 = x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3 \oplus x_1x_4 \oplus x_2x_4 \oplus x_1x_2x_4 \oplus x_1x_3x_4 \oplus x_2x_3x_4\). Then, \(\tau(x_1 \oplus f_1) = \tau(x_1 \hspace{-1em}\lower{0.25em} ／ \oplus x_1 \hspace{-1em}\lower{0.25em} ／ \oplus x_4) = \tau(x_4)=1\), \(\tau(x_2 \oplus f_2)=\tau( x_2 \hspace{-1em}\lower{0.25em} ／ \oplus x_2 \hspace{-1em}\lower{0.25em} ／ \oplus x_1x_3 \oplus x_4 \oplus x_1x_4 \oplus x_3x_4 = \tau(x_1x_3 \oplus x_4 \oplus x_1x_4 \oplus x_3x_4)=4\), \(\tau(x_3 \oplus f_3)= \tau(x_3 \hspace{-1em}\lower{0.25em} ／ \oplus x_3 \hspace{-1em}\lower{0.25em} ／ \oplus x_1x_3 \oplus x_1x_2x_3 \oplus x_4 \oplus x_1x_4 \oplus x_2x_4 \oplus x_1x_2x_4 \oplus x_3x_4 \oplus x_2x_3x_4)=8\), \(\tau(x_4 \oplus f_4)= \tau(x_4 \oplus x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3 \oplus x_1x_4 \oplus x_2x_4 \oplus x_1x_2x_4 \oplus x_1x_3x_4 \oplus x_2x_3x_4)=9\). Thus, the characteristic vector of \(F\) is \(\boldsymbol{\varLambda}(F)=[1,4,8,9]\). \(\tag*{◻}\)

We present the following proposition on the maximum value of elements in \(\boldsymbol{\varLambda}(F)\) because the number of product terms in the PPRM of an \(n\)-variable function is at most \(2^{n}-1\). In this paper, the term “proposition” indicates a theorem that is well known, elementary, or immediately obvious without proof.

Proposition 1: Let \(F\) be a reversible function of \(n\) variables. Every element in \(\boldsymbol{\varLambda}(F)\) is a non-negative integer less than or equal to \(2^{n}-1\). \(\tag*{◻}\)

Definition 3: Among all reversible circuits that realize a reversible function \(F\), those with the exact minimum GC are called the minimum circuits of \(F\). The GC of a minimum circuit of \(F\) is denoted by \(\gamma(F)\). \(\tag*{◻}\)

Theorem 1 (Lower Bound Theorem [25]): For any reversible function \(F\),

\[\gamma(F) \ge \sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\]

holds. \(\tag*{◻}\)

Theorem 1 shows that \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\) is a lower bound on the GC of a minimum circuit of \(F\). The definition of \(\sigma\text{$-$}lb\) is described below.

Definition 4: The set of non-negative integers is denoted by \(\mathbb{N}_0\), and the \(n\)-dimensional space of \(\mathbb{N}_0\) is denoted by \(\mathbb{N}_0^{n}\). An index is an integer in \(\{1,2,\ldots,n\}\). Suppose that \(\boldsymbol{s}\) is a vector \([s_1, s_2, \ldots, s_n] \in \mathbb{N}_0^{n}\), and \(a\) is an index. The function \(\boldsymbol{\varPhi}(\boldsymbol{s}, a) = [s'_1, s'_2, \ldots, s'_n]\) is defined as follows.

\[s'_i = \left\{ \begin{array}{ll} \lfloor s_i/2 \rfloor & \mbox{($i=a$)} \\ \lceil s_i/2 \rceil & \mbox{(otherwise)} \end{array} \right.\]

We extend \(\boldsymbol{\varPhi}\) to allow it to accept a sequence of indices as its second argument:

\[\left\{ \begin{array}{l} \boldsymbol{\varPhi}(\boldsymbol{s}, \varepsilon) = \boldsymbol{s} \\ \boldsymbol{\varPhi}(\boldsymbol{s}, a\alpha) = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}(\boldsymbol{s},a), \alpha), \end{array} \right.\]

where \(\varepsilon\) denotes the empty sequence and \(\alpha \in \{1,2,\ldots,n\}^*\) is a sequence of indices. \(\tag*{◻}\)

Throughout this paper, the dimension of a vector is \(n\).

Example 2: Let \(\boldsymbol{s} = [1, 4, 8, 9]\). \(\boldsymbol{\varPhi}(\boldsymbol{s}, 1) = [\lfloor 1/2 \rfloor, \lceil 4/2 \rceil, \lceil 8/2 \rceil, \lceil 9/2 \rceil] = [0, 2, 4, 5]\), \(\boldsymbol{\varPhi}(\boldsymbol{s}, 2) = [\lceil 1/2 \rceil, \lfloor 4/2 \rfloor, \lceil 8/2 \rceil, \lceil 9/2 \rceil] = [1, 2, 4, 5]\), \(\boldsymbol{\varPhi}(\boldsymbol{s}, 3) = [\lceil 1/2 \rceil, \lceil 4/2 \rceil, \lfloor 8/2 \rfloor, \lceil 9/2 \rceil] = [1, 2, 4, 5]\), \(\boldsymbol{\varPhi}(\boldsymbol{s}, 4) = [\lceil 1/2 \rceil, \lceil 4/2 \rceil, \lceil 8/2 \rceil, \lfloor 9/2 \rfloor] = [1, 2, 4, 4]\). Let \(\boldsymbol{s} = [1, 4, 8, 9]\) and the sequence of indices \(\alpha = 1;4;2;3;4\). \(\boldsymbol{\varPhi}(\boldsymbol{s}, 1;4;2;3;4) = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}([1,4,8,9], 1), 4;2;3;4) = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}([0,2,4,5], 4), 2;3;4) = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}([0,1,2,2], 2), 3;4) = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}([0,0,1,1], 3), 4) = \boldsymbol{\varPhi}([0,0,0,1], 4) = [0,0,0,0]\). \(\tag*{◻}\)

Definition 5: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\sigma\text{$-$}lb(\boldsymbol{s})\) is defined as

\[\sigma\text{$-$}lb(\boldsymbol{s}) = \min\{|\alpha| \mid \alpha \in \{1,2,\ldots,n\}^*, \;\; \boldsymbol{\varPhi}(\boldsymbol{s},\alpha) = \boldsymbol{0} \},\]

where \(|\alpha|\) denotes the length of the index sequence \(\alpha\), and \(\boldsymbol{0}\) denotes the zero vector \([0,0,\ldots,0]\). \(\tag*{◻}\)

\(\sigma\text{$-$}lb(\boldsymbol{s})\) represents the minimum number of application times of \(\boldsymbol{\varPhi}\) to transform a given vector \(\boldsymbol{s}\) into \(\boldsymbol{0}\). Since the result of \(\boldsymbol{\varPhi}\) varies according to the index \(a\) provided as its second argument, many patterns of index sequences are searched to obtain \(\sigma\text{$-$}lb(\boldsymbol{s})\). This process is computationally intensive, leading to a time complexity of \(\mathcal{O}(n^{cn})\), where \(c\) is a constant. In this paper, we introduce a simpler version of \(\boldsymbol{\varPhi}\), denoted as \(\tilde{\boldsymbol{\varPhi}}\), in order to estimate \(\sigma\text{$-$}lb(\boldsymbol{s})\) with quick computation.

Definition 6: Suppose that \(\boldsymbol{s}\) is a vector \([s_1, s_2, \ldots, s_n] \in \mathbb{N}_0^{n}\). \(\iota(\boldsymbol{s})\) denotes the minimum index \(i\) in \(\{1,2,\ldots,n\}\) such that \(s_i=1\):

\[\iota(\boldsymbol{s}) = \left\{ \begin{array}{lr@{}} 0 \hspace{5.75em} (s_i \neq 1\ \text{for all}\ i \in \{1, 2, \ldots, n\}) \\ {\min\{i \mid s_i=1,\, i \in \{1, 2, \ldots, n\}\} \ \ \ \text{(otherwise)}} \end{array} \right.\]

Note that \(\iota(\boldsymbol{s})=0\) if there are no 1’s in the elements of \(\boldsymbol{s}\).

The function \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) = [s'_1, s'_2, \ldots, s'_n]\) is defined as follows.

\[s'_i = \left\{ \begin{array}{ll} 0 & \mbox{($s_i=1$ and $i=\iota(\boldsymbol{s})$)} \\ 1 & \mbox{($s_i=1$ and $i \neq \iota(\boldsymbol{s})$)} \\ \lfloor s_i/2 \rfloor & \mbox{(otherwise)} \end{array} \right.\]

\(\tag*{◻}\)

For a given vector \(\boldsymbol{s}\), the output of \(\boldsymbol{\varPhi}(\boldsymbol{s}, a)\) varies based on the chosen index \(a\). In contrast, \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})\) consistently produces a unique vector. Hence, \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})\) is simpler in its functionality. Utilizing \(\tilde{\boldsymbol{\varPhi}}\), we define a function analogous to \(\sigma\text{$-$}lb\).

Definition 7: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\tilde{\sigma}(\boldsymbol{s})\) is defined as follows.

\[\tilde{\sigma}(\boldsymbol{s}) = \left\{ \begin{array}{ll} 0 & \mbox{($\boldsymbol{s}=\boldsymbol{0}$)} \\ \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}))+1 & \mbox{(otherwise)} \end{array} \right.\]

\(\tag*{◻}\)

In other words, \(\tilde{\sigma}(\boldsymbol{s})\) is defined by the number of applications of \(\tilde{\boldsymbol{\varPhi}}\) required until the nested application of \(\tilde{\boldsymbol{\varPhi}}(\tilde{\boldsymbol{\varPhi}}(\cdots \tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) \cdots ))\) reaches \(\boldsymbol{0}\) for the first time.

Example 3: Let \(\boldsymbol{s}=[1,4,8,9]\). \(\tilde{\sigma}(\boldsymbol{s})= \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}([1,4,8,9]))+1 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}([0,2,4,4]))+2 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}([0,1,2,2]))+3 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}([0,0,1,1]))+4 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}([0,0,0,1]))+5 = \tilde{\sigma}([0,0,0,0])+5 = 5\). \(\tag*{◻}\)

In the next two sections, we show that \(\sigma\text{$-$}lb\) can be approximated by using \(\tilde{\sigma}\). Specifically, we give the upper and lower bounds on \(\sigma\text{$-$}lb\) in terms of \(\tilde{\sigma}\). With these bounds, we prove that the value of \(\tilde{\sigma}\) is theoretically almost equivalent to \(\sigma\text{$-$}lb\).

3.  Lower Bound on \(\sigma\text{$-$}lb\)

In this section, we compare \(\tilde{\sigma}\) and \(\sigma\text{$-$}lb\), and then prove that \(\tilde{\sigma}\) is a lower bound on \(\sigma\text{$-$}lb\). This result confirms that \(\tilde{\sigma}\) is also a lower bound on the GC of reversible circuits.

Definition 8: For two vectors \(\boldsymbol{s}=[s_1, s_2, \ldots, s_n]\) and \(\boldsymbol{s}'=[s'_1, s'_2, \ldots, s'_n]\), we say \(\boldsymbol{s} \le \boldsymbol{s}'\) if \(s_i \le s'_i\) for all \(i \in \{1, 2, \ldots, n\}\). Likewise, we say \(\boldsymbol{s} \ge \boldsymbol{s}'\) if \(s_i \ge s'_i\) for all \(i \in \{1, 2, \ldots, n\}\). \(\tag*{◻}\)

By the definitions of \(\tilde{\sigma}\) and \(\sigma\text{$-$}lb\), we have the following proposition.

Proposition 2: Suppose that \(\boldsymbol{s}\) and \(\boldsymbol{s}'\) are vectors in \(\mathbb{N}_0^{n}\), and “\(\asymp\)” is one of the following relations: “\(=\),” “\(\le\),” and “\(\ge\)”. If \(\boldsymbol{s} \asymp \boldsymbol{s}'\), then \(\tilde{\sigma}(\boldsymbol{s}) \asymp \tilde{\sigma}(\boldsymbol{s}')\) and \(\sigma\text{$-$}lb(\boldsymbol{s}) \asymp \sigma\text{$-$}lb(\boldsymbol{s}')\). \(\tag*{◻}\)

Definition 9: Let \(\boldsymbol{s}=[s_1, s_2, \ldots, s_n]\) and \(\boldsymbol{s}'=[s'_1, s'_2, \ldots, s'_n]\) be vectors in \(\mathbb{N}_0^{n}\). Let \(\pi\) be a permutation of the set \(\{1,2,\ldots,n\}\). If there exists a permutation \(\pi\) such that \(s_{\pi(i)} = s'_{i}\) for all \(i \in \{1,2,\ldots,n\}\), then \(\boldsymbol{s}\) is P-equivalent to \(\boldsymbol{s}'\), which is denoted by \(\boldsymbol{s} \sim \boldsymbol{s}'\). \(\tag*{◻}\)

Proposition 3: Let \(\boldsymbol{s}\) and \(\boldsymbol{s}'\) be vectors in \(\mathbb{N}_0^{n}\). If \(\boldsymbol{s} \sim \boldsymbol{s}'\), then \(\tilde{\sigma}(\boldsymbol{s}) = \tilde{\sigma}(\boldsymbol{s}')\) and \(\sigma\text{$-$}lb(\boldsymbol{s}) = \sigma\text{$-$}lb(\boldsymbol{s}')\). \(\tag*{◻}\)

Lemma 1: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\) and an index \(a\), \(\tilde{\sigma}(\boldsymbol{\varPhi}(\boldsymbol{s},a)) \ge \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}))\). \(\tag*{◻}\)

Proof. Suppose that \(\boldsymbol{s}=[s_1,s_2,\ldots,s_n]\), \(\boldsymbol{s}' = \boldsymbol{\varPhi}(\boldsymbol{s},a) = [s'_1,s'_2,\ldots,s'_n]\), and \(\tilde{\boldsymbol{s}} = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) = [\tilde{s}_1,\tilde{s}_2,\ldots,\tilde{s}_n]\).

Let us consider the case of \(\iota(\boldsymbol{s})=0\). There are no elements \(s_i\) such that \(s_i = 1\). Then, \(s'_i \ge \tilde{s}_i\) for all \(i \in \{1, 2, \ldots, n\}\) since \(\lceil s_i/2 \rceil \ge \lfloor s_i/2 \rfloor\). Hence, \(\boldsymbol{s}' \ge \tilde{\boldsymbol{s}}\), and therefore \(\tilde{\sigma}(\boldsymbol{s}') \ge \tilde{\sigma}(\tilde{\boldsymbol{s}})\) by Proposition 2.

Below, we assume that \(\iota(\boldsymbol{s}) \neq 0\). Let \(b=\iota(\boldsymbol{s})\). \(b\) may be equal to \(a\). For all \(i \in \{1, 2, \ldots, n\} \setminus \{a, b\}\), \(s'_i \ge \tilde{s}_i\) since \(s'_i = \lceil s_i/2 \rceil =1=\tilde{s}_i\) if \(s_i=1\), and \(s'_i = \lceil s_i/2 \rceil \ge \lfloor s_i/2 \rfloor = \tilde{s}_i\) otherwise. For \(i=b\), \(\tilde{s}_b=0\) by the definition of \(\tilde{\boldsymbol{\varPhi}}\). Then, \(s'_b \ge \tilde{s}_b\) since \(s'_b\) is non-negative: \(s'_b \ge 0 = \tilde{s}_b\). From the above argument, we have proven that \(s'_i \ge \tilde{s}_i\) for all \(i \in \{1, 2, \ldots, n\} \setminus \{a\}\). The remaining work to conclude \(\boldsymbol{s}' \ge \tilde{\boldsymbol{s}}\) is to compare \(s'_a\) and \(\tilde{s}_a\).

(Case of \(a = b\)): Since \(s'_b \ge \tilde{s}_b\), we have \(s'_a \ge \tilde{s}_a\). Hence, \(s'_i \ge \tilde{s}_i\) for all \(i \in \{1, 2, \ldots, n\}\). Since \(\boldsymbol{s}' \ge \tilde{\boldsymbol{s}}\), we have \(\tilde{\sigma}(\boldsymbol{s}') \ge \tilde{\sigma}(\tilde{\boldsymbol{s}})\) by Proposition 2.

(Case of \(s_a \neq 1\) and \(a \neq b\)): By the definitions of \(\boldsymbol{\varPhi}\) and \(\tilde{\boldsymbol{\varPhi}}\), \(s'_a = \lfloor s_a/2 \rfloor = \tilde{s}_a\). Hence, \(s'_i \ge \tilde{s}_i\) for all \(i \in \{1, 2, \ldots, n\}\). Since \(\boldsymbol{s}' \ge \tilde{\boldsymbol{s}}\), we have \(\tilde{\sigma}(\boldsymbol{s}') \ge \tilde{\sigma}(\tilde{\boldsymbol{s}})\) by Proposition 2.

(Case of \(s_a=1\) and \(a \neq b\)): By the definitions of \(\boldsymbol{\varPhi}\) and \(\tilde{\boldsymbol{\varPhi}}\), \(s'_a = \lfloor 1/2 \rfloor=0\) and \(\tilde{s}_a = 1\) while \(s'_b = \lceil 1/2 \rceil=1\) and \(\tilde{s}_b = 0\). Let \(\boldsymbol{s}''\) be the vector obtained by swapping \(s'_a\) and \(s'_b\) in \(\boldsymbol{s}'\). Then, \(\boldsymbol{s}'' \ge \tilde{\boldsymbol{s}}\), and therefore \(\tilde{\sigma}(\boldsymbol{s}'') \ge \tilde{\sigma}(\tilde{\boldsymbol{s}})\) by Proposition 2. Since \(\boldsymbol{s}' \sim \boldsymbol{s}''\), \(\tilde{\sigma}(\boldsymbol{s}') = \tilde{\sigma}(\boldsymbol{s}'')\) by Proposition 3. Thus, we have \(\tilde{\sigma}(\boldsymbol{s}') = \tilde{\sigma}(\boldsymbol{s}'') \ge \tilde{\sigma}(\tilde{\boldsymbol{s}})\).\(\tag*{◻}\)

The next proposition follows immediately from Definition 7. This will be used in the proofs of Lemma 2 and some lemmas in the later sections.

Proposition 4: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n} \setminus \{\boldsymbol{0}\}\), \(\tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \tilde{\sigma}(\boldsymbol{s}) - 1\). \(\tag*{◻}\)

Lemma 2: Let \(\boldsymbol{s} \in \mathbb{N}_0^{n}\) and \(\alpha \in \{1,2,\ldots,n\}^*\). If \(\boldsymbol{\varPhi}(\boldsymbol{s}, \alpha) = \boldsymbol{0}\), then \(|\alpha| \ge \tilde{\sigma}(\boldsymbol{s})\). \(\tag*{◻}\)

Proof. The proof is by the mathematical induction on the length of \(\alpha\). If \(\boldsymbol{\varPhi}(\boldsymbol{s}, \varepsilon) = \boldsymbol{0}\), then \(\boldsymbol{s}=\boldsymbol{0}\), and therefore \(\tilde{\sigma}(\boldsymbol{s})=0\). Thus, the lemma holds for \(|\alpha| = 0\).

Assume that the lemma holds for \(|\alpha'| = k\), that is, if \(\boldsymbol{\varPhi}(\boldsymbol{s}', \alpha') = \boldsymbol{0}\) holds for a vector \(\boldsymbol{s}'\) in \(\mathbb{N}_0^{n}\) and an index sequence \(\alpha'\) such that \(|\alpha'| = k\), then \(|\alpha'| = k \ge \tilde{\sigma}(\boldsymbol{s}')\). Using this assumption, we prove the lemma for \(|\alpha| = k+1\). Suppose that \(\boldsymbol{s}\) is a vector in \(\mathbb{N}_0^{n}\) and \(\alpha\) is an index sequence with a length of \(k+1\) (\(|\alpha| = k+1\)). Then, \(\alpha\) can be written in the concatenation of certain \(a\) and \(\alpha'\) as \(\alpha = a\alpha'\), where \(a \in \{1,2,\ldots,n\}\) and \(|\alpha'|=k\). Let \(\boldsymbol{s}'\) be \(\boldsymbol{\varPhi}(\boldsymbol{s},a)\). If \(\boldsymbol{\varPhi}(\boldsymbol{s}, a\alpha') = \boldsymbol{0}\), then we have \(\boldsymbol{\varPhi}(\boldsymbol{s}, a\alpha') = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}(\boldsymbol{s},a), \alpha') = \boldsymbol{\varPhi}(\boldsymbol{s}',\alpha') = \boldsymbol{0}\) by the definition of \(\boldsymbol{\varPhi}\). By using the induction hypothesis, \(k \ge \tilde{\sigma}(\boldsymbol{s}')\) holds, and therefore \(|\alpha|= k+1 \ge \tilde{\sigma}(\boldsymbol{s}')+1\). By Lemma 1 and Proposition 4, \(\tilde{\sigma}(\boldsymbol{s}') \ge \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \tilde{\sigma}(\boldsymbol{s})-1\). Then, we have \(|\alpha| \ge \tilde{\sigma}(\boldsymbol{s}')+1 \ge \tilde{\sigma}(\boldsymbol{s})-1 +1 = \tilde{\sigma}(\boldsymbol{s})\). Thus, the inductive step was proved.\(\tag*{◻}\)

Theorem 2: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\),

\[\sigma\text{$-$}lb(\boldsymbol{s}) \ge \tilde{\sigma}(\boldsymbol{s})\]

holds. \(\tag*{◻}\)

Proof. By the definition of \(\sigma\text{$-$}lb\), there exists a sequence \(\alpha\) such that \(\boldsymbol{\varPhi}(\boldsymbol{s}, \alpha) = \boldsymbol{0}\) and \(|\alpha| = \sigma\text{$-$}lb(\boldsymbol{s})\). Then, \(|\alpha| \ge \tilde{\sigma}(\boldsymbol{s})\) holds by Lemma 2. Thus, we have \(\sigma\text{$-$}lb(\boldsymbol{s}) = |\alpha| \ge \tilde{\sigma}(\boldsymbol{s})\).\(\tag*{◻}\)

Theorem 2 shows that \(\tilde{\sigma}\) is a lower bound on \(\sigma\text{$-$}lb\). By Theorems 1 and 2, we can see that \(\tilde{\sigma}\) is also a lower bound on the GC of a circuit of a reversible function. This fact is expressed as Theorem 3 below.

Theorem 3: For any reversible function \(F\),

\[\gamma(F) \ge \tilde{\sigma}(\boldsymbol{\varLambda}(F))\]

holds. \(\tag*{◻}\)

Example 4: As we have seen in Example 1, the characteristic vector of the reversible function \(F\) in Fig. 1 is \(\boldsymbol{\varLambda}(F)=[1,4,8,9]\). In Example 3, we obtained \(\tilde{\sigma}([1,4,8,9])=5\). Thus, \(\gamma(F) \ge 5\) follows from Theorem 3, implying that five or more gates are required to realize \(F\). Meanwhile, the circuit in Fig. 1 is realized by five gates. In this case, we can conclude that Fig. 1 is the exact minimum circuit of \(F\) and that \(\gamma(F)=5\). \(\tag*{◻}\)

4.  Upper Bound on \(\sigma\text{$-$}lb\)

In this section, we discuss the proximity of \(\tilde{\sigma}\) to \(\sigma\text{$-$}lb\), by providing an upper bound on \(\sigma\text{$-$}lb\) in terms of \(\tilde{\sigma}\).

Definition 10: We call a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\) a power-of-two vector if every element of \(\boldsymbol{s}\) is 0 or a power of two: \(2^0, 2^1, 2^2, \cdots\). A power-of-two vector except \(\boldsymbol{0}\) (the zero vector) is called a non-zero power-of-two vector. \(\tag*{◻}\)

Example 5: Let \(\boldsymbol{s}_0 = [0, 0, 0, 0]\), \(\boldsymbol{s}_1 = [2, 1, 4, 0] = [2^1, 2^0, 2^2, 0]\). \(\boldsymbol{s}_0\) and \(\boldsymbol{s}_1\) are power-of-two vectors. \(\boldsymbol{s}_1\) is a non-zero power-of-two vector.

Lemma 3: If \(\boldsymbol{r}\) is a power-of-two vector and \(a\) is an index, then \(\boldsymbol{\varPhi}(\boldsymbol{r},a)\) is a power-of-two vector. \(\tag*{◻}\)

Proof. Let \(\boldsymbol{r}' = \boldsymbol{\varPhi}(\boldsymbol{r}, a) = [r'_1,r'_2,\ldots,r'_n]\). \(\lceil r_i/2 \rceil = \lfloor r_i/2 \rfloor = r_i/2\) if \(r_i\) is even. Since \(\boldsymbol{r}\) is a power-of-two vector, a possible odd number in \(\boldsymbol{r}\) is 1 only. Therefore, we have the following equation by the definition of \(\boldsymbol{\varPhi}\).

\[r'_i = \left\{ \begin{array}{ll} 0 & \mbox{($r_i = 1$ and $i=a$)} \\ 1 & \mbox{($r_i = 1$ and $i \neq a$)} \\ r_i/2 & \mbox{(otherwise)} \end{array} \right.\]

From this equation, we see that (i) if \(r_i = 0\), then \(r'_i=r_i/2=0\), (ii) if \(r_i = 1\), then \(r'_i\) is 0 or 1 (\(=2^0\)), and (iii) if \(r_i \in \{ 2^1, 2^2, \ldots \}\), then \(r'_i=r_i/2\) is a power of two. Since every \(r'_i\) is 0 or a power of two, \(\boldsymbol{r}'\) is a power-of-two vector.\(\tag*{◻}\)

Lemma 4: Let \(\boldsymbol{r}\) be a power-of-two vector. There exists an index \(a\) such that \(\boldsymbol{\varPhi}(\boldsymbol{r}, a) = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{r})\). \(\tag*{◻}\)

Proof. Suppose that \(\boldsymbol{r} = [r_1,r_2,\ldots,r_n]\), \(\boldsymbol{r}' = \boldsymbol{\varPhi}(\boldsymbol{r},a) = [r'_1,r'_2,\ldots,r'_n]\), and \(\tilde{\boldsymbol{r}} = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{r}) = [\tilde{r}_1,\tilde{r}_2,\ldots,\tilde{r}_n]\). From the proof of Lemma 3, the following equation holds.

\[r'_i = \left\{ \begin{array}{ll} 0 & \mbox{($r_i = 1$ and $i=a$)} \\ 1 & \mbox{($r_i = 1$ and $i \neq a$)} \\ r_i/2 & \mbox{(otherwise)} \end{array} \right.\]

Similarly, the following equation holds by the definition of \(\tilde{\boldsymbol{\varPhi}}\).

\[\tilde{r}_i = \left\{ \begin{array}{ll} 0 & \mbox{($r_i = 1$ and $i = \iota(\boldsymbol{r})$)} \\ 1 & \mbox{($r_i = 1$ and $i \neq \iota(\boldsymbol{r})$)} \\ r_i/2 & \mbox{(otherwise)} \end{array} \right.\]

(Case of \(\iota(\boldsymbol{r})=0\)): In this case, there are no elements \(r_i\) such that \(r_i = 1\). Then, \(r'_i = r_i/2 = \tilde{r}_i\) for all \(i \in \{1, 2, \ldots, n \}\). Thus, \(\boldsymbol{r}' = \tilde{\boldsymbol{r}}\). The lemma holds for an arbitrary \(a\).

(Case of \(\iota(\boldsymbol{r}) \neq 0\)): By choosing \(\iota(\boldsymbol{r})\) as \(a\), we have \(r'_i = \tilde{r}_i\) for all \(i \in \{1, 2, \ldots, n \}\). Thus, \(\boldsymbol{r}' = \tilde{\boldsymbol{r}}\).\(\tag*{◻}\)

Lemma 5: Let \(\boldsymbol{r}\) be a non-zero power-of-two vector. There exists an index \(a\) such that \(\tilde{\sigma}(\boldsymbol{\varPhi}(\boldsymbol{r}, a)) = \tilde{\sigma}(\boldsymbol{r})-1\). \(\tag*{◻}\)

Proof. By Lemma 4 and Proposition 4, there exists an index \(a\) such that \(\tilde{\sigma}(\boldsymbol{\varPhi}(\boldsymbol{r}, a)) = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{r})) = \tilde{\sigma}(\boldsymbol{r})-1\).\(\tag*{◻}\)

Lemma 6: For a power-of-two vector \(\boldsymbol{r}\), \(\sigma\text{$-$}lb(\boldsymbol{r}) = \tilde{\sigma}(\boldsymbol{r})\). \(\tag*{◻}\)

Proof. Since \(\sigma\text{$-$}lb(\boldsymbol{r}) \ge \tilde{\sigma}(\boldsymbol{r})\) holds by Theorem 2, we will prove that

\[\begin{equation*} \sigma\text{$-$}lb(\boldsymbol{r}) \le \tilde{\sigma}(\boldsymbol{r}) \tag{2} \end{equation*}\]

by the mathematical induction on \(\tilde{\sigma}(\boldsymbol{r})\).

If \(\tilde{\sigma}(\boldsymbol{r}) = 0\), then \(\boldsymbol{r} = \boldsymbol{0}\), and therefore \(\sigma\text{$-$}lb(\boldsymbol{r})=0\). Thus, Eq. (2) holds for \(\tilde{\sigma}(\boldsymbol{r}) = 0\).

Assume that Eq. (2) holds for any power-of-two vector \(\boldsymbol{r}'\) such that \(\tilde{\sigma}(\boldsymbol{r}') = k\), i.e., \(\sigma\text{$-$}lb(\boldsymbol{r}') \le \tilde{\sigma}(\boldsymbol{r}') = k\). Then, by the definition of \(\sigma\text{$-$}lb\), there exists an index sequence \(\alpha'\) such that \(|\alpha'| = k\) and \(\boldsymbol{\varPhi}(\boldsymbol{r}', \alpha') = \boldsymbol{0}\). Using this assumption, we prove Eq. (2) for \(\tilde{\sigma}(\boldsymbol{r}) = k+1\). Suppose that \(\boldsymbol{r}=[r_1,r_2,\ldots,r_n]\) is a non-zero power-of-two vector such that \(\tilde{\sigma}(\boldsymbol{r}) = k+1\). By Lemma 3, \(\boldsymbol{\varPhi}(\boldsymbol{r}, a)\) is a power-of-two vector. Then, let \(\boldsymbol{r}' = \boldsymbol{\varPhi}(\boldsymbol{r}, a)\), where \(a\) is the index in Lemma 5. By Lemma 5, \(\tilde{\sigma}(\boldsymbol{r}') = \tilde{\sigma}(\boldsymbol{r}) -1 = (k+1)-1 = k\). By using the induction hypothesis, there exists an index sequence \(\alpha'\) such that \(|\alpha'| = k\) and \(\boldsymbol{\varPhi}(\boldsymbol{r}', \alpha') = \boldsymbol{0}\). Then, \(\boldsymbol{0} = \boldsymbol{\varPhi}(\boldsymbol{r}', \alpha') = \boldsymbol{\varPhi}(\boldsymbol{\varPhi}(\boldsymbol{r}, a), \alpha') = \boldsymbol{\varPhi}(\boldsymbol{r}, a\alpha')\) by the definition of \(\boldsymbol{\varPhi}\). Since \(|\alpha'| = k\), we have \(|a\alpha'| = k+1\). By the definition of \(\sigma\text{$-$}lb\), \(\sigma\text{$-$}lb(\boldsymbol{r}) \le |a\alpha'| = k+1 = \tilde{\sigma}(\boldsymbol{r})\). Thus, the inductive step was proved.\(\tag*{◻}\)

Definition 11: Suppose that \(\boldsymbol{s}\) is a vector \([s_1, s_2, \ldots, s_n] \in \mathbb{N}_0^{n}\). The function \(\boldsymbol{R}(\boldsymbol{s}) = [r_1, r_2, \ldots, r_n]\) is defined as follows, where \(L(s_i)\) denotes the bit length of the binary representation of \(s_i\), i.e., \(L(s_i) = \lceil \log_2(s_i+1) \rceil\).

\[r_i = \left\{ \begin{array}{ll} 0 & \mbox{($s_i = 0$)} \\ s_i & \mbox{($s_i$ is a power of 2: $2^0, 2^1, 2^2, \ldots$ )} \\ 2^{L(s_i)} & \mbox{(otherwise)} \end{array} \right.\]

\(\tag*{◻}\)

Example 6: Let \(\boldsymbol{s} = [1, 0, 2, 5]\). \(\boldsymbol{R}(\boldsymbol{s}) = [1, 0, 2, 8]\).

\(\boldsymbol{R}(\boldsymbol{s})\) rounds up all \(s_i \neq 0\) to the power of two. Therefore, we have the following proposition.

Proposition 5: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\boldsymbol{R}(\boldsymbol{s})\) is a power-of-two vector. \(\tag*{◻}\)

Theorem 4: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\),

\[\sigma\text{$-$}lb(\boldsymbol{s}) \le \tilde{\sigma}(\boldsymbol{R}(\boldsymbol{s}))\]

holds. \(\tag*{◻}\)

Proof. Let \(\boldsymbol{r} = \boldsymbol{R}(\boldsymbol{s})\). Since \(\boldsymbol{s} \le \boldsymbol{r}\) by the definition of \(\boldsymbol{R}\), \(\sigma\text{$-$}lb(\boldsymbol{s}) \le \sigma\text{$-$}lb(\boldsymbol{r})\) by Proposition 2. By Proposition 5, \(\boldsymbol{r}\) is a power-of-two vector. Then, \(\sigma\text{$-$}lb(\boldsymbol{r}) = \tilde{\sigma}(\boldsymbol{r})\) by Lemma 6. Thus, we have \(\sigma\text{$-$}lb(\boldsymbol{s}) \le \sigma\text{$-$}lb(\boldsymbol{r}) = \tilde{\sigma}(\boldsymbol{r})\).\(\tag*{◻}\)

Theorem 4 gives an upper bound on \(\sigma\text{$-$}lb\) in terms of \(\tilde{\sigma}\).

Using the bounds in Theorems 2 and 4, we evaluate the proximity of \(\tilde{\sigma}\) to \(\sigma\text{$-$}lb\). The result will be given as Theorem 5.

Lemma 7: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{R}(\boldsymbol{s})) \le \boldsymbol{s}\). \(\tag*{◻}\)

Proof. Suppose that \([s_1,s_2,\ldots,s_n]=\boldsymbol{s}\), \(\boldsymbol{r} = \boldsymbol{R}(\boldsymbol{s}) =[r_1,r_2,\ldots,r_n]\), and \(\tilde{\boldsymbol{r}} = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{r}) = [\tilde{r}_1,\tilde{r}_2,\ldots,\tilde{r}_n]\). By the definition of \(\boldsymbol{R}\), the following equation holds.

\[r_i = \left\{ \begin{array}{ll} 0 & \mbox{($s_i = 0$)} \\ 1 & \mbox{($s_i = 1$)} \\ s_i & \mbox{($s_i \ge 2$ and $s_i$ is a power of 2)} \\ 2^{L(s_i)} & \mbox{(otherwise)} \end{array} \right.\]

Since \(\boldsymbol{r}\) is a power-of-two vector by Proposition 5, we have the following equation from the above equation and the definition of \(\tilde{\boldsymbol{\varPhi}}\).

\[\tilde{r}_i = \left\{ \begin{array}{ll} 0 & \mbox{($s_i=0$)} \\ 0 & \mbox{($s_i=1$ and $i=\iota(\boldsymbol{s})$)} \\ 1 & \mbox{($s_i=1$ and $i \neq \iota(\boldsymbol{s})$)} \\ s_i/2 & \mbox{($s_i \ge 2$ and $s_i$ is a power of 2)}\\ 2^{L(s_i)-1} & \mbox{(otherwise)} \end{array} \right.\]

It can be observed that \(\tilde{r}_i \le s_i\) holds for all the cases above. Thus, \(\tilde{\boldsymbol{r}} \le \boldsymbol{s}\).\(\tag*{◻}\)

Lemma 8: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\tilde{\sigma}(\boldsymbol{R}(\boldsymbol{s})) \le \tilde{\sigma}(\boldsymbol{s})+1\). \(\tag*{◻}\)

Proof. The lemma clearly holds for \(\boldsymbol{s}=\boldsymbol{0}\). In the following, we prove the lemma under the assumption of \(\boldsymbol{s} \neq \boldsymbol{0}\). Let \(\boldsymbol{r} = \boldsymbol{R}(\boldsymbol{s})\). By Proposition 4, \(\tilde{\sigma}(\boldsymbol{r}) -1 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{r}))\). By Lemma 7 and Proposition 2, \(\tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{r})) \le \tilde{\sigma}(\boldsymbol{s})\). Thus, we have \(\tilde{\sigma}(\boldsymbol{r}) -1 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{r})) \le \tilde{\sigma}(\boldsymbol{s})\).\(\tag*{◻}\)

Theorem 5: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\),

\[\tilde{\sigma}(\boldsymbol{s}) \le \sigma\text{$-$}lb(\boldsymbol{s}) \le \tilde{\sigma}(\boldsymbol{s})+1\]

holds. \(\tag*{◻}\)

Proof. \(\tilde{\sigma}(\boldsymbol{s}) \le \sigma\text{$-$}lb(\boldsymbol{s})\) by Theorem 2. Meanwhile, \(\sigma\text{$-$}lb(\boldsymbol{s}) \le \tilde{\sigma}(\boldsymbol{R}(\boldsymbol{s})) \le \tilde{\sigma}(\boldsymbol{s})+1\) by Theorem 4 and Lemma 8. Thus, we have the theorem.\(\tag*{◻}\)

Theorem 5 guarantees that the maximum difference between \(\tilde{\sigma}(\boldsymbol{s})\) and \(\sigma\text{$-$}lb(\boldsymbol{s})\) is only one. This indicates that \(\tilde{\sigma}(\boldsymbol{s})\) closely approximates \(\sigma\text{$-$}lb(\boldsymbol{s})\).

5.  Quick Calculation of \(\tilde{\sigma}\)

In this section, a quick calculation of \(\tilde{\sigma}(\boldsymbol{\varLambda}(F))\) is discussed. For an \(n\)-variable reversible function \(F\), the dimension of \(\boldsymbol{\varLambda}(F)\) is \(n\) by Definition 2, and the elements in \(\boldsymbol{\varLambda}(F)\) are bounded by \(2^n -1\) by Proposition 1. Since \(\tilde{\boldsymbol{\varPhi}}\) halves the elements of a vector, \(\tilde{\sigma}(\boldsymbol{\varLambda}(F))\) can be determined by applying \(\tilde{\boldsymbol{\varPhi}}\) at most \(c n\) times, where \(c\) is a certain constant. Moreover, the complexity of \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})\) is \(\mathcal{O}(n)\) by Definition 6. Hence, the time complexity of the straightforward computation of \(\tilde{\sigma}(\boldsymbol{\varLambda}(F))\) results in \(\mathcal{O}(n^2)\). To improve this, we propose a quick calculation of \(\tilde{\sigma}\) based on some arithmetic functions for the bit length. This optimized version achieves a time complexity of \(\mathcal{O}(n)\).

According to Definition 7, \(\tilde{\sigma}(\boldsymbol{s})\) denotes the number of necessary applications of \(\tilde{\boldsymbol{\varPhi}}\) in the nested application of \(\tilde{\boldsymbol{\varPhi}}(\tilde{\boldsymbol{\varPhi}}(\cdots \tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) \cdots ))\) for the conversion from \(\boldsymbol{s}\) to \(\boldsymbol{0}\). Interpreting non-negative integers in binary representation, we can regarded the division \(\lfloor s_i/2 \rfloor\) in \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})\) as a right-shift operation. Therefore, the value of \(\tilde{\sigma}(\boldsymbol{s})\) depends on the bit length of the elements in \(\boldsymbol{s}\). Utilizing this insight, we propose a method to quickly compute the value of \(\tilde{\sigma}(\boldsymbol{s})\) based on arithmetic functions related to the bit length.

Definition 12: For a vector \(\boldsymbol{s} = [s_1,s_2,\ldots,s_n] \in \mathbb{N}_0^{n}\), we define \(L_{max}(\boldsymbol{s}) = \max\{ L(s_i) \mid 1 \le i \le n \}\), which is the maximum bit length of \(s_i\) in \(\boldsymbol{s}\). \(\#_d(\boldsymbol{s})\) is defined by the number of elements \(s_i\) whose bit length is \(d\) or more:

\[\#_d(\boldsymbol{s}) = |\{i \mid \mbox{$1 \le i \le n$, $L(s_i) \ge d$}\}|.\]

\(\tag*{◻}\)

Note that \(\#_0(\boldsymbol{s}) = n\) and \(\#_d(\boldsymbol{s}) = 0\) for \(d > L_{max}(\boldsymbol{s})\).

Definition 13: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\), \(\kappa(\boldsymbol{s})\) is defined as follows.

\[\begin{aligned} & \kappa_d(\boldsymbol{s}) = (d-1) + \#_d(\boldsymbol{s})\\ & \kappa(\boldsymbol{s}) = \left\{ \begin{array}{lr} 0 & \mbox{($\boldsymbol{s}=\boldsymbol{0}$)} \\ \max\{ \kappa_d(\boldsymbol{s}) \mid 1 \le d \le L_{max}(\boldsymbol{s}) \} & \\ & {(otherwise)} \end{array} \right. \end{aligned}\]

\(\tag*{◻}\)

Example 7: Let \(\boldsymbol{s}=[1,4,8,9]\). \(\kappa_1(\boldsymbol{s}) = (1-1) + \#_1(\boldsymbol{s}) = 0+4 =4\), \(\kappa_2(\boldsymbol{s}) = (2-1) + \#_2(\boldsymbol{s}) = 1+3 =4\), \(\kappa_3(\boldsymbol{s}) = (3-1) + \#_3(\boldsymbol{s}) = 2+3 =5\), \(\kappa_4(\boldsymbol{s}) = (4-1) + \#_4(\boldsymbol{s}) = 3+2 =5\). Then, \(\kappa(\boldsymbol{s}) =5\). \(\tag*{◻}\)

\(\kappa\) defined above is a faster version of \(\tilde{\sigma}\). Their computational processes look quite different. Nevertheless, both \(\kappa(\boldsymbol{s})\) and \(\tilde{\sigma}(\boldsymbol{s})\) produce the same value for an arbitrary vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\). In the rest of this section, \(\kappa(\boldsymbol{s}) = \tilde{\sigma}(\boldsymbol{s})\) will be proved and then an algorithm for \(\kappa(\boldsymbol{s})\) with a complexity of \(\mathcal{O}(n)\) will be presented.

The definition of \(\kappa\) is more complex than a plain evaluation of the bit length of the elements in \(\boldsymbol{s}\). This is because \(\tilde{\boldsymbol{\varPhi}}\) used in \(\tilde{\sigma}\) has cases other than the right-shift operation. In order to conclude that \(\kappa(\boldsymbol{s}) = \tilde{\sigma}(\boldsymbol{s})\), we need to analyze all the cases of \(\tilde{\boldsymbol{\varPhi}}\) carefully. The analysis will be made in the proof of Lemma 11, by utilizing Lemmas 9 and 10.

Lemma 9: Suppose that \(\boldsymbol{s}\) and \(\boldsymbol{s}'\) are vectors in \(\mathbb{N}_0^{n}\), \(d\) and \(d'\) are positive integers, \(c\) is a constant, and ‘\(\asymp\)’ is one of the following relations: ‘\(=\)’, ‘\(\le\)’, ‘\(<\)’, ‘\(\ge\)’, and ‘\(>\)’. If \(\#_{d}(\boldsymbol{s}) \asymp \#_{d'}(\boldsymbol{s}') +c\), then \(\kappa_{d}(\boldsymbol{s}) \asymp \kappa_{d'}(\boldsymbol{s}') + d -d'+c\). \(\tag*{◻}\)

Proof. By the definition of \(\kappa_d\), \(\kappa_{d}(\boldsymbol{s})= (d-1) + \#_{d}(\boldsymbol{s}) \asymp (d-1) + \#_{d'}(\boldsymbol{s}') +c = (d'-1) + \#_{d'}(\boldsymbol{s}') + d -d' +c = \kappa_{d'}(\boldsymbol{s}') + d -d'+c\).\(\tag*{◻}\)

Lemma 10: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n} \setminus \{\boldsymbol{0}\}\) and an integer \(d\) with \(d \ge 2\), \(\kappa_{d}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \kappa_{d+1}(\boldsymbol{s}) -1\). \(\tag*{◻}\)

Proof. Suppose that \([s_1,s_2,\ldots,s_n]=\boldsymbol{s}\) and \(\boldsymbol{s}' = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) = [s'_1,s'_2,\ldots,s'_n]\). By the definition of \(\tilde{\boldsymbol{\varPhi}}\), we have the following equation for \(L(s'_i)\) and \(L(s_i)\).

\[\begin{equation*} L(s'_i) = \left\{ \begin{array}{ll} 0 & \mbox{($s_i=0$)} \\ 0 & \mbox{($s_i=1$ and $i = \iota(\boldsymbol{s})$)} \\ 1 & \mbox{($s_i=1$ and $i \neq \iota(\boldsymbol{s})$)}\\ L(s_i)-1 & \mbox{($s_i \ge 2$)} \end{array} \right. \tag{3} \end{equation*}\]

From Eq. (3) and the assumption of the lemma \(d \ge 2\), if \(L(s_i) \ge d+1\), then \(L(s'_i) = L(s_i)-1\) and \(L(s'_i) \ge d\). Conversely, if \(L(s'_i) \ge d\), then \(L(s'_i) = L(s_i)-1\) and \(L(s_i) \ge d+1\). It follows that \(L(s'_i) \ge d\) holds if and only if \(L(s_i) \ge d+1\). Hence, \(\#_{d}(\boldsymbol{s}') = \#_{d+1}(\boldsymbol{s})\), and therefore \(\kappa_{d}(\boldsymbol{s}') = \kappa_{d+1}(\boldsymbol{s})-1\) by Lemma 9.\(\tag*{◻}\)

Lemma 11: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n} \setminus \{\boldsymbol{0}\}\), \(\kappa(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \kappa(\boldsymbol{s}) - 1\). \(\tag*{◻}\)

Proof. Suppose that \([s_1,s_2,\ldots,s_n]=\boldsymbol{s}\) and \(\boldsymbol{s}' = \tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}) = [s'_1,s'_2,\ldots,s'_n]\). Then, we have Eq. (3) for \(L(s'_i)\) and \(L(s_i)\) as we have seen in the proof of Lemma 10. Since \(\boldsymbol{s} \neq \boldsymbol{0}\), \(L_{max}(\boldsymbol{s}')= L_{max}(\boldsymbol{s})-1\) holds from Eq. (3).

(Case of \(\iota(\boldsymbol{s})=0\)): Here, no elements \(s_i\) equal 1. Hence, \(\#_{1}(\boldsymbol{s}) = \#_{2}(\boldsymbol{s})\), and therefore \(\kappa_{1}(\boldsymbol{s}) = \kappa_{2}(\boldsymbol{s})-1\) by Lemma 9. Since \(\kappa_{1}(\boldsymbol{s}) = \kappa_{2}(\boldsymbol{s})-1 < \kappa_{2}(\boldsymbol{s})\), we can exclude \(\kappa_{1}(\boldsymbol{s})\) from the candidates for \(\kappa(\boldsymbol{s})\):

\[\begin{equation*} \kappa(\boldsymbol{s}) = \max\{ \kappa_d(\boldsymbol{s}) \mid 2 \le d \le L_{max}(\boldsymbol{s}) \}. \tag{4} \end{equation*}\]

Next, consider \(\kappa_2(\boldsymbol{s})\). The absence of elements \(s_i = 1\) simplifies Eq. (3) as follows.

\[L(s'_i) = \left\{ \begin{array}{ll} 0 & \mbox{($s_i=0$)} \\ L(s_i)-1 & \mbox{($s_i \ge 2$)} \end{array} \right.\]

This equation shows that \(L(s'_i) \ge 1\) holds if and only if \(L(s_i) \ge 2\). Hence, \(\#_{1}(\boldsymbol{s}') = \#_{2}(\boldsymbol{s})\), and therefore \(\kappa_{1}(\boldsymbol{s}') = \kappa_{2}(\boldsymbol{s})-1\) by Lemma 9. For \(\kappa_{3}(\boldsymbol{s}), \kappa_{4}(\boldsymbol{s})\), and so on, \(\kappa_{d}(\boldsymbol{s}') = \kappa_{d+1}(\boldsymbol{s}) -1\) holds by Lemma 10. Combining these equations with the definition of \(\kappa\), we have \(\kappa(\boldsymbol{s}') = \max\{ \kappa_d(\boldsymbol{s}') \mid 1 \le d \le L_{max}(\boldsymbol{s}') \} = \max\{ \kappa_{d+1}(\boldsymbol{s})-1 \mid 1 \le d \le L_{max}(\boldsymbol{s}') \} = \max\{ \kappa_d(\boldsymbol{s})-1 \mid 2 \le d \le L_{max}(\boldsymbol{s}')+1 (= L_{max}(\boldsymbol{s})) \} = \max\{ \kappa_d(\boldsymbol{s}) \mid 2 \le d \le L_{max}(\boldsymbol{s}) \} -1\). From this equation and Eq. (4), we conclude \(\kappa(\boldsymbol{s}') = \kappa(\boldsymbol{s}) - 1\).

(Case of \(\iota(\boldsymbol{s}) \neq 0\)): In this case, \(L(s'_{\iota(\boldsymbol{s})})=0\) and \(L(s_{\iota(\boldsymbol{s})})=1\) from Eq. (3). For other indices \(i \neq \iota(\boldsymbol{s})\), \(L(s'_i) \ge 1\) holds if and only if \(L(s_i) \ge 1\). Hence, \(\#_{1}(\boldsymbol{s}') = \#_{1}(\boldsymbol{s})-1\) holds, and then, Lemma 9 yields

\[\begin{equation*} \kappa_1(\boldsymbol{s}') = \kappa_1(\boldsymbol{s})-1. \tag{5} \end{equation*}\]

Next, consider \(\kappa_2(\boldsymbol{s})\). Equation (3) shows that if \(L(s_i) \ge 2\), then \(L(s'_i) \ge 1\), but its converse does not hold. Hence, \(\#_{2}(\boldsymbol{s}) \le \#_{1}(\boldsymbol{s}')\), and therefore \(\kappa_{2}(\boldsymbol{s}) \le \kappa_{1}(\boldsymbol{s}')+1\) by Lemma 9. Since \(\kappa_1(\boldsymbol{s}') +1 = \kappa_1(\boldsymbol{s})\) from Eq. (5), we have \(\kappa_{2}(\boldsymbol{s}) \le \kappa_{1}(\boldsymbol{s}')+1 = \kappa_{1}(\boldsymbol{s})\). Since \(\kappa_{2}(\boldsymbol{s}) \le \kappa_{1}(\boldsymbol{s})\), we can exclude \(\kappa_{2}(\boldsymbol{s})\) from the candidates for \(\kappa(\boldsymbol{s})\):

\[\begin{equation*} \kappa(\boldsymbol{s}) = \max\{ \kappa_d(\boldsymbol{s}) \mid 1 \le d \le L_{max}(\boldsymbol{s}), \, d \neq 2 \}. \tag{6} \end{equation*}\]

For \(\kappa_{3}(\boldsymbol{s}), \kappa_{4}(\boldsymbol{s})\), and so on, \(\kappa_{d}(\boldsymbol{s}') = \kappa_{d+1}(\boldsymbol{s}) -1\) holds by Lemma 10. Combining this equation, Eq. (5), and the definition of \(\kappa\), we have \(\kappa(\boldsymbol{s}') = \max\{ \kappa_d(\boldsymbol{s}') \mid 1 \le d \le L_{max}(\boldsymbol{s}') \} = \max\{ \kappa_d(\boldsymbol{s})-1 \mid 1 \le d \le L_{max}(\boldsymbol{s}')+1 (= L_{max}(\boldsymbol{s})), \, d \neq 2\} = \max\{ \kappa_d(\boldsymbol{s}) \mid 1 \le d \le L_{max}(\boldsymbol{s}), \, d \neq 2\} -1\). From this equation and Eq. (6), we conclude \(\kappa(\boldsymbol{s}') = \kappa(\boldsymbol{s}) - 1\).\(\tag*{◻}\)

Theorem 6: For a vector \(\boldsymbol{s} \in \mathbb{N}_0^{n}\),

\[\kappa(\boldsymbol{s})=\tilde{\sigma}(\boldsymbol{s})\]

holds. \(\tag*{◻}\)

Proof. The proof is by the mathematical induction on \(\kappa(\boldsymbol{s})\). If \(\kappa(\boldsymbol{s}) = 0\), then \(\boldsymbol{s} = \boldsymbol{0}\), and therefore \(\tilde{\sigma}(\boldsymbol{s})=0\). Thus, the theorem holds for \(\kappa(\boldsymbol{s}) = 0\).

Assume that the theorem holds for any vector \(\boldsymbol{s}'\) such that \(\kappa(\boldsymbol{s}') = k\), i.e., \(\kappa(\boldsymbol{s}') = \tilde{\sigma}(\boldsymbol{s}') = k\). Using this assumption, we prove the theorem for \(\kappa(\boldsymbol{s}) = k+1\). Suppose that \(\boldsymbol{s}\) is a vector such that \(\kappa(\boldsymbol{s}) = k+1\). Then, since \(\kappa(\boldsymbol{s}) = \kappa(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) + 1\) by Lemma 11, \(\kappa(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = k\) holds. By using the induction hypothesis, \(\kappa(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s}))\). By Proposition 4, \(\tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) = \tilde{\sigma}(\boldsymbol{s}) -1\). From these equations, we have \(\kappa(\boldsymbol{s}) = \kappa(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) + 1 = \tilde{\sigma}(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{s})) + 1 = \tilde{\sigma}(\boldsymbol{s}) -1 + 1 = \tilde{\sigma}(\boldsymbol{s})\). Thus, the inductive step was proved.\(\tag*{◻}\)

Example 8: By Examples 3 and 7, \(\kappa([1,4,8,9])=\tilde{\sigma}([1,4,8,9])=5\). \(\tag*{◻}\)

Theorem 6 shows that the value of \(\tilde{\sigma}(\boldsymbol{s})\) can also be obtained by calculating \(\kappa(\boldsymbol{s})\). For computational efficiency, we use \(\kappa(\boldsymbol{s})\) mainly instead of \(\tilde{\sigma}(\boldsymbol{s})\) in the rest of the paper although \(\tilde{\sigma}(\boldsymbol{s})\) provided theoretical insights for the comparison with \(\sigma\text{$-$}lb(\boldsymbol{s})\) in Sects. 3 and 4.

We now present an algorithm for \(\kappa(\boldsymbol{s})\) as Kappa in Fig. 3, in which vectors are expressed as 1-indexed arrays. In Kappa, the calculation of \(\#_{d}(\boldsymbol{s})\) is improved by a technique similar to bucket sorting under the assumption that \(L(s_i) \le n\) for any \(s_i\). Since Kappa is customized for the characteristic vector \(\boldsymbol{\varLambda}(F)\) of a reversible function \(F\), the bit length of \(s_i\) is assumed to be at most \(n\) by Proposition 1. The for loop starting at Line 7 counts the frequency of the bit length of the elements in \(\boldsymbol{s}\) except those with a bit length of 0, storing the results in \(\boldsymbol{b}\). The for loop starting at Line 13 calculates the suffix sums of \(\boldsymbol{b}\), resulting in \(\boldsymbol{h} = [\#_1(\boldsymbol{s}), \#_2(\boldsymbol{s}), \ldots, \#_n(\boldsymbol{s})]\). The for loop at Line 15 identifies the maximum value of \(\kappa_i(\boldsymbol{s})\) for \(1 \le i \le n\), which is finally returned at Line 18.

Fig. 3  Kappa: a fast algorithm for \(\kappa\).

The time complexity of Kappa is \(\mathcal{O}(n)\) if \(L\) is assumed to be a constant-time operation. The assumption is based on the fact that \(L\), i.e., the bit length of an integer, is mathematically a simple logarithm as in Definition 11, and is practically a built-in operation in many programming languages such as Mathematica and Common Lisp. Note that the evaluation of the complexity may vary according to the presumed complexity of the \(L\) operation because Kappa invokes this operation \(n\) times.

6.  Experimental Results

To measure the computation time, we implemented Kappa in Common Lisp (SBCL), and calculated the values of \(\kappa(\boldsymbol{\varLambda}(F))\) for all 3-variable functions (40,320 in total) as well as for 50,000 randomly-generated \(n\)-variable functions ranging from \(n=4\) to \(10\). The program was executed on a computer with Ubuntu 22.04LTS / Core i9-12900K CPU (3.2 GHz). Table 1 shows the average computation time in microseconds per characteristic vector. \(\kappa\) is much faster than \(\sigma\text{$-$}lb\) even though the fastest algorithm named SigmaLB3 [25] for calculating \(\sigma\text{$-$}lb\) was used as the implementation of \(\sigma\text{$-$}lb\). It should be mentioned that SigmaLB3 consumes a lot of memory for caching to reduce its computation time. Without this caching strategy, it has been reported [25] that the computation time for \(\sigma\text{$-$}lb\) grows exponentially with \(n\). Regarding memory usage, Kappa apparently works with only \(\mathcal{O}(n)\) memory.

Table 1  Average computation time [\(\mu\)s] per vector.

Kappa is very fast, but the growth of the experimental times in Table 1 does not look \(\mathcal{O}(n)\). A considerable factor behind this is the overhead necessary for Kappa to work as a procedure. We measured the time of this overhead, which includes the function call for Kappa and the allocation of local variables and arrays. The overhead was about 0.032[\(\mu\)s]. When we adjust the times of Kappa in Table 1 by subtracting this overhead, the resultant times become approximately proportional to \(n\). The calculation of Kappa is so simple that the necessary overhead seems to be a major part of the total computation time. From this observation, we can conclude that Kappa is sufficiently quick in practice.

By Theorem 3, \(\kappa(\boldsymbol{\varLambda}(F))\) is a lower bound on the GC of a circuit of a reversible function \(F\). As an experimental comparison between \(\kappa(\boldsymbol{\varLambda}(F))\) and \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\), we computed both lower bounds for all (40,320) 3-variable functions and 50,000 randomly-generated \(n\)-variable functions ranging from \(n=4\) to \(10\) as well as the experiments in Table 1. The average values of the lower bounds for these functions are given in Table 2. The two lower bounds become closer to each other with increase in the number of variables. On average, the difference in quality between \(\kappa\) and \(\sigma\text{$-$}lb\) is very slight. In this paper, we omit a comparison with the minimum circuits or the upper bounds. A detailed comparison between those data and \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\) has been made in the work [25].

Table 2  Average of lower bounds.

Table 3 shows the match-to-mismatch ratio of \(\kappa(\boldsymbol{\varLambda}(F))\) and \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\) for functions. Theorem 5 states that there can be two cases: either \(\kappa(\boldsymbol{\varLambda}(F)) = \sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))\) or \(\kappa(\boldsymbol{\varLambda}(F)) = \sigma\text{$-$}lb(\boldsymbol{\varLambda}(F))-1\). In Table 3, more than 90% of the functions for \(n \ge 4\) fall into the former case, and the percentage of this case increases with \(n\). Experimentally, the two lower bounds are equal for most functions. One instance of a mismatch in \(n = 4\) is the function \(F = [6, 12, 14, 11, 3, 4, 13, 1, 10, 15, 7, 2, 8, 9, 5, 0]\) in permutation notation. Its characteristic vector is \(\boldsymbol{\varLambda}(F) = [9, 9, 11, 7]\), and its lower bounds are \(\kappa(\boldsymbol{\varLambda}(F)) = 6\) and \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F)) = 7\). Another such instance is the function \(F = [10, 15, 6, 13, 9, 2, 7, 5, 3, 8, 0, 14, 12, 4, 1, 11]\) with \(\boldsymbol{\varLambda}(F) = [6, 10, 11, 10]\), \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{\varLambda}(F)) = [3, 5, 5, 5]\), \(\kappa(\boldsymbol{\varLambda}(F)) = 6\), and \(\sigma\text{$-$}lb(\boldsymbol{\varLambda}(F)) = 7\). Like these examples, if \(\boldsymbol{\varLambda}(F)\) or \(\tilde{\boldsymbol{\varPhi}}(\boldsymbol{\varLambda}(F))\) contains many odd numbers, the two lower bounds may differ due to the discrepancy between the ways of halving in \(\boldsymbol{\varPhi}\) and \(\tilde{\boldsymbol{\varPhi}}\) operations.

Table 3  Match-to-mismatch ratio of two lower bounds for functions.

7.  Conclusion

We have introduced a halving operation \(\tilde{\boldsymbol{\varPhi}}\) for the characteristic vectors of reversible functions. Through a careful analysis of \(\tilde{\boldsymbol{\varPhi}}\), we proposed a new lower bound \(\tilde{\sigma}\) on the GC of reversible circuits that realize a given reversible function. To improve computational efficiency, a faster version of \(\tilde{\sigma}\), called \(\kappa\), was presented. The theory and experiments have confirmed that the value of \(\kappa\) is almost the same as that of the previous lower bound \(\sigma\text{$-$}lb\). \(\kappa\) can be calculated much faster than \(\sigma\text{$-$}lb\) by several orders of magnitude. The complexity of our proposed algorithm for \(\kappa\) is \(\mathcal{O}(n)\) with respect to both time and space. Our future work includes refining our bounds to take into account practical cost metrics such as the number of controls and applying our bounds to the reversible logic synthesis.

References

[1] T. Hirayama, R. Suzuki, K. Yamanaka, and Y. Nishitani, “Quick computation of the lower bound on the gate count of toffoli-based reversible logic circuits,” Proc. 53rd ISMVL, Matsue, Japan, pp.153-157, May 2023.

[2] R. Wille and R. Drechsler, “Towards a Design Flow for Reversible Logic,” Springer, 2010.

[3] P. Gupta, A. Agrawal, and N.K. Jha, “An algorithm for synthesis of reversible logic circuits,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol.25, no.11, pp.2317-2330, Nov. 2006.

[4] K. Iwama, Y. Kambayashi, and S. Yamashita, “Transformation rules for designing CNOT-based quantum circuits,” Proc. 39th Design Automation Conference, USA, pp.419-424, 2002.

[5] D. Maslov, G.W. Dueck, and D.M. Miller, “Toffoli network synthesis with templates,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol.24, no.6, pp.807-817, June 2005.

[6] D. Miller and G. Dueck, “Spectral techniques for reversible logic synthesis,” Proc. 6th Int. Symp. Representations and Methodology of Future Computing Technologies, Trier, Germany, pp.56-62, March 2003.

[7] G.W. Dueck, D. Maslov, and D.M. Miller, “Transformation-based synthesis of networks of Toffoli/Fredkin gates,” Proc. Canadian Conference on Electrical and Computer Engineering, pp.211-214, vol.1, May 2003.

[8] P. Kerntopf, “A new heuristic algorithm for reversible logic synthesis,” Proc. 41st Design Automation Conference, pp.834-837, 2004.

[9] D. Maslov, G.W. Dueck, and D.M. Miller, “Synthesis of Fredkin-Toffoli reversible networks,” IEEE Trans. VLSI Syst., vol.13, no.6, pp.765-769, June 2005.

[10] H. Thapliyal and N. Ranganathan, “Design of reversible sequential circuits optimizing quantum cost, delay and garbage outputs,” ACM Journal of Emerging Technologies in Computing Systems, vol.6, no.4, article 14, pp.1-31, Dec. 2010.

[11] H. Thapliyal and N. Ranganathan, “Design of efficient reversible logic based binary and BCD adder circuits,” ACM Journal of Emerging Technologies in Computing Systems, vol.9, no.3, pp.17:1-17:31, Oct. 2013.

[12] M. Saeedi and I.L. Markov, “Synthesis and optimization of reversible circuits - a survey,” ACM Computing Surveys, vol.45, no.2, article 21, pp.1-34, Feb. 2013.

[13] K.N. Patel, I.L. Markov, and J.P. Hayes, “Optimal synthesis of linear reversible circuits,” Quantum Information and Computation, vol.8, no.3&4, pp.282-294, March 2008.

[14] N. Abdessaied, M. Amy, R. Drechsler, and M. Soeken, “Complexity of reversible circuits and their quantum implementations,” Theoretical Computer Science, vol.618, pp.85-106, 2016.

[15] D. Maslov and G.W. Dueck, “Reversible cascades with minimal garbage,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol.23, no.11, pp.1497-1509, Nov. 2004.

[16] V.V. Shende, A.K. Prasad, I.L. Markov, and J.P. Hayes, “Synthesis of reversible logic circuits,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol.22, no.6, pp.710-722, June 2003.

[17] M. Soeken, N. Abdessaied, and R. Drechsler, “A framework for reversible circuit complexity,” Proc. International Workshop on Boolean Problems 2014, arXiv:1407.5878, Aug. 2014.

[18] D.V. Zakablukov, “On asymptotic gate complexity and depth of reversible circuits without additional memory,” arXiv:1504.06876, Feb. 2016.

[19] S. Popescu, B. Groisman, and S. Massar, “Lower bound on the number of Toffoli gates in a classical reversible circuit through quantum information concepts,” Physical Review Letters, vol.95, no.12, pp.120503-1-120503-4, Sept. 2005.

[20] D. Maslov, “Optimal and asymptotically optimal NCT reversible circuits by the gate types,” Quantum Information & Computation, vol.16, no.13&14, pp.1096-1112, Oct. 2016.

[21] M. Saeedi, M.S. Zamani, M. Sedighi, and Z. Sasanian, “Reversible circuit synthesis using a cycle-based approach,” ACM Journal on Emerging Technologies in Computing Systems, vol.6, no.4, article 13, pp.1-26, Dec. 2010.

[22] R. Wille and R. Drechsler, “Synthesis of Boolean functions in reversible logic,” in Progress in Applications of Boolean Functions, ed. T. Sasao and J.T. Butler, ch. 4, pp.79-96, Morgan & Claypool Publishers, 2010.

[23] N.M. Nayeem and J.E. Rice, “Improved ESOP-based synthesis of reversible logic,” Proc. Reed-Muller 2011 Workshop, Tuusula, Finland, pp.57-62, May 2011.

[24] M. Higashiohno, T. Hirayama, and Y. Nishitani, “A lower bound on the number of Toffoli gates in reversible logic circuits,” IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, vol.J92-A, no.4, pp.263-266, April 2009.

[25] T. Hirayama, H. Sugawara, K. Yamanaka, and Y. Nishitani, “A lower bound on the gate count of Toffoli-based reversible logic circuits,” IEICE Trans. Information and Systems, vol.E97.D, no.9, pp.2253-2261, Sept. 2014.

[26] M. Szyprowski and P. Kerntopf, “Estimating the quality of complexity measures in heuristics for reversible logic synthesis,” Proc. IEEE Congress on Evolutionary Computation (CEC) 2010, pp.1-8, July 2010.

[27] X. Chen and M.L. Bushnell, “Efficient Branch and Bound Search with Application to Computer-Aided Design,” Springer, 1996.

[28] M. Davio, J.P. Deschamps, and A. Thayse, “Discrete and Switching Functions,” McGraw-Hill International, 1978.

[29] T. Sasao, “Switching Theory For Logic Synthesis,” Kluwer Academic Publishers, Feb. 1999.

Authors

Takashi HIRAYAMA
  Iwate University

Rin SUZUKI
  Iwate University

Katsuhisa YAMANAKA
  Iwate University

Yasuaki NISHITANI
  Iwate University

Keyword

reversible logic circuits,  Toffoli gates,  lower bound,  logic minimization