Implementing Function Evaluation with Simple Quantum Gates

This section is not directly needed for what follows, but we think it will help you realize that the function box $U_f$ could be constructed directly from just a few of the quantum gates we described earlier. This figureDiag_11_4 (after Mermin, 2007, p. 42) shows you the circuit diagrams. Each circuit consists of two input wires and two output wires. A qubit state is associated with each wire. For example, in the top part of this same figure, each wire could represent either $|0⟩$ or $|1⟩$. Since those wires connect directly to the output, the states do not change.

In the second function circuit, the lower register state is subject to a controlled-$\text{NOT}$ ($\text{CNOT}$) gate, drawn as a controlled $\text{X}$ gate, with the upper register state acting as the control state. In that case, if the upper register state is $|0⟩$, then the lower register state output is the same as the lower register state input. If the upper register state is $|1⟩$, the lower register state is “flipped.” For example, $|1⟩$ becomes $|0⟩$. That set of operations is just what is needed to implement function $f_1$ from this tableTable_11_1.