Reversible and DNA Computing. Hafiz M. H. Babu

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.8 Toffoli 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.

1.15 Area

      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.

1.16 Design Constraints for Reversible Logic Circuits

      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.

1.17 Quantum Analysis of Different Reversible Logic Gates

      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.

      Property 1.17.1

      The quantum cost of every 2 2 gate is the same. It can be easily assumed that 1 1 gate cost nothing, since it can always be included to arbitrary 2 2 gate that precedes or follows it. Thus, in first approximation, every permutation quantum gate will be built from 1 1 and 2 2 quantum primitives and its cost is calculated as a total sum of 2 2 gates used. All gates of the form 2 2 has equal quantum cost, and the cost is unity.

      1.17.1 Reversible NOT Gate (Feynman Gate)

      Example 1.13

A 2 2 Feynman gate is also called CNOT. This gate is one through because it passes one of its inputs. Every linear reversible function can be built by using only 2 2 Feynman gates and inverters. Since this is a 2 2 gate, the quantum cost is 1. Quantum equivalent circuit of the Feynman gate is shown in Figure 1.9.

      1.17.2 Toffoli Gate

Figure 1.10 shows the equivalent quantum realization of three input Toffoli gate. The cost of the Toffoli gate is five 2 2 gates, or simply 5. In Figure 1.10, is a square‐root of NOT gate and is its hermitian. Thus, creates a unitary matrix of NOT gate and = I (an identity matrix, describing just a quantum wire).

Figure 1.9 Quantum cost calculation of Feynman gate.

Скачать книгу