Tutorial Blog 1 : Basic Concepts of Reversible Circuits ( Quantum Computing)

 Basic Concepts of Reversible Circuits ( Quantum Computing)

                          - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

                      👷 Posted By Souvik Kumar Parui            

 Introduction :

In recent years, the research community has shown considerable intentness towards the reversible logic due to its potential to minimize the power dissipation in the VLSI circuits to design a power efficient circuit. The reversible logic holds the key feature of designing the information lossless circuits and it may lead to zero-energy dissipation in the ideal case.  
 

Reversible Logic : 

                   A function is called reversible if it has equal numbers of inputs and outputs and there exists a bijective mapping between them. Reversible functions are used to implement the reversible circuits.

     Example  : Let us consider a function (x1, y1) → (x1, x1 ⊕ y1) is said to be a reversible function as the function has two inputs and two outputs and also it can be observed from Table below that inputs and outputs are bijectively mapped.

Reversible Logic Circuits : 

                         A reversible circuit is implemented only with reversible gates and it also satisfies the basic feature of reversible function. A reversible circuit is also fan-out free. 

           Constant Input :  If an input of a reversible circuit is always set to a fixed value, then the input is known as constant input. 

           Garbage Output : The extra outputs that are attached to the circuit to satisfy the condition of the reversibility of the given function are called garbage outputs of the circuit. 

  Example : The use of constant input and garbage output in reversible function is explained in the following example. 

  Consider a function f=x1.y1 which denotes the logical AND operation. It can be observed from the Table below 2.2 that the function is not satisfying the condition of reversibility. But the AND function can be converted into reversible by attaching one more input (constant input) and two additional outputs (garbage outputs). The new form of the given function f can be realized as f=z1 ⊕ x1y1, where z1 is set to constant zero and outputs x1 and y1 work as “garbage” output shown in Table 2.3 . 

 Reversible Logic Gates :

       A reversible gate is constructed with control lines (CL) and target lines (TL) only. At the gate, set CL may be empty, but TL must contain at least one target line where CL∩TL = Φ.  

      Toffoli Gate :

       k-control Toffoli gate:  A generalized -CNOT gate has a set of control inputs X1, X2, X3,…., and only a single target input T. The input and output combination can be represented as (X1,X2,X3,…Xk,T)→(X1,X2, X3,…,Xk,T⨁X1,X2,X3..Xk). It shows that at the control lines, the outputs are same as inputs. The target input T is complemented when all the control nodes are set to 1. A -control Toffoli gate is shown in below. 

         

        NOT gate:   A reversible gate with only the target input (T) and no control input ( k= 0) is known as  NOT gate. 

      

     CNOT gate:  Similarly, a reversible gate with target input and one control input is termed as controlled NOT (CNOT) gate. It maps the input/output vector as (x1,T)→(x1,T⨁x1). 

   2-controlled Toffoli gate:  A reversible gate with two control inputs and the target input is known as 2-controlled Toffoli gate. It is represented as (x1,x2,T)→(x1,x2,T⨁x1.x2). 

Pictorial representation and truth table of some other reversible gates are also given below. 

 Fault Models : 

          Several fault models (SMGF, RGF, PMGF, MMGF) for k−CNOT based reversible circuits have been explained in details in the below section. 

      Single missing-gate fault (SMGF) : Missing of an entire k-CNOT gate from the circuit is called SMGF which changes the functionality of the circuit. 

An SMGF is observed in Fig. where entire 2-CNOT (denoted by the dotted box) gate is missing from the circuit. An SMGF can be detected by setting 1 to all the control nodes of the gate and any value (0 or 1) to other nodes of the gate. In Fig. the test vector <a, b, c> = <0, 1, 1> is applied to the circuit to detect the identified SMGF in the circuit.  

     Repeated-gate fault (RGF) :  An unwanted repetition of a k-CNOT gate by several instances of the same gate is known as RGF.  

An example of RGF, denoted by the dotted box is shown in Fig. below, From the example, it can be seen that the first 2-CNOT gate is repeated for two instances to occur an RGF in the circuit and makes the circuit faulty one. Here, the test vector <a, b, c> = <0, 1, 1> detects the RGF in the circuit. 

 

     Partial missing-gate fault (PMGF) :

         Missing of the existing control node from a k-CNOT gate is termed as PMGF. A PMGF can be of (k − p)th order, where k is the total number control nodes of the gate and p is the number of control nodes which are missing in the gate. 

 
A PMGF is shown in Fig. below where the second control input (denoted in the dotted box) of 2-CNOT gate is disappeared to cause a PMGF. The detection condition of PMGF is to set 0 to one of the mistuned control nodes and 1 to all other control nodes. So, the located PMGF can be detected by the vector <a, b, c> = <0, 0, 1>.  
 

   Multiple missing-gate faults (MMGF) : 

     Missing of more than one consecutive k-CNOT gates from the circuit is called MMGF.  
In Fig. an MMGF is denoted by the dotted box. Here, first two gates are disappeared from the circuit to cause an MMGF which is identified by the vector <a, b, c> = <0, 1, 1>.

    Posted By : Souvik Kumar Parui

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------