Hafiz M. H. Babu - Reversible and DNA Computing

(1.11.1)

where

= Quantum gate calculation complexity

= A quantum NOT gate

= A quantum CNOT gate

= A quantum controlled‐V (controlled‐) gate

Figure 1.6Block diagram of the reversible FRG gate.

Figure 1.7Quantum representation of a reversible FRG gate.

Figure 1.7shows the quantum representation of a reversible Fredkin (FRG) gate. The figure describes that there is only one NOT operation, four quantum CNOT operations, and three quantum controlled‐V (controlled‐ ) operations. So, the quantum gate calculation complexity of the reversible FRG gate is .

Fan‐out is a term that defines the maximum number of inputs in which the output of a single logic gate can be fed. The fan‐out of any reversible circuit is 1.

The fan‐out of any reversible circuit is 1.

A gate is said to be self‐reversible if its dual combination is the same as itself.

In Figure 1.8, there are two Toffoli gates that are in the cascading form. If the outputs of the first Toffoli gate are fed to the input of the second Toffoli gate, then the output of the second Toffoli gate is equal to the input of the first Toffoli gate. Here the outputs of first gate are P, Q , and R , where P = A , Q = B , and R = AB C . Then the outputs of second gate are X, V , and Z , where X = A, Y = B , and Z = AB AB C = 0 C = C .

In a reversible circuit, correct output is found by applying correct input instance and controlling one or more inputs if needed. Feynman gate (FG) is already presented to illustrate the idea of garbage output, Feynman gate is 2 2 reversible gate where inputs are A, B, and corresponding functions are P = A, Q = A B . The Feynman gate is used here to show how to control input to produce expected output. Both the inputs A and B are used as control inputs, and their impact on output is shown below.

Figure 1.8Toffoli gates as self‐reversible.

A as control input:

For , output , and ,

For , output , and .

B as control input:

For , output , and .

For , output , and .

It is better to note that when B is used as control input and , both the outputs P = B and Q = A . By controlling B , the copies of A can be created. This circuit can be easily used as a copying circuit.

The area of a logic circuit is the summation of individual areas of each gate of the circuit. Suppose a reversible circuit consists of n reversible gates. Area of those n gates are . Then by using above definition area, denoted by A , of that circuit is

The above definition for the area of a circuit can be calculated easily by obtaining area of each individual gate using CMOS 45 nm Open Cell Library and Synopsis Design Compiler.

Area of a gate can also be defined by the feature size. This size varies according to the number of quantum gates. As the basic quantum gates are fabricated with quantum dots with the size ranges from several to tens of nanometers ( m) in diameter, the size of the basic quantum gates ranges from 50–300 Å. Quantum circuits can be implemented with the basic quantum gates and the number of quantum gates depends on the number of basic quantum gates needed to implement it. So, the area of a gate can be defined as follows: Area = Number of quantum gates Size of basic quantum gates.

The following are the important design constraints for reversible logic circuits:

Reversible logic gates do not allow fan‐outs.

The reversible logic circuits should have minimum number of reversible gates.

Reversible logic circuits should have minimum quantum cost.

The design can be optimized so as to produce minimum number of garbage outputs.

The reversible logic circuits must use minimum number of constant inputs.

The reversible logic circuits must use a minimum logic depth or gate levels.

Reversible logic circuits should have minimum area and power.

The reversible logic circuits must use minimum hardware complexity and minimum quantum gate calculation complexity.

Calculating quantum cost of reversible circuit is always an interesting one. Quantum circuits, DNA technologies, nano‐technologies and optical computing are the most common applications of quantum theory. Every reversible gate can be calculated in terms of quantum cost and hence the reversible circuits can be measured in terms of quantum cost. Reducing the quantum cost from reversible circuit is always a challenging issue and research are still going on in this area. In this section, the quantum equivalent diagram of some popular reversible gate is presented.