1 Introduction

Recently, quantum computation has received a lot of attention and interest and has become one of the focal points of theoretical and experimental research. One of the important features of quantum computing is reversibility.

Landauer [1] discovered that the process of erasing information produces heat dissipation. The amount of energy dissipated per bit is equal to K B T ln2 where K B the Boltzmann’s constant and T the absolute temperature of the environment. This result was obtained for circuits based on classical gates. Bennet [2] showed that this heat dissipation would not occur if the computation is carried out in a reversible way. He proposed that in order to avoid the problem of the energy dissipation, the logic circuit must be built with reversible logic gates. Theoretically we expect that in a classical computer built with reversible gates there no heat loss. A reversible gate is an n-input n-output circuit (denoted by n*n) such that there is a one to one mapping between the input and output values. In other words it is always possible to uniquely recover the input values once the output values are given. A reversible logic based on reversible circuits is a promising area of research which has extensive applications in futuristic technologies such as quantum computation, optical information processing, DNA computing etc. [3]. There are some optimization parameters which have a direct influence of the performance and the speed of the reversible circuit. These parameters include the quantum cost [4–7], the quantum delay [8–10] and the garbage outputs [11–13]. The main challenges in digital design are reducing these parameters.

The network quantum cost (QC) is the sum of the quantum cost of all gates. The quantum cost of a gate is the number of the elementary quantum operations required to realize the function given by the gate. The quantum cost is an important indicator in evaluating the performance of a reversible circuit [14]. The quantum delay (QD)is the maximum number of gates in a path from any input line to any output line.

The unused output of a reversible gate is called garbage output (GO). Garbage outputs are needed to ensure the reversibility of the gate but do not perform any useful operations. In quantum computing, information is not manipulated as in the classical way as a series of zeros and ones called bits, but as a continuous superposition of bits. Such superposition is called quantum bits or qubits.

In this paper we construct reversible arithmetic logic unit (reversible ALU) that is a part of a programmable reversible computing device such as a quantum computer by using the quantum full adder completed double Peres gate [14].

Recently, reversible ALUs, which form the essential component of a computing system, have been designed in binary as well as ternary logic as in [15–25], where cost parameters such as number of garbage outputs (G O), quantum cost (Q C) and quantum delay (Q D) are considered for optimization.

The goal of this article is to build a multi-functional circuit that conditionally performs one of several possible arithmetic-logical operations on two operands depending on control input data instructions.

This paper is organized as follows; Section 2 gives an overview of the basic reversible logic gates used to construct adder circuit. In Section 3 we present a reversible full adder based on a double Peres gate. In Section 4 a novel design of reversible ALU is presented. The performance of this ALU and comparison with the existing ones are provided in Section 5. Finally Section 6 concludes the paper.

2 The Basic Reversible Gates

There are a number of commonly used reversible logic gates such as Feynman gate [26], Toffoli gate [27], Fredkin gate [28] and Peres gate [14]. NOT gate is represented in Fig. 1. Since it is a 1x1 gate, its quantum cost is zero.

Fig. 1
figure 1

Not gate

Full size image

In simple terms, the quantum cost of a reversible gate can be calculated by counting the number of V,V +and CNOT gates used in implementing it, except in few cases. The V and V + quantum gates have the following properties:

$$\begin{array}{@{}rcl@{}}V\ast V=NOT \end{array} $$
(1)
$$\begin{array}{@{}rcl@{}} V\ast V^{+}=V^{+}\ast V^{+}=I \end{array} $$
(2)
$$\begin{array}{@{}rcl@{}} V^{+}\ast V=NOT \end{array} $$
(3)

A 2x2 Feynman gate, also known as controlled-NOT (1-CNOT), is depicted in Fig. 2. Its outputs are P = A and Q = A ⊕ B. The quantum representation of Feynman gate is a 2 × 2 gate, it has a QC and QD of 1 and 1 Δ respectively Fig. 3a shows a 3 × 3 Toffoli gate in which two of the three outputs (P and Q) are same as two inputs (A and B). Toffoli gate can be treated as universal gate in view of the fact that it is the fundamental gate to be used to realize any 3 × 3 gate. Logical AND operation can be obtained through the third output by making third input C equal to zero. Implementation of Toffoli gate using quantum gates is shown in Fig. 3b, which shows that its QC and QD is equal to 5 and 5 Δ respectively.

Fig. 2
figure 2

Feynman gate

Full size image
Fig. 3
figure 3

(a) Toffoli gate and (b) its quantum implementation

Full size image

A 3 × 3 Fredkin gate is shown in Fig. 4a. Here the input A is passed as first output. Inputs B and C are swapped to get the second and third outputs, which is controlled by A. If A = 0, then the outputs are simply duplicates of the inputs; otherwise, if A = 1, then the two input lines (B and C) are swapped. Figure 4b shows its quantum implementation. Note that, each dotted rectangle in Fig. 4b is equivalent to a 2 × 2.

Fig. 4
figure 4

(a) Fredkin gate and (b) its quantum implementation

Full size image

Feynman gate and so the quantum cost of each dotted rectangle is 1. Hence the QC of Fredkin gate consisting of two dotted rectangles, one V gate and two CNOT gates is 5 and its QD is 5 Δ Fig. 5a shows the Peres gate and Fig. 5b its quantum implementation. The QC and QD of the Peres gate is 4 and 4 Δ respectively, since it requires two V+ gates, one V gate and one CNOT gate for its implementation. In the existing literature, among the 3 × 3 reversible gates, Peres gate has the minimum quantum cost.

Fig. 5
figure 5

(a) Peres gate and (b) its quantum implementation

Full size image

If the third input C is equal to zero, this gate can be used as an AND gate through the output R in addition to the XOR function from output Q.

3 Reversible Full Adder

There have been existed a lot of reversible full adder circuits in the literature [29–33] We use Double Peres gate (DPG) [34], which is a combination of two Peres gates as shown in Fig. 6, and his truth table in Table 1. The quantum cost of this full adder is found to be 8 The full adder produces two parts, called a sum (S) and carry (C)

Fig. 6
figure 6

Reversible full adder based on double Peres gate

Full size image
Table 1 Truth table of full adder based on double Peres gates
Full size table

From the truth table, for computing Sum and Carry out (C o u t ), some equations can be obtained as followed

$$\begin{array}{@{}rcl@{}}C_{out}&=&\left( A\oplus B \right)C_{in}\oplus AB \end{array} $$
(4)
$$\begin{array}{@{}rcl@{}} Sum&=&A\oplus B\oplus C_{in} \end{array} $$
(5)

In order to design reversible ALU, we assume the two n-bit argument as A i = (A 1 A 2 A 3…A n ) and B i = (B 1 B 2 B 3…B n ). Let C i be the ith bit of carry and S i be the ith bit of sum. Some equations can be obtained as followed according to (4) and (5).

$$\begin{array}{@{}rcl@{}}C_{i}&=&(A_{i}\oplus B_{i})C_{i-1}\oplus A_{i}B_{i} \end{array} $$
(6)
$$\begin{array}{@{}rcl@{}} S_{i}&=&A_{i}\oplus B_{i}\oplus C_{i} \end{array} $$
(7)

A 4-bit reversible adder is cascade by the reversible full adder shown in Fig. 6. It is summarized here as Fig. 7.

Fig. 7
figure 7

Reversible 4-bit adder based on Peres gate

Full size image

4 The Design of Reversible Arithmetic Logic Unit

ALU is a data processing component, which is an important part in center process unit (CPU). Different kinds of computers have different ALUs. But all of the ALUs contain arithmetic unit and logic unit, which are the basic structures. In arithmetic operations there are add, minus, while in logical operations there are NOT, OR, AND, XOR and so on. The above operations can be realized by using reversible logic gates, through which can avoid the energy consumption.

In this paper, the multi-function ALU (see Fig. 8) based on reversible logic gates has been designed which contains the reversible control unit and the reversible full adder. The reversible control unit and the reversible full adder are cascaded and arbitrary bit reversible ALU modules can be realized by this way. The A and B inputs of the reversible control unit are altered depending on the S0…S 6 values and applied as input to reversible full adder using Double Peres gates. By controlling one of the inputs to adder, various arithmetic and logic operations can be realized. The designed circuit has 7 control signals with a provision for realizing 28 arithmetic and logic operations.

Fig. 8
figure 8

The proposed reversible 4-bit ALU

Full size image

The proposed reversible ALU produce in their ith result (R i ) the general expression:

$$\begin{array}{@{}rcl@{}} R_{i}&=&\overline{S_{6}}\left[ \left( A_{i}\oplus S_{2} \right)\oplus \left( B_{i}\oplus S_{1} \right)\oplus S_{3}C_{i-1}\oplus S_{4}\left( A_{i}\oplus S_{2} \right)\oplus S_{5} \right]\oplus\\ &&S_{6}\left[ S_{0}\oplus \left( A_{i}\oplus S_{2} \right)\left( B_{i}\oplus S_{1} \right)\oplus S_{3}C_{i-1}\left( (A_{i}\oplus S_{2})\oplus (B_{i}\oplus S_{1}) \right) \right] \end{array} $$
(8)

4.1 Reversible Arithmetic Operations

Depending on the (8) can obtain (6) and (7). Necessary for addition operation.

When we set S 3 = 1 (true) and the rest of control inputs equal to 0 (false) the ALU generates the Sum as result

$$ R_{i}=A_{i}\oplus B_{i}\oplus C_{i-1}=S_{i} $$
(9)

When we set S 3 = S 6 = 1 and the rest equal to zero. The ALU generates the Carry as result

$$ R_{i}=A_{i}B_{i}\oplus C_{i-1}\left( A_{i}\oplus B_{i} \right)=C_{i} $$
(10)

For subtraction we set S 2 = S 3 = S 5 = 1 and the rest of control inputs equal to 0 the ALU generates the difference A − B (D i ) as result

$$ R_{i}=A_{i}\oplus B_{i}\oplus C_{i-1}=\overline{\overline{A_{i}}\oplus B_{i}\oplus C_{i-1}}=D_{i} $$
(11)

When we set S 2 = S 3 = S 5 = S 6 = 1 and the rest of control inputs equal to 0 the ALU generates the borrow C i as result

$$ R_{i}=\overline{A_{i}}B_{i}\oplus C_{i-1}\left( \overline{A_{i}}\oplus B_{i} \right)=C_{i} $$
(12)

There are other 10 arithmetic operations when we change the control inputs as summarized in Table 2

Table 2 Selected operations resulting of the proposed ALU
Full size table

4.2 Reversible Logic operations

Depending on the (8) when we set S 4 = S 5 = 1 and the rest of control inputs equal to 0 the ALU generates logic operation (AND), when we set S 0 = S 1 = S 2 = S 6 = 1 and the rest equal to 0 the ALU produces (OR) and when we set all control inputs equal to 0 (except S 4 = 1) the ALU produces B (no operation), see Table 2. There are other 9 logic operation which are summarized in Table 2.

5 The Performance Analysis of the Proposed Reversible 4-bit ALU

A 4-bit reversible arithmetic logic unit was presented in [17] and it is based on the Van Rentergem adder. This 4-bit ALU produced 10 operations, having a QC of 78, QD of 57 Δ and GO of 0. Another design of ALU was presented in [25] which can produce 19 operations is better than [18] but the 4-bit ALU requires at least the QC of 120, QD of 65 Δ and GO of 18. In [35] three designs of 1-bit reversible ALU are presented. We choose for the sake of comparison the design 2 because it has the best results. Depending of 1-bit ALU results we can conclude that the 4-bit of [35] produces 10 operations with the number of QC, QD and GO are 48, 48 Δ and 0 respectively.

The proposed design can produce 28 operations and requires at least QC, QD and GO of 95, 40 Δ and 7 respectively. These results are summarized in Table 3.

Table 3 Comparative results of different reversible 4-bit ALU
Full size table

In order to compare this work with the previous ones we must select the points of comparison. The first point is the number of operations of the design; this number must be big compared to existing design The second point is the optimization of the circuit parameters QC, QD and GO which have to be low compared to the previous designs. To achieve both of the two points we introduce the improvement factor (I f) which is defined as follows:

$$ If=\frac{number~of~operations}{Q~cost+Q~delay+Q~garbage} $$
(13)

The design 4-bit ALU in [18, 20, 23, 25, 35] and [24] has the I f equal to 0.074, 0.094, 0.104, 0.045, 0.057 and 0.056 respectively. The proposed design has the I f equal to 0.197. Hence the percentages of improvement of the proposed design over [18, 20, 23, 25, 35] and [24] are 166, 109, 89, 338, 245 and 252% respectively. The results are summarized in Table 4.

Table 4 Improvement percentages of the proposed design over existing designs
Full size table

For more explanation of 4 bit reversible ALU given by Fig. 8 we present a new figure (Fig. 9) where we depict one primary circuit of 1 bit (for example i = 2) with the explicit output for each step of calculation.

Fig. 9
figure 9

The proposed 1-bit ALU (e x e m p l e i = 2)

Full size image

6 Conclusion

This work presents the complete design of a 4-bit reversible arithmetic logic unit (ALU) that can be part of a programmable reversible computing device such quantum computer. We provide explicit construction of this quantum ALU that performs various arithmetic and logic operations such as addition, subtraction, AND, NAND, OR, NOR, XOR, NOP, Negation. This ALU is designed using double Peres adder and can perform up to 28 logic and arithmetic operations

We have compared the proposed design with the existing designs in terms of the quantum cost, quantum delay, garbage outputs and the number of operations.

The proposed ALU could handle more operations and has better performance in terms of quantum delay, quantum cost and garbage outputs as compared to some existing designs.

The implementation of the proposed ALU design favors low delay and high logical calculation output, which are desirable for realization of a reversible central processing unit.

For a complete realization of reversible computer architecture with the help of the proposed design, more fundamental elements must be designed. These include a reversible control unit and a new approach to reversible memory.