) the target qubit is transformed into U|x). This is the definition of the controlled-U gate. Actually, the equivalence of the circuit shown in Fig. 16.10 and the controlled-U gate stems from Euler's theorem, which is demonstrated in Appendix N. The theorem states that for any 2 x 2 unitary transformation U, there exist three matrices A, B, C satisfying ABC = I and for which U = eis AXBXC, where 8 is an arbitrary phase. As a third illustrative example, consider next the 3-qubit quantum circuit shown in Fig. 16.11, which involves two CNOT gates, and three controlled-U gates based on a unitary operator V and its Hermitian conjugate V+. The property V2= U is also assumed. Let us walk the input state |a>|b)|x) through the quantum circuit, considering the four possibilities for the control qubits (a)|b)==00|0), = |0)|1), |1) |0), |1)|1). This 16.4 Quantum circuits Figure 16.12 Three-qubit quantum circuit with Hadamard gates (H), /4-phase gates (T, T+), and a single /2-phase gate (S), which is equivalent to a CCNOT or Toffoli gate. gives: |0>|0>|x> |0>|0>|x> |0>|1>|x> |0)|1>|x> |0>|1)|x> |0>|1)|x> |1)|0>|x) |1>|0>|x> |1>|1>|x) |1>|1>|x> |1)|1) 0)Vxx) |1)|1)VV|x) |1)|1)U|x). (16.43) We observe from the above result that when |a) |b) # |1)|1) the circuit leaves the target qubit /x) invariant, and when |a) b) = |1)|1) the target qubit is transformed into U|x). This is the definition of a controlled-controlled-U, or CCU gate, whose representation and matrix are shown in Fig. 16.7. It is straightforward to verify that in the case (16.44) we have U = V2 = X, and the CCU gate reduces to the previously described CCNOT or Toffoli gate (Fig. 16.6). 10 As another example, consider the elaborate quantum circuit shown in Fig. 16.12, which includes Hadamard gates (H), /4-phase gates (T, T+), and a single /2- phase gate (S). It is left as an exercise to establish that this quantum circuit is actually a possible equivalent realization of a Toffoli or CCNOT gate. As a final example of complex quantum circuits, consider the plain-adder 