1 Introduction

Energy loss is a significant constraint in digital circuit design. It is involved in each phase of design cycle starting from the logic level to the technological level of development. Since the evolution of electronic devices, starting from the centimeter scale vacuum tubes to the present nanometer scale CMOS: the minimization of power dissipation, lowering the size and enhancing the speed are major challenges in the pursuit of cutting-edge technology. Higher degree of on-chip integrated circuits and type of fabrication processes have dramatically reduced the energy levels over the last decades. Today, we have achieved in reducing the size to some nanometers scales providing clock speed more than 3 GHz. But if we further minimize the size, we have to compensate with speed and power dissipation. This statement limits the evolution of Moore’s law and it may saturate by 2020 [46]. Another factor of power dissipation is the loss of information as highlighted by Landauer [45]. According to this, every bit loss in logic circuits is involved in a loss of \(k_BT\ln 2\) Joules of heat in the environment, where \(k_B\) is Boltzmann’s constant and T is the absolute temperature at which operation is performed. For instance, the heat dissipation per bit is \(2.9\times 10^{-21}\) Joules [45]. However, it is very small but cannot be ignored where the rate of the processor frequency is very high. This problem propel the engineers and researchers to develop such a logic that does not involve information loss. It is possible only by the inclusion of reversible gates in logic design process. Quantum computation is also known for saving power on the top of several emerging technologies like trapped ion, magnetic resonance etc. Moreover, all the quantum computation are inherently reversible in nature [59].

Reversible logic is one of the promising techniques to reduce the power requirements, as these circuits are theoretically claimed for producing nearly energy free computation systems by preserving the loss of information [6]. These circuits have the capability of producing ultra high speed and compact electronic devices [59]. However, the logic can be applied to traditional logic circuits [93], but its applications to quantum computation have been proven for achieving excellence in terms of power consumption, speed and size. The identification and implementation of reversible quantum circuits have been achieved using several probabilistic methods and ideas [5, 15, 59, 70, 91]. Figure 1 shows some dominating technologies where the researchers are currently exploring the possibilities for employing this logic at physical foregrounds [13, 43, 64, 73, 81].

Fig. 1
figure 1

Computing technologies

Full size image

The construction of reversible logic circuits design and synthesis techniques [14, 22, 26, 31, 48, 55, 65, 66, 78, 79, 92] are based on fundamental Toffoli and Fredkin gates [18, 19, 86]. These gates can be further extended to nth order gates, known as Multiple Control Toffoli (MCT) and Multiple Controlled Fredkin (MCF) gate libraries. Numerous other reversible gates have also been proposed in the literature [7, 32, 33, 39,40,41, 52, 63, 71, 74, 75, 77, 82, 84], but the primary components of these gates are MCF and MCT [28]. Moreover, the final quantum decomposition of the reversible circuits are based on them. The efficiency of the designs are governed by several performance metrics defining their operating cost. These metrics are wires, gates, quantum stages and garbage [50].

2 The Logic

Currently, all digital logic circuits are physically irreversible because they comprise of irreversible gates. The energy provided by the source is eventually converted into heat with every bit loss. For example, there is a loss of a bit per clock in a two input AND gate as shown in Fig. 2a. Moreover, irreversible logic does not traverse the state sequences in the reverse direction to achieve the initial state after the completion of logical functions. In the I/O of AND gate shown in Table 1, the output permutation is 0 for three input permutations 0, 1 and 2. The output cannot be unique because there are only two logic states (0 and 1) where at least two output will be same, the reverse computation cannot be achieved. The statement cannot be true number of inputs greater than the number of permutations. Hence, there should be same number of inputs and outputs. For two inputs there will be two outputs as shown in Fig. 2b. But assuming two output will not provide the solution. Consider the example circuit of \(2\times 2\) AND gate shown in Fig. 2c whose I/O is listed in Table 2. Here, again the output permutation is 0 for two input permutations 0 and 1. There is a need to develop a logic to settle this situation, where we can conserve output bits.

Fig. 2
figure 2

Irreversible computation

Full size image
Table 1 I/O of AND gate
Full size table
Table 2 I/O of 2 \(\times \) 2 AND gate
Full size table

In this situation, information lossless computing presents an option, where a logical operation does not yield loss of information called reversible operation. There are two approaches to attain reversibility; they are logical and physical reversibility. The first one corresponds to the bijective relation between inputs and outputs, so inputs can be inferred from the outputs [45]. The later means that there must be some conditions for computation in reverse order [6]. Logical reversibility can be achieved by following two different criteria. First, when intermediate information’s are retained during computation from input to output. Here, the reverse computation can be obtained in backward direction, i.e., from output to input by considering the retained information. Second, when logical reversible gates are used for computation without storing intermediate results. However, logical reversibility in turn implies physical reversibility which bards the dissipative effects in computation process. For a computation to be physically reversible, it must be logically reversible. The unsuspecting erasure of a bit of information must always incur a cost of \(k_BT\ln 2\) in thermodynamic entropy in irreversible computation. Hence, reversible logic entails the reduction of increment in physical entropy by saving the input information and prevent the information loss in the form of heat to the environment.

Fig. 3
figure 3

Reversible computation

Full size image
Table 3 I/O of 2 \(\times \) 2 XOR gate
Full size table

Consider the example circuit of 2 \(\times \) 2 XOR gate shown in Fig. 3a. Its I/O listed Table 3 shows the same results as required for a reversible \(2\times 2\) function where there is a unique correlation between input and output permutations called as bijectivity or logical reversibility. Moreover, it can also be observed from Table 3 that, if the output is again used as an input, which results in original input permutation, called as physical reversibility. For instance, for input permutation 2 the output is 3 and if we use 3 as an input permutation, the output is the original input permutation i.e. 2.

The mathematical equivalence circuit of 2 \(\times \) 2 XOR gate shown in Fig. 3b. Its corresponding reversible/quantum representation is shown in Fig. 3c, which is called as reversible Controlled NOT (CNOT) gate. It is having a control input k and target output T. The output function f(k, T) is controlled by the input k. For instance, if \(k=0\), \(f(k,T)=T\) and if \(k=1\), \(f(k,T)=\overline{T}\), i.e., controlled NOT operation. The concept was very theoretical in the beginning. Many mathematical equations were used to prove its feasibility and strengths. Since the past two decades, this topic drew more attention and improved in design, synthesis and testing. Mainly, there are two categories of current research in this area, physical implementation and designing where a number of research groups in leading research labs around the globe are working.

2.1 Reversible Function

A Boolean function produces p outputs \((y_1,y_2,\ldots ,y_p)\) with respect to n inputs \(x_1,x_2,\ldots ,x_n\), where the output y is the function of inputs \(y_p=f(x_1,x_2,\ldots ,x_n)\). A Boolean logic function with n variables is reversible if it generates unique output for each input permutations [86]. The necessary conditions for a Boolean function with n variables to be reversible can be stated as:

  • The number of inputs and outputs should be equal.

  • There should be bijective mapping between input and output.

2.2 Reversible Gates

A reversible gate recognizes a reversible function. If a \(n\times n\) input output gate produces distinct output for its distinct input functions, it is called as \(n\times n\) reversible gate. The basic building blocks for designing any functional circuits are the logic gates and synthesis schemes based on them. Alike irreversible AND, OR and NOT logic gates, there are two fundamental Controlled NOT and Controlled SWAP reversible gates. These gates are commonly known as Toffoli and Fredkin gates, which are further extended into \(n\times n\) gates which form Multiple Control Toffoli (MCT) and Multiple Controlled Fredkin (MCF) gates libraries.

Multiple Controlled Toffoli

An MCT gate has m control inputs \((k_1,k_2,\ldots ,k_m)\) and one target input T to form \(\big (m+1\big )\times \big (m+1\big )\) reversible Boolean function. The control input directly mapped to their respective outputs and the function \(f(k_m,T)\) is given by Eq. 1. The illustration is also provided in Fig. 4a. A \(3\times 3\) gate shown in Fig. 4b is called a Toffoli gate. The least member of this family shown in Fig. 4c is known as a NOT gate, whose output is inversion of the input applied to it.

$$\begin{aligned} f(k_m,T)=(k_1\cdot k_2\cdot \ldots k_m)\oplus T \end{aligned}$$
(1)
Fig. 4
figure 4

Schematic representation of MCT gates

Full size image
Fig. 5
figure 5

Schematic representation of MCF gates

Full size image

Multiple Controlled Fredkin

An MCF gate has m control inputs \((k_1,k_2,\ldots ,k_m)\) and two target inputs \(T_1\) and \(T_2\) to form a \(\big (m+2\big )\times \big (m+2\big )\) reversible function as depicted in Fig. 5a. The gate passes all the control inputs directly to respective outputs and the target outputs \(f_1(k_m,T_1,T_2)\) and \(f_2(k_m,T_1,T_2)\) are given by Eqs. 2 and 3 respectively. Here, \(k_{PR}=k_1\cdot k_2\cdot \ldots \cdot k_m\). A \(3\times 3\) gate shown in Fig. 5b is called a Fredkin gate, whose respective outputs are given by \(f_1(k,T_1,T_2)=\overline{k}T_1+kT_2\) and \(f_2(k,T_1,T_2)=kT_1+\overline{k}T_2\). The least member of this family is shown in Fig. 5c is known as a SWAP gate which interchange its applied target inputs at the outputs.

$$\begin{aligned} f_1(k_m,T_1,T_2)=\overline{k_{PR}}\cdot T_1+k_{PR} \cdot T_2 \end{aligned}$$
(2)
$$\begin{aligned} f_2(k_m,T_1,T_2)=k_{PR}\cdot T_1+\overline{k_{PR}}\cdot T_2 \end{aligned}$$
(3)

Others

There are many n I/O gates has been projected in the last two decades other than fundamental MCT and MCF gates, [7, 32, 33, 39,40,41, 52, 53, 63, 71, 74, 75, 77, 82, 84], which are projected for special functions efficiently. The purposes includes universality, addition, parity preservation etc. The schematics of some popular \(3\times 3\) and \(4\times 4\) gates are shown in Table 4, where the inputs {A, B, C} and outputs {P, Q, R} are revealed. The schematics of some popular \(4\times 4\) gates are shown in Table 5, where the inputs {A, B, C, D} and respective outputs {P, Q, R, S} can be seen. The gates Peres, R and URG are known for their universality. TR, TSG and PAOG gates are projected for addition purposes. The gates SMS, R1, OTG and PPRG are having parity preservation and generation capabilities which can be used for testability purpose. The properties of nearly all commonly used \(3\times 3\) and \(4\times 4\) gates are summarized and analyzed at two significant experimentation levels in [28].

Table 4 Input-output of 3 \(\times \) 3 gates
Full size table
Table 5 Input-output of 4 \(\times \) 4 gates
Full size table

2.3 Fundamental Properties of Reversible Gates and Circuits

Depending on the functionality of reversible gates, they can be categorized into two different classes:

  • Conservative: The gates which retain the number of logic values from the input to output are known as conservative gates. In other words, the number of 1s and 0s are same at both ends of the circuit.

  • Parity preserving: The gates in which the sum of logic 1s in their inputs and outputs are even are called parity preserving gates. Scientifically, the exor of all inputs and outputs result a null value. If these properties are closely analyzed it can be concluded that the conservative gates are parity preserving but vice-versa is not always correct.

Fig. 6
figure 6

Reversible circuits

Full size image

The construction of all reversible logic circuits design and synthesis techniques are based on fundamental MCT and MCF gates. Since the operations in reversible logic circuits are linear, i.e., all the outputs of one gate stage varies the operations of next gate stages. The input signal is once propagated from the input, will not be taken back and cannot be taken as inputs to multiple gates and there is no loss of logic bits which maintains the information entropy. The synthesis of reversible circuits is restricted to ‘FANOUT’ and ‘FEEDBACK’. In reversible circuits, these factors are not allowed [6, 59]. It results in the only condition to form a reversible circuit by means of cascading reversible gates, Fig. 6a, b, c illustrated the three reversible circuit networks by using MCT, MCF and MCTF gates respectively.

2.4 Cost Metrics

In designing reversible circuits, certain cost measures has been considered to evaluate the efficacy of proposed methodologies. These measures are can be considered as operating cost of the circuits [23, 24, 50]. A brief explanation and respective illustration using a reversible full adder (rd32 benchmark circuit [16] shown in Fig. 7) of these metrics is given as follows:

Fig. 7
figure 7

Reversible full adder

Full size image
Fig. 8
figure 8

Schematic of reversible full adder

Full size image

Gate Cost:

The number of gates required to construct a circuit refer its gate count. It is a direct measure to calculate the cost of a circuit, which is commonly called as gate cost (GC). The number of gates used to construct a full adder shown in Fig. 7 are four, hence its gate cost is equal to 4.

Quantum Cost:

A complete reversible circuit can also be realized in corresponding quantum realization using elementary quantum gates (\(1\times 1\) NOT, \(1\times 1\) CNOT, Control V and Control V\(+\)). The sum of these elementary quantum gates are termed as quantum cost (QC) of the circuit. The full adder (Fig. 7) can be decomposed using twelve quantum gates as shown in Fig. 8, hence its quantum cost is 12.

Ancilla Input:

There are the requirement of additional constant inputs to convert an irreversible into reversible circuit. These additional inputs are referred as ancilla inputs (AI). The last input is taken as constant 0 to construct SUM and CARRY functions as shown in green colour in Fig. 7, hence number of ancilla input is 1.

Input:

The number of inputs directly impact on the qubits in a reversible circuit and increases the size of the circuit. These number of input or wires (n) including ancilla input can also be taken to evaluate the performance of any design methodology. There are four wires needed to implement a full adder circuit shown in Fig. 7, hence \(n=4\).

Garbage Output:

To maintain the bijectivity property in the realization of reversible circuits, some outputs are left unused. These outputs are referred as garbage outputs (GO). It can be seen that, two output are left unused to realize a full adder circuit depicted in Fig. 7, written as garbage in red colour. Hence GO for this circuit is 2.

The discussed parameters show a direct connection with area/size and complexity of a circuit. The more values of these parameters raise the size and complexity and enhance the power dissipation and physical cost of circuits and devices. Hence the minimization of these measures should be the major subject all through the development of design and test strategy for reversible logic circuits. The quantum cost has a proportionate association with delay, while ancilla inputs are the extra source of input power and garbage depicts the loss of power. Moreover, there are some technology-dependent measures are also exist like input to output delay which can be used to compute the speed.

3 A Door Step Towards Quantum Computation

A traditional computer circuits comprised of wires and logic gates, where the wires transfer the information which is further manipulated by logic gates to perform some operations. In quantum computers, the information is switched with the help of change in quantum states. These states are defined using linear combinations, called as superposition for a single qubit system as given in Eq. 4. Where, \(\alpha \) & \( \beta \) are the two complex numbers and \(|0\rangle ,|1\rangle \) shows the Dirac notations of the two states.

$$\begin{aligned} |\psi \rangle =\alpha |0\rangle +\beta |1\rangle \end{aligned}$$
(4)

Out of the infinite quantum information space (Hilbert Space) in the superposition, there are two quantum states \(|0\rangle \) and \(1\rangle \) that can be easily recognizable for performing any operation. These states refers the ground state and excited state of electrons in an atom respectively, as demonstrated in Fig. 9. The qubit is once propagated from the input will not be taken back and cannot be taken as inputs to multiple stages in a quantum system.

Fig. 9
figure 9

qubit representation as two electronic levels

Full size image

A quantum circuit contains elementary quantum gates to hold and manipulate the quantum information. The smallest (and trivial) member of this family is elementary NOT gate whose functionality is as usual. Rather than a truth table, these gates are represented in form of a matrix, which pursue the linearity of quantum gates. Controlled NOT, Z, H, SWAP are the elementary quantum gates that can be derived to multiple qubit gates. Similar to reversible gates a quantum controlled NOT gate used to invert a state and SWAP gate is used to interchange any two states. The change of states in quantum NOT gate can be given by \(\alpha |0\rangle +\beta |1\rangle \rightarrow \alpha |1\rangle +\beta |0\rangle \). The swap and copy operations are process for minimum of two qubit system. The archetypal multi-qubit quantum gates are controlled NOT gates, similar as that of reversible MCT and MCF gates and all the quantum operations are inherently reversible in nature.

Hence, regardless of the physical implementation, the research in design and synthesis of reversible logic circuits will be the foundations of quantum computers. The implementation of reversible logic will be formulated in conjunction with quantum technology. The full scope of potential technologies has not been imagined yet nor it will be, until definite quantum information hardware is obtainable for future generations of computation. The reversible logic designs and synthesis methods are independent of the implementation technique. Once the implementation becomes more stable for fabrication, the design can be set into a real hardware device.

4 Summary of the Chapter

However, physical implementation is limitedly experimented, a healthy research has been accomplished in the area of reversible logic circuits. Following are the key points that are discussed in this chapter:

  • Description of the theory of reversible logic

  • Basis definitions and notations

  • Explanations of reversible gates and their properties

  • Explains all the cost metrics used for analysis

  • Efficacy of Toffoli and Fredkin gates for reversible and quantum circuit implementations ihas been emphasized

  • Connections of reversible logic with quantum computation