e, the Toffoli gate has three input ports (a, b, c) and three output ports (a',b',c'). The difference is that a, b are control bits (a' = a, b'= b) and C is the target bit. By convention, control bits are marked with a dot () and the target bit with a cross (x). The Toffoli gate outputs C + (a ^ b), or c' = C + ab for short. The truth table in the figure shows that the value of C is flipped (function NOT) when the two control bits are set to =b= 1, and is left unchanged otherwise (function REPEAT). The Toffoli gate can, thus, be conceived as a controlled-controlled-NOT (CCNOT) gate. As we shall see next, the inputs (a, b, c) can also play different roles of variable, control, or ancilla bits, with c' remaining the gate's functional output bit, by definition. Figure 15.10 illustrates that the logical functions NOT, AND, NAND, XOR, and FANOUT can be built from single Toffoli gates. The function OR can be built with two NOT and one NAND gates using the relation avb=a7b. The figure also shows the CNOT gate, which can be viewed as a simplified representation of the XOR gate. The Toffoli gate, like the Fredkin gate, thus, represents a universal building block in the construction of reversible-logic circuits. I shall now provide an example of a complex circuit exclusively constructed from CNOT and Toffoli gates, which is called the plain adder. A plain adder performs the addition of two binary numbers A= aoa an and B = bobi bn. This function entails not only the bit-by-bit addition operations (a + bi with but also the computation and addition of the carry bit Ci-1 at each stage i. To construct a plain adder, one, thus, needs two new gate circuits, which we call SUM and CARRY, and which are illustrated in Fig. 15.11. It is seen from the figure that SUM is built from a cascade of two CNOT gates. The plain-adder circuit performs the double sum x = a o b (bit-by-bit addition of order i) and + C (addition of the result with carry C of order i- 1), with indices being omitted here for clarity. The circuit CARRY outputs the car