An Improved Design of n-Bit Universal Reversible Gate Library

Abstract

Reversible logic has been considered as an important solution to the power dissipation problem in the existing electronic devices. Many universal reversible libraries that include more than one type of gates have been proposed in the literature. This paper proposes a novel reversible n-bit gate that is proved to be universal for synthesizing reversible circuits. Reducing the reversible circuit synthesis problem to permutation group allows Schreier-Sims Algorithm for the strong generating set-finding problem to be used in the synthesize of reversible circuits using the proposed gate. A novel optimization rules will be proposed to further optimize the synthesized circuits in terms of the number of gates, the quantum cost and the utilization of library to achieve better results than that shown in the literature.

1 Introduction

Research in reversible logic circuits [1, 2] is motivated by the advances in quantum computation [3, 4] , low-power design CMOS [5, 6] and many more. Landauer [7] proved that any conventional, irreversible gate dissipates a certain amount of energy per operation. Bennett [1] shows that the power dissipation can be avoided in a circuit if and only if the circuit is synthesized using reversible gates.

Recently, the study of reversible logic synthesis problem using group theory is rising rapidly. Investigation on the universality of the basic building blocks of reversible circuits has been presented [8, 9]. A relation between the reversible logic synthesis problem and Young subgroups has been discussed [10]. A difference between the decomposition of a quantum circuit and a reversible circuit using group theory has been shown [11]. GAP-based algorithms that is used to synthesize reversible circuits for various types of gates, and with various gate costs have been proposed [12,13,14, 22]. GAP-based algorithms that is used to synthesize reversible circuits for one type of gates have been proposed [15, 25].

The aim of the paper is to propose a novel reversible n-bit gate that is proved to be universal for reversible circuit synthesis. The proposed gate is extendable according to the number of bits in the circuit design. The proposed gate is important as it is a single type of gate and using this technology might be cheaper to implement. All results shown in this paper have been implemented and tested using the group theory algebraic software GAP [16]. The experimental results using the proposed gate library show better quantum cost and utilization of the gate library compared to the existing work in [15, 25]. Some obtained results matches the results obtained by other methods such as [12, 17, 18, 22].

The paper is organized as follows: Section 2 reviews the required background for the synthesis of reversible circuit problem. In addition, it shows that the problem can be reduced to permutation group, and gives an analysis about the universality properties of the common universal reversible libraries in the literature. Section 3 presents the proposed gate library and its properties. Section 4 discusses the experimental results and shows a comparison with relevant results obtained by others in the literature. The paper ends up with a summary and conclusion in Section 5.

2 Preliminaries

This section will review the basic concepts of reversible circuits, terminologies used for reversible circuit synthesis and the relationship between reversible logic circuits and permutation group theory.

Let X = {0,1} and define a Boolean function f with n input variables x₁,…,x_n and n output variables y₁,…,y_n, to be a function $f:{X}^n\to {X}^n$, where (x₁,…,x_n) ∈ Xⁿ is called the input vector and (y₁,…,y_n) ∈ Xⁿ is called the output vector. An n-input n-output Boolean function is reversible (n × n function) if it maps each input vector to a unique output vector, i.e. bijection. There are 2ⁿ! reversible n × n Boolean functions. For n = 3, there are 40320 3-in/out reversible functions.

An n-input n-output (n-in/out) reversible gate (or circuit) is a gate that realizes an n × n reversible function. A set of reversible gates that can be used to build a reversible circuit is called a gate library L [15]. A universal reversible gate library L_n is a set of reversible gates such that a cascading of gates in L_n can be used to synthesize any reversible circuit with n-in/out [15]. A universal reversible gate sub library SL_n is a set of reversible gates such that $S{L}_n\subseteq {L}_n$ that can be used to build any reversible circuit with n-in/out [15]. Let |L_n| be the number of gates in L_n and |SL_n| be the number of gates in SL_n, then the ratio ${2}^{\mid S{L}_n\mid }/{2}^{\mid {L}_n\mid }$ represents the utilization of gates in a universal sub library and the ratio ${2}^{\min \left(|S{L}_n|\right)}/{2}^{\mid {L}_n\mid }$ represents the utilization of gates in the smallest universal sub libraries from a universal library [15].

Let a finite set A = {1,2,…,2ⁿ} and a bijection $\delta :A\to A$, then can be written as, $\left(\begin{array}{ccccc}1& 2& 3& \cdots & {2}^n\\ {}\delta (1)& \delta (2)& \delta (3)& \cdots & \delta \left({2}^n\right)\end{array}\right)$, i.e. δ is a permutation of A. Let A be an ordered set, then the top row can be eliminated and δ can be written as,

$$ \left(\delta (1)\kern0.5em \delta (2)\kern0.5em \delta (3)\kern0.5em \cdots \kern0.5em \delta \left({2}^n\right)\right). $$

(1)

Any reversible circuit with n-in/out can be considered as a permutation and Eq..1 is called the specification of this reversible circuit [15]. The set of all permutations on A forms a symmetric group on A under composition of mappings [18], denoted by ${S}_{2^n}$ [19]. A permutation group G is a subgroup of the symmetric group ${S}_{2^n}$ [18]. A universal reversible gate library L_n is called the generators of the group. Another important notation of a permutation is the product of disjoint cycles [19]. For example, $\left(\begin{array}{c}1,2,3,4,5,6,7,8\\ {}8,2,6,4,5,3,1,7\end{array}\right)$ will be written as (1,8,7)(3,6). The identity mapping “()” is called the unit element in a permutation group. A product p ∗ q of two permutations p and q means applying mapping p then q, which is equivalent to cascading p and q [20].

2.1 Reversible Circuits

The CⁿNOT gate is a reversible gate that can be used to build any n-in/out reversible circuits. It is denoted in [13] as,

$$ {C}^n\mathrm{NOT}\left({x}_1,{x}_2,\cdots \kern0.3em ,{x}_{n-1};f\right), $$

with n inputs:x₁,x₂,⋯ ,x_n− 1 (named control bits) and f_in (named target bit), and n outputs:y₁,y₂,⋯ ,y_n− 1 and f_out. The operation of the CⁿNOT gate is defined as follows,

$$ {y}_i={x}_i,\mathrm{for}1\le i\le n-1,{f}_{\mathrm{out}}={f}_{\mathrm{in}}\oplus {x}_1,{x}_2\cdots {x}_{n-1}, $$

i.e. if the control bits are set to 1 then the target bit is flipped, otherwise the target bit is left unchanged. The CⁿNOT gate is represented by the circuit shown in Fig. 1.

Fig. 1

CⁿNOT gate.The control bit is denoted by ∙, and the target bit is denoted by ⊕

There exist three special cases of the CⁿNOT gate and are defined as, C¹NOT gate with no control bit is called NOT gate. C²NOT gate with one control bit is called CNOT. C³NOT gate with two control bits is called Toffile gate. For the ease of readability C¹NOT, C²NOT and C³NOT can be written as N, C and T respectively where the control and/or target bits will be shown in the subscript of the gate and the total number of bits will be shown in the superscript. Many quantum gates have been studied but we focus on the elementary quantum gates NOT, CNOT, Controlled-V (v) and Controlled-V⁺ (u), also known as quantum primitives. These gates have been widely used to synthesize reversible circuits [26]. The Controlled-V (v) and the Controlled-V⁺ (u) gates are represented by the matrices as follows, $v=\frac{1+i}{2}\left(\begin{array}{cc}1& -i\\ {}-i& 1\end{array}\right)$ and $u=\frac{1-i}{2}\left(\begin{array}{cc}1& i\\ {}i& 1\end{array}\right)$, where vu = uv = I, vv = uu = N and I is the identity gate [26].

The quantum cost of a reversible circuit is measured by the number of elementary gates required to build the CⁿNOT gate [26], which are considered as the number of 2-qubit gates used in its implementation as a circuit. In this paper, we use the cost015 metric [12], the quantum cost of NOT gate is 0 (zero), the quantum cost of any 2-qubit gate is 1 and the quantum cost of the T³ gate is 5.

The NOT (N) gate acts on a 1-bit and it is defined as follows, it flips the input bit unconditionally with quantum cost equal zero [12]. A gate library with N³ gates is not universal for 3-in/out reversible circuits since it can realize 8 circuits from the 40320 circuits [15]. There are 3 possible N³ gates for the 3-in/out reversible circuits as shown in Fig. 2, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{N}_1^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1\oplus 1,{x}_2,{x}_3\right)\equiv \left(1,5\right)\left(2,6\right)\left(3,7\right)\left(4,8\right),\\ {}{N}_2^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2\oplus 1,{x}_3\right)\equiv \left(1,3\right)\left(2,4\right)\left(5,7\right)\left(6,8\right),\\ {}{N}_3^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2,{x}_3\oplus 1\right)\equiv \left(1,2\right)\left(3,4\right)\left(5,6\right)\left(7,8\right).\end{array}} $$

(2)

Fig. 2

The 3 possible N gates for 3-bit reversible circuits

The Feynman (C) gate acts on two-bits and it is defined as follows, if the control bit is set to 1 then the target bit line is flipped. A gate library with C³ gates is not universal for 3-in/out reversible circuits, since it can realize 168 circuits from the 40320 reversible circuits [15]. There are 6 possible C³ gates for the 3-in/out reversible circuits as shown in Fig. 3, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{C}_{12}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2\oplus {x}_1,{x}_3\right)\equiv \left(5,7\right)\left(6,8\right),\\ {}{C}_{13}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2,{x}_3\oplus {x}_1\right)\equiv \left(5,6\right)\left(7,8\right),\\ {}{C}_{23}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2,{x}_3\oplus {x}_2\right)\equiv \left(3,4\right)\left(7,8\right),\\ {}{C}_{21}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1\oplus {x}_2,{x}_2,{x}_3\right)\equiv \left(3,7\right)\left(4,8\right),\\ {}{C}_{32}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2\oplus {x}_3,{x}_3\right)\equiv \left(2,7\right)\left(6,8\right),\\ {}{C}_{31}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1\oplus {x}_3,{x}_2,{x}_3\right)\equiv \left(2,6\right)\left(4,8\right).\end{array}} $$

(3)

Fig. 3

The 6 possible C gates for 3-bit reversible circuits

The Toffile (T³) gate acts on three-bits and it is defined as follows, if the two control bits are set to 1 then the third target bit line is flipped. The T³ gate is the smallest reversible gate that is proved to be universal for non-reversible computation as it is proved to function as NAND gate by initializing the target bit to 1 [21]. A gate library with T³ gate is not universal for 3-in/out reversible circuits, since it can realize 24 circuits from 40320 reversible circuits [15]. There are three possible T³ gates for the 3-in/out reversible circuits as shown in Fig. 4, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{T}_{123}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2,{x}_3\oplus {x}_1{x}_2\right)\equiv \left(7,8\right),\\ {}{T}_{132}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_2\oplus {x}_1{x}_3,{x}_3\right)\equiv \left(6,8\right),\\ {}{T}_{321}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1\oplus {x}_2{x}_3,{x}_2,{x}_3\right)\equiv \left(4,8\right).\end{array}} $$

(4)

Fig. 4

The 3 possible T³ gates for 3-bit reversible circuits

The Fredkin (F) gate acts on three-bits and it is defined as follows, it performs a conditional swap on two of its inputs if the third input is set to 1. A gate library of F³ gates is not universal for 3-in/out reversible circuits, since it can realize 6 circuits from the 40320 reversible circuits [15]. There are three possible F³ gates for 3-in/out reversible circuits as shown in Fig. 5, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{F}_{123}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_1,{x}_3,{x}_2\right)\equiv \left(6,7\right),\\ {}{F}_{132}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_3,{x}_2,{x}_1\right)\equiv \left(4,7\right),\\ {}{F}_{321}^3:\left({x}_1,{x}_2,{x}_3\right)& \to & \left({x}_2,{x}_1,{x}_3\right)\equiv \left(4,6\right).\end{array}} $$

(5)

Fig. 5

The 3 possible F³ gates for 3-bit reversible circuits

The Peres (P) gate acts on three-bits and it is defined as follows, it combines the function of T gate and C gate in a one gate. A gate library of P³ gates is not universal for 3-in/out reversible circuits, since it can realize 5040 circuits from the 40320 reversible circuits [15]. There are six possible P³ gates for 3-in/out reversible circuits as shown in Fig. 6, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{P}_{23}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1,{x}_2\oplus {x}_1,{x}_3\oplus {x}_1{x}_2\right)\equiv \left(5,7,6,8\right),& & \\ {}{P}_{32}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1,{x}_2\oplus {x}_1{x}_3,{x}_3\oplus {x}_1\right)\equiv \left(5,6,7,8\right),& & \\ {}{P}_{13}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1\oplus {x}_2,{x}_2,{x}_3\oplus {x}_1{x}_2\right)\equiv \left(3,7,4,8\right),& & \\ {}{P}_{31}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1\oplus {x}_2{x}_3,{x}_2,{x}_3\oplus {x}_2\right)\equiv \left(3,4,7,8\right),& & \\ {}{P}_{12}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1\oplus {x}_3,{x}_2\oplus {x}_1{x}_3,{x}_3\right)\equiv \left(2,6,4,8\right),& & \\ {}{P}_{21}^3:\left({x}_1,{x}_2,{x}_3\right)\to \left({x}_1\oplus {x}_2{x}_3,{x}_2\oplus {x}_3,{x}_3\right)\equiv \left(2,4,6,8\right).& & \end{array}} $$

(6)

Fig. 6

The 6 possible P³ gates for 3-bit reversible circuits

The (R³) gate acts on three-bits and it is defined as follows, it combines the action of N, C and T³ in a single gate. A gate library of R³ gates is universal for 3-in/out reversible circuits, since it can realize all the 40320 reversible circuits [25]. There are six possible R³ gates for 3-in/out reversible circuits as shown in Fig. 7, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}& {R}_{j,k,l}^3& :{y}_i={x}_j\oplus {x}_k\oplus {x}_j\cdot {x}_l\oplus 1,\\ {}& & \kern1em {y}_k={x}_k\oplus {x}_j\cdot {x}_l\oplus 1,\\ {}& & \kern1em {y}_l={x}_l\oplus {x}_j,\\ {}& {R}_{123}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,7,6,5,4,2,8,3\right),\\ {}& {R}_{321}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,4,6,2,7,5,8,3\right),\\ {}& {R}_{312}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,4,7,3,6,5,8,2\right),\\ {}& {R}_{132}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,6,7,5,4,3,8,2\right),\\ {}& {R}_{231}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,6,4,2,7,3,8,5\right),\\ {}& {R}_{213}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,7,4,3,6,2,8,5\right).\end{array}} $$

(7)

where j,k and l ∈ {1, 2, 3} in any order.

Fig. 7

The 6 possible R³ gates for 3-bit reversible circuits

Many suggested universal reversible libraries consist of more than one type of gates such as NOT(N), Feynman(C), Toffoli(T³), Fredkin(F) and Peres(P) gates. Different combinations of universal reversible libraries have been studied [12, 14, 17, 23]. For examples, there exist 6-universal reversible libraries NCT, NCP, NCF, NCPT, NCTF and NCPF. Recently some universal reversible libraries consist of one type of gate such as G gate and R gate have been proposed [15, 25].

3 The Proposed M-Gate Library

This section proposes a reversible n-bit gate Mⁿ for n-bits input/output reversible circuits. The proposed M-gate is extendable according to the number of bits in the circuit design.

3.1 Single-Bit Gate

M¹ gate performs as N gate which inverts the input bit unconditionally. For 1-bit reversible circuits built using M-gate library, there is one M¹ gate with quantum cost equal zero as shown in Fig. 8, that perform as follows:

$$ {M}_1^1:\left({x}_1\right)\to \left({x}_1\oplus 1\right)\equiv \left(1,2\right). $$

(8)

3.2 Two-Bit Gate

Fig. 8

The one possible M¹ gate for 1-bit reversible circuit

M² gate performs as a combination of N gate and C gate. For 2-bit reversible circuits built using M gate library, there are two possible M² gates with quantum cost equal 1 as shown in Fig. 9, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}& {M}_{i,j}^2& :{y}_i={x}_i\oplus 1,\\ {}& & {y}_j={x}_j\oplus {y}_i={x}_j\oplus {x}_i\oplus 1,\\ {}& {M}_{1,2}^2& :\left({x}_1,{x}_2\right)\to \left(1,4,2,3\right),\\ {}& {M}_{2,1}^2& :\left({x}_1,{x}_2\right)\to \left(1,4,3,2\right).\end{array}} $$

(9)

Fig. 9

The two possible M² gate for 2-bit reversible circuit

3.3 Three-Bit Gate

M³ gate combines the action of the three gates N, C and T³. It acts on an arbitrary 3-bits x_i, x_j and x_k in any order. For 3-bit reversible circuits built using M-gate library, there are six possible M³ gates with quantum cost equal 5 as shown in Fig. 10, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}& {M}_{i,j,k}^3& :{y}_i={x}_i\oplus \left({x}_k\oplus {x}_j\right),\\ {}& & {y}_j=\left({x}_j\oplus 1\right)\oplus \left({x}_k\oplus {x}_j\right)\cdot \Big({x}_i\oplus \left({x}_k\oplus {x}_j\right),\\ {}& & {y}_k={x}_k\oplus {x}_j,\\ {}& {M}_{1,2,3}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,3,8,5,7,2,6,4\right),\\ {}& {M}_{1,3,2}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,2,8,5,6,3,7,4\right),\\ {}& {M}_{2,1,3}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,5,8,3,7,2,4,6\right),\\ {}& {M}_{2,3,1}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,2,8,3,4,5,7,6\right),\\ {}& {M}_{3,1,2}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,5,8,2,6,3,4,7\right),\\ {}& {M}_{3,2,1}^3& :\left({x}_1,{x}_2,{x}_3\right)\to \left(1,3,8,2,4,5,6,7\right).\end{array}} $$

(10)

where i,j and k ∈ {1, 2, 3} in any order.

Fig. 10

The 6 possible M³ gates for 3-bit reversible circuits

The quantum cost of the ${M}_{123}^3$ gate is 4, Fig. 11 shows the decomposition of the gate. Figure 11a shows the gate representation of gate, Fig. 11b shows the four component gates of ${M}_{123}^3$, and Fig. 11c shows the representation of the ${M}_{123}^3$ gate into its five elementary gates (one of them with cost zero). The optimization is done by applying new Toffoli decomposition techniques [24] and applying the moving rules in [22]. The first gate [C₂₃v₃₂], which is merging gate between C₂₃ and v₃₂ in order, as shown in Fig. 12. To improve the quantum cost of the circuits synthesized with M³ gate, N gate added to form a new library called NM³ which is also universal. The main NM³ library consist of nine gates (generators) as shown in Figs. 13 and 14.

Fig. 11

The circuit representation for the decomposition of ${M}_{123}^3$ gate, where: a The gate representation, b The decomposition of the ${M}_{123}^3$ gate into its four components and c The optimized decomposition of ${M}_{123}^3$ gate into its five elementary quantum gates

Fig. 12

The circuit representation for the decomposition of [C₂₃v₃₂] gate [25], where: a The gate representation, and b The decomposition of the gate into its two component C₂₃ gate and v₃₂ gate

Fig. 13

The circuit representation for the decomposition of [C₃₁C₁₃] gate [25], where: a The gate representation, and b The decomposition of the gate into its two component C₁₃ gate and C₃₁ gate

Fig. 14

The main NM³ library consist of 9 gates (generators)

3.4 Four-Bit Gate

M⁴ gate combines the action of the four gates N,C,T³ and T⁴. It acts on an arbitrary 4-bits x_i,x_j,x_k and x_l in any order. Figure 15 shows the decomposition of the gate, Fig. 15a shows the representation of the ${M}_{1234}^4$, and Fig. 15b shows the decomposition of the ${M}_{1234}^4$ gate into its five components. There 24 gates are sufficient to realize the (2⁴)! reversible circuits. For 4-bits reversible circuits built using M-gate library, there are 24 possible M⁴ gate, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}& {M}_{i,j,k,l}^4& :{y}_i={x}_i\oplus \left({x}_k\oplus {x}_j\right),\\ {}& & \kern1.30em {y}_j=\left({x}_j\oplus 1\right)\oplus \left({x}_k\oplus {x}_j\right)\cdot \Big({x}_i\oplus \left({x}_k\oplus {x}_j\right),\\ {}& & \kern1.30em {y}_k={x}_k\oplus {x}_j,\\ {}& & \kern1.30em {y}_l={x}_l\oplus {y}_i\cdot {y}_j\cdot {y}_k,\end{array}} $$

(11)

$$ {\displaystyle \begin{array}{rcl}{M}_{1,2,3,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,10,14,4,12,8,2,6,15,9,13,3,11,7\right),\\ {}{M}_{1,3,2,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,10,12,6,14,8,2,4,15,9,11,5,13,7\right),\\ {}{M}_{2,1,3,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,6,14,4,8,12,2,10,15,5,13,3,7,11\right),\\ {}{M}_{2,3,1,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,6,8,10,14,12,2,4,15,5,7,9,13,11\right),\\ {}{M}_{3,1,2,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,4,12,6,8,14,2,10,15,3,11,5,7,13\right),\\ {}{M}_{3,2,1,4}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,4,8,10,12,14,2,6,15,3,7,9,11,13\right),\\ {}{M}_{1,2,4,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,11,15,4,12,8,3,7,14,9,13,2,10,6\right),\\ {}{M}_{1,3,4,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,13,15,6,14,8,5,7,12,9,11,2,10,4\right),\\ {}{M}_{2,1,4,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,7,15,4,8,12,3,11,14,5,13,2,6,10\right),\\ {}{M}_{2,3,4,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,13,15,10,14,12,9,11,8,5,7,2,6,4\right),\\ {}{M}_{3,1,4,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,7,15,6,8,14,5,13,12,3,11,2,4,10\right),\\ {}{M}_{3,2,4,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,11,15,10,12,14,9,13,8,3,7,2,4,6\right),\\ {}{M}_{1,4,2,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,11,12,7,15,8,3,4,14,9,10,5,13,6\right),\\ {}{M}_{1,4,3,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,13,14,7,15,8,5,6,12,9,10,3,11,4\right),\\ {}{M}_{2,4,1,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,7,8,11,15,12,3,4,14,5,6,9,13,10\right),\\ {}{M}_{2,4,3,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,13,14,11,15,12,9,10,8,5,6,3,7,4\right),\\ {}{M}_{3,4,1,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,7,8,13,15,14,5,6,12,3,4,9,11,10\right),\\ {}{M}_{3,4,2,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,2,16,11,12,13,15,14,9,10,8,3,4,5,7,6\right),\\ {}{M}_{4,1,2,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,4,12,7,8,15,3,11,14,2,10,5,6,13\right),\\ {}{M}_{4,1,3,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,9,16,6,14,7,8,15,5,13,12,2,10,3,4,11\right),\\ {}{M}_{4,2,1,3}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,4,8,11,12,15,3,7,14,2,6,9,10,13\right),\\ {}{M}_{4,2,3,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,5,16,10,14,11,12,15,9,13,8,2,6,3,4,7\right),\\ {}{M}_{4,3,1,2}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,6,8,13,14,15,5,7,12,2,4,9,10,11\right),\\ {}{M}_{4,3,2,1}^4:\left({x}_1,{x}_2,{x}_3,{x}_4\right)& \to & \left(1,3,16,10,12,13,14,15,9,11,8,2,4,5,6,7\right).\end{array}} $$

where i,j,k and l ∈ {1, 2, 3, 4} in any order.

Fig. 15

The circuit representation for the decomposition of ${M}_{1234}^4$ gate, where: a The gate representation, b The decomposition of the ${M}_{1234}^4$ gate into its five components

3.5 n-Bit Gate

It can be shown using GAP that a permutation group with two generators ${M}_{12}^2$ and ${M}_{21}^2$ is of size 24, i.e. a cascade of these two gates are sufficient to implement any of the 24 2-in/out reversible circuits. It can be shown using GAP that a permutation group with the six generators of M³ is of size 40320, i.e. a cascade of these six gates are sufficient to implement any of the 40320 3-in/out reversible circuits. Extending the M gate for n-bits is trivial as shown in Fig. 16. It can be shown using GAP that a permutation group with the n! of Mⁿ is of size 2ⁿ!, i.e. a cascade of these n! gates are sufficient to implement any of the 2ⁿ! n-in/out reversible circuits. The Mⁿ gate is universal of n-bit gate.

Fig. 16

The circuit representation for the decomposition of ${M}_{1234\dots n}^n$ gate, where: a The gate representation, b The decomposition of the ${M}_{1234\dots n}^n$ gate into its main components

For n ≥ 3, Mⁿ combines the action of the n-gate N,C,T³,T⁴,…,T^n− 1,Tⁿ as shown in Fig. 16. The total number of possible gates for the general Tⁿ is computed in [15] as follows:

$$ n\sum \limits_{r=0}^{n-1}\left(\genfrac{}{}{0.0pt}{}{n-1}{r}\right) $$

(12)

where n is the number of bits and r ≥ 0 is the number of controls per gate. There are n! possible Mⁿ gates which are sufficient to realize any n-bits reversible circuit, that perform as follows:

$$ {\displaystyle \begin{array}{rcl}{M}_{a_1,{a}_2,{a}_3,{a}_4,{a}_5,\dots, {a}_{n-1},{a}_n}^n:{y}_{a_1}& =& {x}_{a_1}\oplus \left({x}_{a_3}\oplus {x}_{a_2}\right),\\ {}{y}_{a_2}& =& \left({x}_{a_2}\oplus 1\right)\oplus \left({x}_{a_3}\oplus {x}_{a_2}\right)\cdot \Big({x}_{a_1}\oplus \left({x}_{a_3}\oplus {x}_{a_2}\right),\\ {}{y}_{a_3}& =& {x}_{a_3}\oplus {x}_{a_2},\\ {}{y}_{a_4}& =& {x}_{a_4}\oplus {y}_{a_1}\cdot {y}_{a_2}\cdot {y}_{a_3},\\ {}{y}_{a_5}& =& {x}_{a_5}\oplus {y}_{a_1}\cdot {y}_{a_2}\cdot {y}_{a_3}\cdot {y}_{a_4},\\ {}& & \dots \\ {}& & \dots \\ {}{y}_{a_{n-1}}& =& {x}_{a_{n-1}}\oplus {y}_{a_1}\cdot {y}_{a_2}\cdot {y}_{a_3}\cdot {y}_{a_4}\dots {y}_{a_{n-2}},\\ {}{y}_{a_n}& =& {x}_{a_n}\oplus {y}_{a_1}\cdot {y}_{a_2}\cdot {y}_{a_3}\cdot {y}_{a_4}\cdot {y}_{a_5}\dots {y}_{a_{n-1}},\end{array}} $$

(13)

where a₁,a₂,a₃,… and a_n ∈{1,2,3,…,n} in any order.

Fig. 17

a The circuit representation for [${M}_{123}^3,{M}_{213}^3$], b Decompose the circuit into Toffoli gates, c Decompose the circuit into its elementary quantum gates, d Optimization is done by applying moving rules, e The optimized decomposition of the circuit[${M}_{123}^3,{M}_{213}^3$] into its 9 elementary gates with QC equal 7

Table 1 Utilization of the different universal libraries

Table 2 Utilization of gates in the smallest universal sub libraries

Given the proposed NM³ gate library with nine generators as shown in Fig. 14 and the 40320 specifications for all 3-in/out reversible circuits. All sub-libraries of NM³ gate library are generated, that is 511 sub-libraries after excluding the identity mapping. Using each sub-library to attempt to synthsize a reversible circuit for the 40320 specifications, if possible, using Schreier-Sims Algorithm. The term “if possible” here means that if a specification does not belong to the group generated by a sub-library, then it is impossible for this specification to be represented as a reversible circuit using this sub-library. The process of synthesizing all possible 3-bit reversible circuits using the proposed NM³ gate is shown in Algorithm 1.

4 Experimental Results

This section discusses and compares the performance of the proposed two gate libraries M³ and NM³, with the known libraries in [12,13,14,15, 18, 25]. It can be shown using GAP [17] that a permutation group of M³ generators is of size 40320, thus the six generators in M³ gate library are universal. There are 64 possible sub libraries from the main M³ gate library, 55 of them are universal for the 3-bits reversible circuits. It can be shown using GAP [17] that a permutation group of NM³ generators is of size 40320, thus the nine generators in NM³ gate library are universal. There are 512 possible sub libraries from the main NM³ gate library, 475 of them are universal for the 3-bits reversible circuits (Fig. 17).

Table 1 compares the utilization of the different libraries, it can be seen that the NM³ gate library gives the utilization of 92.773%, which is better than the utilization of libraries NT, NP, NCT, NCF, NCP, NCTF, NCPT, NCPF, G³, M³, R³ and NR³. The size of the minimum universal sub libraries from the main M³ gate library and NM³ gate library is two. For M³ gate library, there are 12 universal sub libraries of size two, such as $\left\{{M}_{123}^3,{M}_{213}^3\right\},\left\{{M}_{132}^3,{M}_{231}^3\right\}$ and $\left\{{M}_{213}^3,{M}_{321}^3\right\}$. For NM³ gate library, there are 16 universal sub libraries of size two, such as $\left\{{M}_{132}^3,{M}_{321}^3\right\},\left\{{M}_{123}^3,{M}_{213}^3\right\}$ and $\left\{{M}_{231}^3,{M}_{312}^3\right\}$.

Table 2 compares the utilization of gates in the smallest universal sub libraries. The utilization of the universal sub libraries with minimum size for M³ is 86.667%, while for NM³ is 47.222%. It shows that NM³ gives a utilization better than NP, NCT, NCF, NCP, NCTF, NCPT, NCPF and NR³. Table 4 compares the minimum length for the 3-bits reversible circuits using different libraries. It shows that the average minimum length for M³ is 6.425, while for NM³ the average minimum length is 5.325, which is better than NT,NCT,NCF,NCTF,G³,R³ and M³ (Table 3).

Table 3 The proposed Rules of decomposing 3-bit M-reversible circuits

Table 4 Minimum length of 3-bits reversible circuits using using the proposed M³-gate library and the existing work in [25]

Table 4 shows that the minimum length for M³ is 6.42 and the minimum length for NM³ is 5.32. These results are identical with the minimum length for R³ and NR³, but our results are different with the minimum quantum cost. For example, it can be shown using GAP [17] that a cyclic permutation equal (5, 8, 7, 6) can be realized by NR³-based reversible circuit $\left[{N}_1^3,{R}_{231}^3,{R}_{123}^3,{N}_3^3,{R}_{231}^3,{N}_1^3\right]$ with minimum quantum cost equal 12 and minimum length equal 6 as shown in Fig. 18, while the same cyclic permutation equal (5, 8, 7, 6) can be realized by NM³-based reversible circuit $\left[{M}_{231}^3,{N}_1^3,{M}_{123}^3,{M}_{213}^3,{N}_1^3,{N}_3^3\right]$ with minimum quantum cost equal 11 and minimum length equal 6 as shown in Fig. 19.

Fig. 18

The circuit representation for the cyclic permutation equal (5, 8, 7, 6), where: a The NR³-based reversible circuit realize the cyclic permutation b The optimized decomposition of the NR³-based reversible circuit into its 18 elementary quantum gates with QC equal 12

Fig. 19

The circuit representation for the cyclic permutation equal (5, 8, 7, 6), where: a The NM³-based reversible circuit realize the cyclic permutation b The optimized decomposition of the NM³-based reversible circuit into its 17 elementary quantum gates with QC equal 11

The optimization rules will be used to identify and classify similarity of gates among a circuit when decomposed to a sequence of quantum gates. Decomposition of 3-bit reversible circuits can be used to decrease the quantum cost. Optimization is done by removing and/or combing (merging) adjacent gates act on same qubit [23] and applying new decomposition techniques defined in [24]. For example, the cost of the sequence of reversible gates $\left[{M}_{123}^3,{M}_{213}^3\right]$ is 7 instead of 8 as shown in Fig. 17. The first gate is [C₂₃v₃₂], which is merging gate between C₂₃ and v₃₂ in order, as shown in Fig. 12. The fourth gate is[C₃₁C₁₃], which is merging gate between C₃₁ and C₁₃ in order, as shown in Fig. 13. Applying the novel optimization rules as shown in Table 3 to reduce the quantum cost of 3-bit reversible circuits built using M³ gate library.

Table 5 Minimum cost of 3-bits reversible circuits using the proposed M³-gate library and the existing work in [25]

The quantum cost of all the 40320 3-bit reversible circuits synthesized by the M³ and NM³ gate libraries are calculated and compared with different universal libraries as shown in Table 5. For 3-bits reversible circuits built using M³-gate library, the maximum quantum cost is 36 and average quantum cost is 25.70 before optimization. After adding the N gate to the M³-gate library, the maximum quantum quantum cost has been reduced to 24, having an average cost 13.29 after apply optimization rules are shown in Table 3, giving 48.3% of improvement. The quantum cost of the circuits built using NR³-gate library have improved by 44.1% and the quantum cost of the circuits built using NT-gate library have improved by 13.4% [25].

5 Conclusion

The paper proposed a novel reversible n-bit gate that is proved to be universal for synthesizing reversible circuits using the algebraic software GAP. The proposed gate is extendable according to the number of bits in the circuit design and is important as it a single type of gate and using this technology might be cheaper to implement. All experimental results shown in this paper have been obtained using GAP. For 3-bits reversible circuits built using the proposed M³-gate library, it shown that:

• The average minimum quantum cost for reversible circuits based on M³ library is 25.70 with minimum length is 6.403.

• The average minimum quantum cost for reversible circuits based on NM³ library is 13.29 with the minimum length is 5.325. (adding the N gate to the M³-gate library giving 48.3% of improvment).

The reversible circuits based on NM³ library give better results than that the reversible circuits based on NR³ library and NT³ library with respect to the quantum cost. The reversible circuits based on NM³ library give the utilization of 92.773%, which is better than the utilization of different libraries achieved by other in the literature. The analysis of universal sub libraries for the proposed gate to find the optimal sub library with exact minimal number of gates that generate an efficient quantum circuit is an extension to this work.