ry bit c' = (ab) + c(a ) b), where C is the carry from order i - 1. It is easily checked that c' is the carry of Reversible computation 0 + xy FANOUT Figure 15.10 Logic gates NOT, AND, NAND, FANOUT, and XOR, as built from single Toffoli gates. The gate CNOT is also shown. CARRY Figure 15.11 Gate circuits SUM and CARRY, built from CNOT and Toffoli gates. order i of the sum a + b + C. 16 The plain-adder circuit, which performs the computation + B of two binary numbers A=aaa and B bob,...., bn, chosen here with n = 2 for simplicity,17 is shown in Fig. 15.12. The interpretation of the V-shaped circuit shown in the figure goes as follows. Consider first the CARRY gates. In the left part of the circuit (the descending branch of the V), we observe that the carry is computed through a cascade of three CARRY gates, up Indeed, (a) if a = b = 0 then c' = 0 + 0c = 0; (b) if a=b=1 then c' = 1 + 0c = 1; (c) if a # b then 0 1c C. As adapted from V. Vedral and M.1 B. Plenio, Basics of quantum computation. Prog. Quant. Electron., 22 (1998), 1-39. 15.3 Reversible logic gates and computation Figure 15.12 Plain-adder gate circuit, performing the addition of two binary numbers A = aoaa and B = bobb, with output A = aoaa and D = dodid2d. The gates C and S with a thick bar to the right correspond to the CARRY and SUM gates shown in Fig. 15.11. The gate C with a thick bar to the left effects the reverse operation of CARRY. to the highest order (i = 3), which yields C3 = d3 (highest-weight bit of D = + B). In the right part of the circuit (ascending branch of the V), the reverse operation is effected,18 which resets the bit values initially input to the previous CARRY gate in the sequence. Second, consider the three SUM gates in the right part of the circuit. These gates are seen to compute di = a + bi -1 in descending order (from i = 2 i = 0), with co = 0. At the bottom of the V, one observes that the reverse CARRY gate is substituted with a CNOT gate. An easy verification shows that such an arrangement makes it possible to initiate the