s and computation way, without heat dissipation or entropy increase. The corresponding computer should exclusively use reversible gates, which we shall analyze next. Reversible logic gates and computation In this section, I shall describe a new class of logic gates, which make it possible to build a variety of reversible-computing circuits. The first two elementary gates having such a property are called the Fredkin and the Toffoli gates, which we shall consider now. The Fredkin gate is illustrated in Fig. 15.7, along with its truth table. It is seen from the figure that the Fredkin gate has three input ports (a, b, c) and three output ports (a',b',c'). Two input ports are used for the operand data (a, b), the third port being used for a control bit (c). The gate operates according to the following logic (see also the Figure's truth table): If C = 0, then a, b remain unchanged (a' = a, b' = b); If C = 1, then a, b are swapped (a' = b,b'==) The control bit C remains unchanged (c' = c). Figure 15.8(a) and (b) illustrate the first two basic operations of the Fredkin gate: REPEAT (c = 0) and CROSSOVER or SWAP (c=1). = But the gate can be configured to perform other functions of interest, as shown in Fig. 15.8(c) and (d): setting a = l,b=0,c=x yields a' = N O T x) and b'=c'= (FANOUT x). Setting a = 0,b=y,c= = x yields a'=xxy(x) AND y) and b'=x yy (x AND y). The input bits a, b, which are preset to constant values 0 or 1 in the Fredkin gate, as shown in Fig. 15.8(c) and (d), are referred to as ancilla bits. Such ancilla bits, which are the key to the operation of reversible gates, represent a novel concept in computational logic. Another novelty is that reversible gates produce extra or garbage bits, which are not useful to the rest of the computation (e.g., the bit b = x ^y in Fig. 15.8(d). Last but not least, we notice from the Fredkin gate truth table (Fig. 15.7) that each output port configuration (a', b', c') exclusively corresponds to a unique input port configuration (a, b, c). Thus, there exists a mutual and un