Reversible and DNA Computing. Hafiz M. H. Babu

can be any number of dimensions for a reversible gate, but lower dimension is always preferable for designing efficient circuits. Popular reversible gates, Feynman gate (FG), Toffoli gate (TG), Peres gate (PG), Fredkin gate (FRG), Feynman double gate (F2G), and new fault‐tolerant gate (NFTG), are shown in Figure 1.2.

1.4 Garbage Outputs

The output (outputs) of a reversible gate that is (are) not used as input to other gate or the output (outputs) that is (are) not treated as a primary output is (are) called garbage output (outputs). The unutilized outputs from a gate are called garbage outputs. A heavy price is paid for every garbage output. So, for any circuit design, the fewer the garbage outputs, the better.

Figure 1.1 A

reversible gate.

Figure 1.2 Popular reversible gates.

Figure 1.3 Reversible Feynman gate.

      Example 1.2

When a Feynman gate (FG) is used for Ex‐OR (exclusive‐OR, ) operation of two inputs, an extra output is generated at the output part of the FG in addition to the Ex‐OR output. This additional output is known as garbage output. In Figure 1.3, the garbage output of a gate is shown. Here, A is the garbage output.

1.5 Constant Inputs

      Constant inputs are the inputs of a reversible gate (or circuit) that are either set to 0 or 1.

      Example 1.3

      If the complement of the input A from Figure 1.3 is needed, then B is set to 1 and .

1.6 Quantum Cost

      The quantum cost of a circuit is the total number of 2 2 quantum primitives that are used to realize corresponding quantum circuit. Basically, the quantum primitives are matrix operations, which are applied on qubits state.

      Example 1.4

The quantum realization of reversible Fredkin (FRG) gate is shown in Figure 1.4. Each quantum Ex‐OR gate and quantum or gate requires 1 (one) quantum cost. The reversible FRG gate has four quantum Ex‐OR gates, two quantum V gates, and one quantum gate. So, the quantum cost of reversible FRG gate seems 7 (seven). But, we know if a quantum Ex‐OR gate and a quantum or gate exist angularly (denoted by angular box), then the quantum cost is treated as 1. From the figure, we see that there exists two angular boxes, and each angular box is treated as 1 quantum cost. As a result, the total quantum cost of reversible FRG gate is 5 (five).

Figure 1.4 Quantum realization of reversible Fredkin (FRG) gate.

      Example 1.5

The cost of all 2 2 gates is the same, and it is 1. For 1 1 gate, the cost is 0. Every circuit can be constructed from those 1 1 and 2 2 quantum primitives, and the cost of circuit is the total sum of required 2 2 gates.

1.7 Delay

      The delay of a logic circuit is the maximum number of gates in a path from any input line to any output line. The definition is based on two assumptions: (i) Each gate performs computation in one unit time and (ii) all inputs to the circuit are available before the computation begins.

      Example 1.6

      The delay of each 1 1 and 2 2 reversible gate is taken as unit delay 1. Any 3 3 reversible gate can be designed from 1 1 reversible gates and 2 2 reversible gates, such as CNOT gate, controlled‐V, and controlled‐ gates (V is a square root of NOT gate and is its hermitian). Thus, the delay of a 3 3 reversible gate can be computed by calculating its logical depth when it is designed from smaller 1 1 and 2 2 reversible gates.

1.8 Power

      Power of a gate is defined by the energy. Energy of a basic quantum gate is 142.3 meV. 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 realize it. That means the total number of required quantum gates in the quantum representation of a reversible quantum circuit or gate. So, the power of a reversible