Reversible and DNA Computing. Hafiz M. H. Babu

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

of garbage outputs. This chapter explains the basic reversible logic gates for more complex system, which may have reversible circuits as a primitive component and can execute complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers, as all quantum operations are reversible. This chapter presents the information related to the primitive reversible gates and helps researchers in designing higher complex computing circuits using reversible gates.

1.1 Reversible Logic

      In this section, basic definitions and ideas related to reversible logic are presented. Formal definitions of reversible gate, garbage output, and the popular reversible gates, along with their input–output vectors, are presented here. Illustrative figures and examples are also included in respective discussions.

1.2 Reversible Function

      The multiple‐output Boolean function

of n Boolean variables is called reversible if:

      1 The number of outputs is equal to the number of inputs.

      2 Any output pattern has a unique pre‐image.

      In other words, the functions that perform permutations of the set of input vectors are referred to as reversible functions.

1.3 Reversible Logic Gate

Reversible logic has unique mapping between input and output bit pattern. A unit logic entity is represented as a gate. The gates or circuits that do not lose information are called reversible gates or circuits.

      Property 1.3.1

      A reversible circuit is a circuit in which the number of input and the number of output is equal and there is one‐to‐one mapping between input and output vectors.

Let us consider the gate shown in Figure 1.1. According to the definition, the gate is a reversible gate, because it has k number of inputs and k number of outputs and the gate is known as

reversible gate. Without the NOT gate, classical logic gates are called irreversible, since they cannot determine the input vector states from the output vector states uniquely.

      Example 1.1

There 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.

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