Deutsch–Jozsa algorithm

The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It is also a deterministic algorithm, meaning that it always produces an answer, and that answer is always correct.

Problem statement

In the Deutsch-Jozsa problem, we are given a black box quantum computer known as an oracle that implements some function $f:\{0,1\}^{n}\rightarrow \{0,1\}$. In layman's terms, it takes n-digit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all outputs or 1 on all outputs) or balanced (returns 1 for half of the input domain and 0 for the other half); the task then is to determine if $f$ is constant or balanced by using the oracle.

Motivation

The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. The motivation is to show a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need a large number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different.

Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.

Classical solution

For a conventional deterministic algorithm where n is number of bits, $2^{n-1}+1$ evaluations of $f$ will be required in the worst case. To prove that $f$ is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (remembering that the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values that happen to be selected are different. For a conventional randomized algorithm, a constant $k$ evaluations of the function suffices to produce the correct answer with a high probability (failing with probability $\epsilon \leq 1/2^{k-1}$). However, $k=2^{n-1}+1$ evaluations are still required if we want an answer that is always correct. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation of $f$.

History

The Deutsch–Jozsa Algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case.
Specifically we were given a boolean function whose input is 1 bit, $f:\{0,1\}\rightarrow \{0,1\}$ and asked if it is constant.

The algorithm as Deutsch had originally proposed it was not, in fact, deterministic. The algorithm was successful with a probability of one half. In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takes $n$ bits for its input. Unlike Deutsch's Algorithm, this algorithm required two function evaluations instead of only one.

Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al., resulting in an algorithm that is both deterministic and requires only a single query of $f$. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.

The Deutsch–Jozsa algorithm provided inspiration for Shor's algorithm and Grover's algorithm, two of the most revolutionary quantum algorithms.

Algorithm

For the Deutsch–Jozsa algorithm to work, the oracle computing $f(x)$ from $x$ has to be a quantum oracle which doesn't decohere $x$. It also mustn't leave any copy of $x$ lying around at the end of the oracle call.

The Deutsch-Jozsa algorithm's quantum circuit

The algorithm begins with the $n+1$ bit state $|0\rangle ^{\otimes n}|1\rangle$. That is, the first n bits are each in the state $|0\rangle$ and the final bit is $|1\rangle$. A Hadamard transform is applied to each bit to obtain the state

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$.

We have the function $f$ implemented as a quantum oracle. The oracle maps the state $|x\rangle |y\rangle$ to $|x\rangle |y\oplus f(x)\rangle$, where $\oplus$ is addition modulo 2 (see below for details of implementation). Applying the quantum oracle gives

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )$.

For each $x,f(x)$ is either 0 or 1. Testing these two possibilities, we see the above state is equal to

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$.

At this point the last qubit may be ignored. We apply a Hadamard transform to each qubit to obtain

${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$

where $x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}$ is the sum of the bitwise product.

Finally we examine the probability of measuring $|0\rangle ^{\otimes n}$,

${\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}$

which evaluates to 1 if $f(x)$ is constant (constructive interference) and 0 if $f(x)$ is balanced (destructive interference).

Deutsch's algorithm

Simulation of quantum circuit for Deutsch's algorithm using Q-Kit

Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm. We need to check the condition $f(0)=f(1)$. It is equivalent to check $f(0)\oplus f(1)$ (where $\oplus$ is addition modulo 2, which can also be viewed as a quantum XOR gate implemented as a Controlled NOT gate), if zero, then $f$ is constant, otherwise $f$ is not constant.

We begin with the two-qubit state $|0\rangle |1\rangle$ and apply a Hadamard transform to each qubit. This yields

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

We are given a quantum implementation of the function $f$ that maps $|x\rangle |y\rangle$ to $|x\rangle |f(x)\oplus y\rangle$. Applying this function to our current state we obtain

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

$={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))$

$=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).$

We ignore the last bit and the global phase and therefore have the state

${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).$

Applying a Hadamard transform to this state we have

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

$={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).$

Obviously $f(0)\oplus f(1)=0$ if and only if we measure a zero and $f(0)\oplus f(1)=1$ if and only if we measure a one. So with certainty we know whether $f(x)$ is constant or balanced.

Deutsch's algorithm can be simulated on Q-Kit, quantum circuit simulator with a graphical interface, for all possible constant and balanced f(x). In the simulation shown, the qubits are initialized in a state $|11\rangle$ (instead of $|01\rangle$). Upon measurement of $|y\rangle ,|x\rangle$ collapses to $|0\rangle$ or $|1\rangle$ corresponding to a balanced or constant f(x) respectively.

References

DESIGN AND IMPLEMENTATION OF REVERSIBLE COMPONENTS OF CPU

Unique:

         Reversible rationale circuits are of high interests to ascertain with least vitality utilization having applications in low-control CMOS outline, optical processing and nanotechnology, particularly in quantum PC.
         In traditional PCs, just NOT entryway performs reversible activity since it has an equivalent number of data sources and yields with their remarkable coordinated mapping. Some reversible doors have just been proposed in writing like the controlled-not (CNOT) (proposed by Feynman), Toffoli and Fredkin entryways, IG Gate and MIG entryway. Reversible doors have different applications in the outlining of adders, subtractions, and multipliers and so forth. Same like traditional PCs.

A Reversible rationale is described by: 1. Meet number of information sources and yields. 2. There exists balanced mapping between the separate data sources and yields. 3. Circles and fan out are not permitted.

                                         CHAPTER 1
                                           PREFACE

1.1 Goal OF WORK

           Presently a day's energy is a noteworthy, non-immaterial, un-maintained a strategic distance from and essential issue in hardware world. In the present life every single electronic segments, gadgets, and hardware experience the ill effects of the circumstance of warmth evacuation and power dissemination issue. At the point when electronic gadgets have the warmth scattering issue then more power is utilized to charge the battery or to alive that gadgets and this overheated and power dispersal issue will prompt diminish the life expectancy of electronic frameworks. Power and warmth dispersal is most concerning issues which oppose meeting the execution due date, and power is one of the factor that expands the cost of that gadgets. Region of the circuit is one of the controlling variable of energy dissemination. Usage of reversible focal preparing unit is critical to decrease every one of the issues identified with electronic circuits and frameworks.
         It is demonstrated [1] that, reversible circuit seriously lessens the warmth dispersal and power utilization of a circuit by coordinated mapping amongst information sources and yields of the reversible circuit. 
        D.P.Divincenzo [2] demonstrated that the reversible circuit assumes a critical part in quantum calculation, on the grounds that the reversible circuits are straightforwardly used to outline the quantum circuits. The nearby connection between quantum entryways and reversible door make it simpler to straightforwardly outline the quantum circuit from the reversible circuit.
        It is to make certain that the processor configuration is an extremely troublesome and tedious assignment, in this way the reasoning about the outlining of engineering in reversible way is a particularly troublesome, and require a ton of time and work to finish the processor plan in reversible way. The reversible processor requires less power and little measure of warmth dispersal than the relating Ir-reversible one.
        As the reversible field is another field in science and innovation, so not very many individuals H.Axelson [3] and M.Thomsen [4] have finished their work with respect to reversible processor. Likewise there is no administration specialist or lawful security for help to work around there.

1.2 DESIRE OF THE PROJECT

 The principle objective is to Design and Implementation of a Reversible Central Processing Unit  Different destinations are given beneath.  To outline the reversible acknowledge of the flip-flops.  To plan the reversible memory circuits, (for example, cradle registers and counter circuits) utilizing the proposed reversible flip-failures of the past advance.  To outline the math circuits, for example, snake, multiplier, divider, and comparator and so on.  To Design the reversible acknowledgment of ALU.  To Design the reversible control unit of the processor by outlining a productive direction decoder.

1.3 Purpose for THE PROJECT

      In the present specialized world, warm contemplations, unwavering quality issues and effectiveness have turned out to be real concerns. These days, investigate is being done to outline a framework with superior, speed and low power dissemination or preferably no warmth age. As power utilization is a noteworthy requirement in planning of VLSI circuits so we have to change to that processing world where no data misfortune exists in light of the fact that as per Landauers standard, on all of calculation, regular computerized frameworks scatter KTln2 measure of vitality, where K is Boltzmann's steady and T is the temperature at which the calculation is performed. Bennett demonstrated that this vitality dissemination would not happen if a similar number of data bits are produced, i.e. no data misfortune exists. Show irreversible innovations disseminate a considerable measure of warmth regarding bit misfortune which diminishes life of the circuit. Every single sensible activity in the present traditional PCs are irreversible. It implies extraction of contribution from the individual yield isn't conceivable. 
    Then again, reversible calculation has a notable element of one of a kind coordinated mapping amongst data sources and yields which lessens the significant issue of energy scattering with no data misfortune.

1.4 ISSUE FORMULATION

        In customary PCs, reversible task is performed just by NOT doors as a result of same number of information and yield, and it is hard to discover balanced mapping between separate data sources and yields with different entryways. 
       To beat this issue we are utilizing the uniquely composed entryways for reversible calculation, for example, controlled-not (CNOT) door Toffoli and Fredkin doors, IG Gate and MIG door. 

Eliminate non-use yield. Reduce additional info. Utilization of least number of doors. Negligible deferral. 1.5 ORGANIZATION OF DOCUMENTATION The project is organized as follows: Chapter 1“PREFACE”: This chapter includes the introduction part of the project. Chapter 2“REASERCH REVIEW”: Chapter 2 consists of research survey of all the reference papers. Chapter 3” Speculation OF REVERSIBLE LOGIC”: This chapter includes basics of reversible logic and all the definitions related to reversible logic gate. Chapter 4” FUNDAMENTAL GATES BASED ON REVERSIBLE LOGIC”: This chapter consists of backend design and simulation of all the basic reversible logic gates. Chapter 5” STRATEGY”: The design and methodology is explained in this chapter. Chapter 6” APPLICATIONS AND ADVANTAGES OF REVERSIBLE CPU”: Chapter 6 includes application and advantages of reversible components of cpu. Chapter 7” SIMULATION RESULTS”: Simulation results of all the reversible components of CPU is explained. Chapter 8” CONCLUSION AND FUTURE SCOPE”: At last chapter 8 includes the conclusion and future work of this project.

                                                                 CHAPTER 2
                                       REASERCH REVIEW   
      Landauer [1] expressed that the measure of vitality dispersed to eradicate each piece of data is at any rate kTln2 (where k is the Boltzmann consistent and T is the room temperature) amid any calculation the transitional bits used to register the last outcome are deleted. This eradication of bits is one of the principle explanations behind the power dissemination.
      C. H. Bennett [2] in 1973 uncovered that the power scattering in any gadget can be made zero or unimportant if the calculation is finished utilizing reversible model. He demonstrated his hypothesis with the assistance of the Turing machine which is an emblematic model for calculation presented by Turing. Bennett likewise demonstrated that the calculations that are performed on irreversible or traditional machine can be performed with same proficiency on the reversible machine. The examination on the reversibility was begun in 1980 depends on the above idea.
    Gordon. E. Moore [3] in 1965 anticipated that the quantities of segments on the chip will twofold like clockwork. At first he anticipated just for a long time yet because of development in the incorporated circuit innovation his forecast is legitimate till today. His work is broadly perceived as the Moore's law. The impact of Moore's law was considered painstakingly and scientists have arrived at the conclusion that as the quantity of segments in the chip builds the power scattering will likewise increment massively. It is additionally anticipated that the measure of energy disseminated will be equivalent to the warmth dispersed by the rocket spout. Thus control minimization has turned into an essential factor for the present VLSI engineers.
    In the year 1994 Shor [4] completed an exceptional research work in making a calculation utilizing reversibility for factorizing extensive number with better effectiveness when contrasted with the traditional figuring hypothesis. After this the work on reversible processing has been begun by more individuals in various fields, for example, nanotechnology, quantum PCs and CMOS VLSI.
   Edward Fredkin and Tommaso Toffoli [5, 6] presented new reversible doors known as Fredkin and Toffoli reversible entryways in view of the idea of reversibility . These doors have zero power dissemination and are utilized as general entryways in the reversible circuits. These entryways have three yields and three sources of info, henceforth they are known as 3*3 reversible doors.

       Peres [7] presented another entryway known as Peres door. Peres door is likewise a 3*3 entryway however it isn't a widespread entryway like the Fredkin and Toffoli entryway. Despite the fact that this entryway isn't general door it is broadly utilized as a part of much application since it has less quantum cost regarding the widespread door. The quantum cost of the Peres entryway is 4.
     H Thalpliyal and N Ranganathan [8] developed a reversible entryway known as TR door. The primary reason for presenting this reversible TR door was to diminish the waste yield in a reversible circuit. H Thalpliyal and N Ranganathan [9] acquainted the reversible rationale with consecutive circuits. Execution of the consecutive circuit, for example, D-lock, T hook, JK lock and SR hook utilizing Fredkin and Feynman entryway has been finished. After this work more research has been done on consecutive circuits utilizing reversible doors.
   
      In established PCs, just NOT entryway performs reversible task since it has an equivalent number of sources of info and yields with their interesting coordinated mapping. Some reversible entryways have just been proposed in writing like the controlled-not (CNOT) (proposed by Feynman), Toffoli and Fredkin doors, IG Gate and MIG door. Reversible entryways have different applications in the outlining of adders, subtractions, and multipliers and so on., same like traditional PCs.

A Reversible rationale is portrayed by: 1. Break even with number of data sources and yields. 2. There exists coordinated mapping between the individual information sources and yields. 3. Circles and fan out are not permitted.

CHAPTER-3

                                      SPECULATION OF REVERSIBLE LOGIC

3.1 Fundamental DEFFINITION OF REVERSIBLE LOGIC

a. REVERSIBLE FUNCTION:

        The numerous yield Boolean capacity F(x1; x2; :::; xn) of n Boolean factors is called reversible if: 

a. The quantity of yields is equivalent to the quantity of sources of info; b. Any yield design has a special pre-picture. At the end of the day, reversible capacities are those that perform changes of the arrangement of info vectors.

b. Reversible entryway:

        The circuit of reversible entryway has a n-sources of info and n-yields to create a particular yield design for each given information. The n-information and n-yield of reversible entryway is spoken to as n*n. In reversible entryway the quantity of info is equivalent to the quantity of yield. In this manner the information sources and yields are associated by balanced mapping.

c. Reversible logic gate:

               Reversible Gates are circuits in which number of yields is equivalent to the quantity of information sources and there is a balanced correspondence between the vector of data sources and outputs[8-10]. It not just encourages us to decide the yields from the information sources yet additionally causes us to remarkably recoup the contributions from the yields.

d. Constant input:

       This refers to the number of inputs that are to be maintain constant at either 0 or 1 in order to synthesize the given logical function [11].

e. Flexibility:

      Adaptability alludes to the all inclusiveness of a reversible rationale door in acknowledging more capacities [13].

f. Gate level:

     This alludes to the quantity of levels in the circuit which are required to understand the given rationale capacities.

g. Equipment complexity:

      This alludes to the aggregate number of rationale activity in a circuit. Means the aggregate number of AND, OR and EXOR task in a circuit [14] and [15].

h. Trash yield:

         Trash yield is characterized as the non-used yield or the yield which is important to deal with the reversibility is known as the junk yield.

i. Quantum cost:

          The quantum cost can be acquired from the circuit of reversible entryway by falling the components of quantum doors [5]. Rudimentary quantum doors deliver the qubits instead of unadulterated rationale esteems.

3.2 Reversible circuits

     To execute reversible calculation, gauge its cost, and to judge its breaking points, it is formalized it as far as door level circuits. For instance, the inverter (rationale entryway) (NOT) door is reversible since it can be fixed. The restrictive or (XOR) entryway is irreversible on the grounds that its sources of info can't be unambiguously reproduced from a yield esteem. Nonetheless, a reversible rendition of the XOR entryway—the controlled NOT door (CNOT)— can be characterized by safeguarding one of the information sources. The three-input variation of the CNOT door is known as the Toffoli entryway. It jam two of its sources of info a,b and replaces the third c by c\oplus (a\cdot b). With c=0, this gives the AND work, and with a\cdot b=1 this gives the NOT work. In this manner, the Toffoli door is all inclusive and can execute any reversible Boolean capacity (sufficiently given zero-introduced auxiliary bits). All the more by and large, reversible doors have a similar number of data sources and yields. A reversible circuit associates reversible doors without fan-out and circles. Along these lines, such circuits contain meet quantities of information and yield wires, each experiencing a whole circuit. 

Reversible rationale circuits have been first roused in the 1960s by hypothetical contemplations of zero-vitality calculation and also down to earth change of bit-control changes in cryptography and PC designs. Since the 1980s, reversible circuits have pulled in enthusiasm as segments of quantum calculations, and all the more as of late in photonic and Nano-figuring advancements where some exchanging gadgets offer no flag pick up. Reviews of reversible circuits, their development and improvement and also late research challenges are accessible.

                                            CHAPTER 4
      FUNDAMENTAL GATES BASED ON REVERSIBLE LOGIC 

4.1 FREDKIN GATE

                         Figure 4.1.1: 3x3 reversible Fredkin gate

Fredkin entryway is a 3x3 reversible door which utilizes three data sources and give three yields.

P=A,

Q=A'B+AC,

R=AB+A'C.

        TABLE 4.1: TRUTH TABLE OF FREDKIN GATE

0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1

 IMPLEMENTATION OF FREDKIN GATE

Figure 4.1.2: implemented Fredkin gate Figure 4.1.3: inside connections of Fredkin gate

Figure 4.1.4: schematic result of FREDKIN gate 4.2 FEYNMAN GATE The Feynman entryway which is a 2x2 door and is additionally called as Controlled NOT and it is broadly utilized for fan-out purposes. The data sources (A, B) and yields

P=A,
Q= A XOR B.
It has Quantum taken a toll one

Figure 4.2.1: 2x2 reversible Feynman gate.

TABLE 4.2: TRUTH TABLE OF FEYNMAN GATE

0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0

 IMPLIMENTATION OF FEYNMAN GATE

Figure 4.2.2: Feynman gate

                  Figure 4.2.3: internal architecture of Feynman gate

Figure 4.2.4: schematic results of Feynman gate

Figure 4.2.5: layout designing of Feynman gate

4.3 BJN GATE:

                                     Figure 4.3.1 3x3 reversible BJN door
                    BJN door is a 3x3 reversible entryway which utilizes three data sources and give three yields. In his door the first and second yield P and Q are equivalent to the first and second info A and B separately. The third yield R is equivalent to the whole of two sources of info A and B, and the summation result is xor with third information c.

BJN gate yields the output as….,

    P=A,
    Q=B’
    R= (A+B) XOR C,

Table 4.3.1: truth table of BJN gate

0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0

 IMPLTEMENTATION OF BJN GATE

Figure 4.3.2: symbol reversible BJN gate

Figure 4.3.3: internal architecture of BJN gate

Figure 4.3.4: schematic result of BJN gate

                                                CHAPTER 5
                                                 STRATEGY

5.1 Outlined WORK

        The constitution of the propel reversible focal handling unit is appeared in the figure 5.1.1. 
                   Figure: 5.1.1 inside design of reversible processor

        The interior engineering of a processor is absolutely relies upon the outlining and use of a processor. The building square of a microchip incorporates control unit, memory, airthematic and rationale unit, and information/yield gadgets. Information transports are capable to exchange the data and flag between the diverse transports. The airthematic and coherent tasks are accomplished by effective outlining of airthematic and rationale unit. The principle capacity of timing and control rationale unit is that it bring back the activity codes of every guideline from memory and begin the grouping of ALU tasks. Every last operational code will impact on all the component of the processor.
        Well ordered planning of reversible focal handling unit is as per the following. 

• Design the general design structure of reversible CPU. • Designing of Flip-slumps and registers for reversible memory. • Design the reversible multiplier. • Design the reversible decoder to unravel the directions. • Design the reversible control unit to coordinate info and yield of a framework. • Design the reversible comparator. • Design the reversible multiplier and reversible divider. • Software Xilinx 14.4 and MW apparatuses Consider the sub-modules of the information way design which is talk about in beneath areas. 5.2 REVERSIBLE ADDER

 The reversible adder is implemented by using 4x4 reversible TSG gate. The main benefit of TSG gate is that, only one gate is sufficient to design and implement full adder. The circuit diagram and the truth table of 4 bit RCA is as follows.
                                             a 

Fig 5.2.1: circuit symbol of reversible full adder based on TSG gate.

Table 5.2.1 truth table of reversible 4-bit RCA A

0 0 0 0 0 0 0

0 0 1 0

0 1 0

0 1 0 0 1 1 0

0 1 1 0 1 0

1

1 0

0 1 1 1 0

1 0 1 1 1 0 1

1 1 0 1 0 0 1

1 1 1 1 0 1 1

The implementation of 4-bit reversible Ripple Carry Adder is as follows.

Fig 5.2.2 : RTL schematic of 4-bit RCA

Fig 5.2.3 : internal RTL schematic view of 4-bit RCA

Fig 5.2.4 : design summary of 4-bit ripple carry adder

Fig 5.2.5 : TSG gate based reversible full adder

Fig 5.2.6 : internal architecture of RCA

Fig 5.2.7 : layout design of reversible RCA

Fig 5.2.8 : output waveforms of reversible RCA

5.3 REVERSIBLE BOOTH MULTIPLIER The circuit diagram for 5x5 booth multiplier consists of 4 types of reversible gates such as double Feynman gates, Fredkin gates, MIG gates, and MNFT gates.

Fig 5.3.1 : circuit diagram of 5x5 reversible booth multiplier.

Fig 5.3.2 : RTL schematic of 5x5 booth multiplier

Fig 5.3.3: design summary of 5x5 reversible booth multiplier

5.4 Reversible signed multiplier A Wallace tree is a productive hardwired usage of a computerized circuit that increases two whole numbers. The Wallace tree has three stages: 1. All of the multiplicand is duplicated (i.e. What's more, by all of multiplier, along these lines yielding n2 comes about (for n X n duplication). Contingent upon position of the duplicated bits, the wires convey diverse weights, i.e. weight of bit conveying consequence of a5b6 is 65. 2. The quantity of incomplete items is lessened to 2 by layers of full and half adders. 3. The wires are assembled in two numbers, and included utilizing a regular snake.

Fig 5.4.1 Reversible Wallace tree for signed multiplication Table 5.4.1 comparison table for reversible and irreversible Wallace tree

5.5 REVERSIBLE DIVIDER

Fig 5.5.1: RTL schematic of reversible divider

Fig 5.5.2: internal RTL view of reversible divider

Fig 5.5.3: desidn summary of reversible divider 5.6 REVERSIBLE sequence counter: Fig 5.6.1: RTL schematic of reversible sequence counter

                         Fig 5.6.2: Internal RTL view of reversible sequence counter

Fig 5.6.3: design summary of reversible sequence counter 5.7 REVERSIBLE COMPARATOR

Fig 5.7.1: RTL Schematic of 8-bit reversible comparator

Fig 5.7.2: RTL Schematic of reversible 2-bit comparator

Fig 5.7.3 : Internal RTL view of 8-bit reversible comparator

Fig  5.7.4: Design summary of reversible comparator

5.8 REVERSIBLE MULTIPLEXER Fig 5.8.1 : RTL schematic of reversible multiplexer

Fig 5.8.2 : internal RTL view of reversible multiplexer

Fig 5.8.3 : Design summary of reversible multiplexer 5.9 REVERSIBLE DECODER Fig 5.9.1: RTL schematic of reversible decoder Fig 5.9.2 : internal RTL view of reversible decoder

Fig 5.9.3 : design summary of reversible decoder 5.10 reversible cintrol logic gate

Fig 5.10.1: RTL Schematic of reversible control logic gate

Fig 5.10.2 : Internal view of reversible control logic gate

Fig 5.10.3 : design summary of reversble control logic gate

5.11 REVERSIBLE ALU Table 5.11.1: Operations performed in reversible ALU

Fig 5.11.1 : RTL Schematic of reversible ALU

Fig 5.11.2 : internal view of reversible ALU

Fig 5.11.3: design summary of reversible ALU

                                        CHAPTER 6

APPLICATIONS AND ADVANTAGES OF REVERSIBLE CPU

6.1 APPLICATIONS Reversible computing may have applications in computer security and transaction processing, but the main long-term benefit will be felt very well in those areas which require high energy efficiency, speed and performance .it include the area like  Low power CMOS.  Quantum computer.  Nanotechnology.  Optical computing.  DNA computing.  Computer graphics.  Communication.  Design of low power arithmetic and data path for digital signal processing (DSP).  Field Programmable Gate Arrays (FPGAs) in CMOS technology.

The potential application areas of reversible computing include the following  Nano computing  Bio Molecular Computations  Laptop/Handheld/Wearable Computers  Spacecraft  Implanted Medical Devices  Wallet “smart cards”  “ Smart tags” on inventory  Prominent application of reversible logic lies in quantum computers.  Quantum gates perform an elementary unitary operation on one, two or more two–state quantum systems called qubits.  Any unitary operation is reversible and hence quantum networks also.  Quantum networks effecting elementary arithmetic operations cannot be directly deduced from their classical Boolean counterparts (classical logic gates such as AND or OR are clearly irreversible).  Thus, Quantum computers must be built from reversible logical components.

6.2 ADVANTAGES:  It is unavoidable sort of registering later on as the cutting edge processing depends on advancements which are essentially reversible. So when the hidden physical acknowledge of figuring wind up reversible, it likewise manages the reversibility at sensible level.  As indicated by Landuer, the vitality is scattered at whatever point we are having any coherent task done on the machine ,This happens as a result of the comprehensiveness of the thermodynamic laws where Entropy is expanded at whatever point there is an activity that doesn't have each activity having the extraordinary and diverse answer . This structures the premise of Reversible Logic where we have just a single is to one correspondence b/w the information and the yield.  Display day circuits disseminated energy of the request of nano-watts which is nearly 3-4 size bigger than the power lost because of entropy change.  so the present day circuits don't have such issues with the power loss of this request however when in future when we will have the circuits having low power misfortune it will end up practically identical and in this manner we have to configuration circuits that are reversible in nature.

                                                CHAPTER 7
                               SIMULATION RESULTS

7.1 Reversible ripple carry adder Fig 7.1 : Simulation result of 4-bit RCA 7.2 Simulation result of booth multiplier

Fig 7.2 : simulation result of reversible booth multiplier 7.3 Reversible multiplier

Fig 7.3 : simulation result of reversible multiplier 7.4 Reversible divider

Fig 7.4: simulation result of reversible divider

7.5 : Revrsible sequence counter

Fig 7.5: Simulation result of reversible sequence counter 7.6 : Reversible comparator

Fig 7.6: simulation result of reversible comparator

7.7 reversible multiplexer

Fig 7.7 : Simulation result of Reversible multiplexer 7.8 Reversible Decoder

Fig 7.8 : Simulation result of reversible decoder

7.9 Reversible control logic gate Fig 7.9 : Simulation result of reversible control logic gate 7.10 Reversible ALU

Fig 7.10: Simulation result of Reversible ALU

7.11 Reversible Fredkin gate

  Fig 7.11.1 : Output of reversible Fredkin gate

Figure7.11.2 : layout designing of FREDKIN gate

7.12 Reversible Feynman gate Fig 7.12.1 : output of reversible Feynman gate

Fig 7.12.2: layout designing of reversible Feynman gate 7.13 Reversible BJN gate

Fig 7.13.1: output of reversible BJN gate Figure 7.13.2: layout designing of BJN gate 7.14 Reversible Full Adder Fig 7.14.1: output of reversible full adder Fig 5.2.7 : layout design of reversible full Adder

Chapter 8 CONCLUSION AND FUTURE SCOPE

     In this work, our main motive is to design and implementation of reversible central processing unit to reduce the power consumption, heat dissipation, less area, low cost, and to minimize the delay as compare to the corresponding ir-reversible CPU. By incorporating all the individual reversible components of this work, we can construct the complete design and implementation of reversible CPU.

REFERENCES

[1] R. Landauer, - Irreversibilty and Heat Generation in the Computational Process, IBM Journal of Research and Development, 5, pp. 183-191, 1961 [2] Bennett C.H., “Logical reversibility of Computation”, IBM J.Research and Development, pp. 525-532, 1973. [3] Gordon. E. Moore, Cramming more components onto integrated circuits Electronics, Volume 38, Number 8, April 19, 1965. [4] P. Shor, Algorithms for quantum computation: discrete log and factoring, Proc. 35th Annual Symp. On Found. Of Computer Science (1994), IEEE Computer Society, Los Alamitos, 124-34. [5] E. Fredkin, T Toffoli, “Conservative Logic”, International Journal of Theor. Physics, 21(1982), pp. 219-253 [6] T. Toffoli., Reversible Computing, Tech memo MIT/LCS/TM-151, MIT Lab for Computer Science (1980). [7] A. Peres, Reversible Logic and Quantum Computers, Physical Review A, vol. 32, pp. 3266-3276, 1985. [8] H Thapliyal and N Ranganathan, “Design of Efficient Reversible Binary Subtractors Based on a New Reversible Gate”, IEEE Proceedings of the Computer Society Annual Symposium on VLSI, pp. 229-234 (2009). [9] H Thapliyal and N Ranganathan, “Design of Reversible Latches Optimized for Quantum Cost, Delay and Garbage Outputs”, Proceedings of Twenty Third International Conferences on VLSI Design, pp. 235-240(2010)

Abstract The reversible components of CPU is designed and implemented in order to optimize area, cost, power, minimum garbage output which in turn leads to small amount of heat dissipation. The cost and area is optimized by reducing the gate count, and the hardware complexity is reduced by using the minimum constant input. As compared to the current work, the proposed work includes the plan and implementation of some additional reversible components of CPU and also achieves extra features as compared to the current work. The proposed configuration is mimicked and the outcome is checked by utilizing programming Xilinx ISE 14.4. Index Terms—Reversible Logic, Reversible components of CPU, Garbage Output, constant inputs, gate count, and optimized area . I. INTRODUCTION Area, cost, and power are an essential issues in this day and age. In later a long time, the developing business sector of electronic frameworks experiences control scattering and warmth evacuation issue. Assuming to an ever increasing extent control is scattered, system ends up heating problem and this lessens the life span of the components. The requirements of electronic circuits with less power dispersal prompts the utilization of reversible method of reasoning circuit. Lafifa and Hafiz Md [1] had worked on reversible CPU components to reduce power and heat dissipation. Bennett [2] demonstrated that the balanced mapping between the sources of info and yields of reversible circuit definitely lessens the power utilization furthermore, warm dispersal of a system. Now a day’s prevention in computerized registering, interchanges are of most significance. In this way cryptanalysis conventions assume a noteworthy part. David [3] demonstrated that reversibility assumes key part in total calculation. Established reversible system, the information quantity of quantum samples should be equivalent to the quantity of produced quantum samples. The quantum doors what's more, systems should be reversible. Along these lines, the quantum systems can specifically composed from reversible systems. The current reversible mainframe [4] was not worked on the architecture of reversible arithmetic logic unit, reversible control logic gate. The new configuration of all the reversible components of CPU, such as reversible ALU, reversible adder, reversible multiplier, reversible divider, reversible multiplexer, reversible decoder, reversible comparator, reversible sequence counter and reversible control logic gate. II. PROPOSED WORK The interior game plan of a chip shifts depending on the plan and the expected motivations behind the chip. A chip incorporates a number juggling rationale unit arithmetic logic unit and control unit sections. The ALU plays out the number-crunching and consistent activities. The control rationale segment recovers direction task, program codes from storage memory as well as starts grouping the tasks, which are the requirements of arithmetic logic unit to complete the task. The configuration of the reversible components of the processor is appeared in below Figure 1, which consist of reversible adder, Multiplexer, Decoder, Control logic gate, ALU, , Multiplier Divider.

Fig 1. Design of reversible central processing unit.  

A. reversible Adder

Fig 2.RTL schematic of reversible RCA. The new configuration of reversible 4 bit RCA is based on TSG gate. The most critical part of this entryway is that it can work separately as a reversible RCA. The new configuration of reversible 4 bit RCA achieves 2 unused output, 1 invariable input, and gate level is 1. Figure 3. simulation result of 4 bit adder B. reversible Multiplexer Fig 4. RTL schematic of reversible multiplexer The reversible MUX consist of two reversible 2:1 multiplexer. Where each 2:1 multiplexer is made up of only one fredkin gate. As compare to the existing reversible 4:1 multiplexer [1] we are using only two fredkin gates in proposed 4:1 mux, and we acheives the 4 garbage output, gate count is 2, and 0 constant inputs.and it uses only two fredkin gate because of this, the power,area, and cost is minimum. Fig 5. simulation result of 4:1 multiplexer C. Reversible Decoder Fig 6. RTL view of proposed reversible 3:8 decoder. The proposed reversible 3:8 decoder consist of 1 double Feynman gate (F2G) and two reversible gate. As compared to the current decoder [1] the new configuration of reversible decoder uses only 3 reversible gates. By reducing the figure of reversible doors, the area, cost, and power o the reversible 3:8 decoder is reduced. From the proposed reversible decoder we achieves 4 constant inputs, 3 gate counts, and only 1 garbage output. Fig 7. Simulation result of proposed 3:8 reversible decoder. D. Reversible control logic gate. Fig 8. RTL schematic of control logic gates

The circuit diagram of reversible control logic gate consists of 8 TG gate, and 5 Feynman gates. From the proposed reversible control logic gate we can achieves the 13 gate count, 13 constant inputs, and 19 garbage output.

Fig 9. Simulation of reversible control logic gate. E. Reversible ALU Fig 10 . RTL schematic of 16 bit reversible ALU The new configuration of reversible 16 bit ALU consist of 1 NOT gate, 1 DPG gate, 1 DKG gate, 1 TG gate, and 11 reversible 2:1 multiplexer which is based on FRG gate. The implementation of proposed 16 bit reversible ALU achieves 27 garbage output, 8 constant inputs, and gate count is 15. Fig 11. simulation result of 16 bit reversible ALU F. Reversible Multiplier Fig 12. RTL schematic of booth multiplier The RTL schematic of proposed 5 bit reversible booth multiplier consist of double Feynman gates (F2G), FRG gates, MIG gates, MNFT gates. The implementation of proposed reversible 5 bit multiplier achieves 84 garbage outputs, 2 constant inputs, and gate counts are 45. Fig 13. simulation result of proposed 5 bit reversible booth multiplier G. Reversible Divider Figure 14. implementation of proposed reversible divider The RTL schematic of proposed reversible divider consist of 4 feynman gate, and 5 reversible CDA gate. The reversible CDA gate consist of 1 FG and 1 DPG gate. The implementation of proposed reversible divider achieves the 10 garbage output, 9 constant inputs, and gate count is 9. Fig 15. simulation result of proposed reversible divider III. CONCLUSION AND FUTURE WORK The reversible logic synthesis with the minimum power, area and cost factors are carried out for the components of the reversible processor. Successfully designed and implemented the components like reversible ALU (Adder, Multiplier, Divider) multiplexer, decoder etc and achieves optimized result in terms of gate level, garbage output, constant inputs, optimized area, minimum cost and less power as compared to existing reversible components of CPU. At the last all the reversible elements of the CPU going to be incorporate together. ACKNOWLEDGMENT

REFERENCES [1] Lafifa Jamal and Hafiz Md. Hasan Babu, “Design and Implementation of a Reversible Central Processing Unit” 2015 IEEE Computer Society Annual Symposium on VLSI. pp 187-190. [2] C. H. Bennett, “Logical reversibility of computation,” IBM J. Research and Development, vol. 17, pp. 525–532, 1973. [3] D. P. DiVincenzo, “Quantum gates and circuits,” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 454, no. 1969, pp. 261–276, 1998. [4] H. Axelsen, R. Glck, and T. Yokoyama, “Reversible machine code and its abstract processor architecture,” in Computer Science Theory and Applications, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2007, vol. 4649, pp. 56–69. [5] E. Fredkin, T Toffoli, “Conservative Logic”, International Journal of Theor. Physics, 21(1982), pp. 219-253 [6] T. Toffoli., Reversible Computing, Tech memo MIT/LCS/TM-151, MIT Lab for Computer Science (1980).

External links

• Deutsch's lecture about the Deutsch-Jozsa algorithm
• Q-Kit Graphical Quantum Circuit Simulator, a desktop application for building and customizing quantum gates and circuits, simulating upto 20-qubit systems.