8.70: Evaluating a Function Using a Quantum Circuit and a Demonstration of Parallel Computation

This tutorial deals with quantum function evaluation and parallel computation. The example is taken from pages 94-95 of Exploring the Quantum by Haroche and Raimond. A certain function of x yields the following table of results.

\[ \begin{pmatrix} \text{x} & 0 & 1 & 2 & 3 \\ \text{f(x)} & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

First we establish that the circuit given below yields the results shown in the table, and then demonstrate that it also carries out a parallel calculation in one step using all four input values of x.

In Figure 2.22(b) Haroche and Raimond show a three wire quantum circuit which evaluates f(x). The top two wires are coded for the values of x (2 bits, 4 values) and the third wire is initially set to |0 >. After operation of the circuit on the initial state, the value of the function appears on the third wire. The qubits on the top wires are not changed by the circuit. The circuit consists of a CnNOT (controlled-controlled NOT) gate employing all three wires, followed by a CNOT gate involving the second and third wires, and finally a NOT gate operating on the third wire. A sketch is provided below.

\[ \begin{matrix} \begin{matrix} |a \rangle & \triangleright & \cdot & \cdots & \cdots & \cdots & \cdots & \triangleright & |a \rangle \\ ~ & ~ & | \\ |b \rangle & \triangleright & | & \cdots & \cdot & \cdots & \cdots & \triangleright & |b \rangle \\ ~ & ~ & | & ~ & | \\ |0 \rangle & \triangleright & \oplus & \cdots & \oplus & \cdots & \fbox{NOT} & \triangleright & | f(x) \rangle \end{matrix} \text{ where } |0 \rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} & |1 \rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{matrix} \nonumber \]

The required quantum gates in matrix operator form are as follows:

\[ \begin{matrix} \text{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} & \text{NOT} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} & \text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} & \text{CnNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \end{matrix} \nonumber \]

Kronecker is Mathcad's command for carrying out the tensor multiplication of matrices. Note that the identity operator is required when a wire is not involved in an operation. In the Appendix the matrix form of the circuit is displayed and its reversibility is demonstrated.

\[ \text{QuantumCircuit = kronecker(I, kronecker(I, NOT)) kronecker(I, CNOT) CnNOT} \nonumber \]

The operation of the quantum circuit is now illustrated.

\[ \begin{matrix} ~ & \text{Input} & \text{Calculation} & \text{Output} \\ \text{f(0) = 1} & \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \text{QuantumCircuit} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ \text{f(1) = 0} & \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \text{QuantumCircuit} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ \text{f(2) = 0} & \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \text{QuantumCircuit} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ \text{f(3) = 0} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} & \text{QuantumCircuit} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{matrix} \nonumber \]

Now we come to the demonstration of parallel calculation that is possible in a quantum gate circuit such as the one shown above. If all the values of x (0, 1, 2, 3) are present simultaneously as a superposition, the |a>|b> part of the input register is (1/2 is the normalization constant),

\[ \begin{matrix} \frac{1}{2} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} & \text{which leads to this total input register} & \frac{1}{2} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

Operating on this register with the quantum circuit yields the following result, which by inspection is clearly a balanced superposition of the earlier results. The function has been evaluated for all values of x in one pass through the circuit.

\[ \begin{matrix} ~ & \text{f(0) = 1} & \text{f(1) = 0} & \text{f(2) = 0} & \text{f(3) = 1} \\ \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0.5 \\ 0.5 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.5 \end{pmatrix} & \frac{1}{2} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & + \frac{1}{2} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & + \frac{1}{2} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} & + \frac{1}{2} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0.5 \\ 0.5 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0.5 \end{pmatrix} \end{matrix} \nonumber \]

The amplitude of each contribution to the superposition is 1/2, so the probability of being observed on measurement is 0.25. The contributions to the superposition are rewritten to emphasize that the top two wires carry the input value of x, while the bottom wire has the value of f(x).

\[ \begin{matrix} \text{f(0) = 1} & \text{f(1) = 0} & \text{f(2) = 0} & \text{f(3) = 1} \\ \begin{pmatrix} 0 \\ 1 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 1\\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{matrix} \nonumber \]

Haroche and Raimond describe this process as follows: "By superposing the inputs of a computation, one operates the machine 'in parallel', making it compute simultaneously all the values of a function and keeping its state, before any final bit detection is performed, suspended in a coherent superposition of all the possible outcomes."

This seems absolutely marvelous, four calculations in a single operation of the circuit. However, there's a catch, and that is that an inquiry (measurement) into the results of the calculation can yield only one of the results. On measurement the quantum superposition collapses, as it always does, to one value and the others are irretrievably lost. You can only learn one thing from a quantum state measurement. This is illustrated with projection operators on the top two wires to learn the value of x by measurment. The identity operator leaves the lower wire alone which now carriers the value of f(x).

\[ \begin{matrix} ~ & \text{f(0) = 1} \\ \text{kronecker} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}^T, ~ \text{kronecker} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}^T, ~ \text{I} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \frac{1}{2} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ ~ & \text{f(1) = 0} \\ \text{kronecker} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}^T, ~ \text{kronecker} \left[ \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}^T, ~ \text{I} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \frac{1}{2} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ ~ & \text{f(2) = 0} \\ \text{kronecker} \left[ \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}^T, ~ \text{kronecker} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}^T, ~ \text{I} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \frac{1}{2} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ ~ & \text{f(2) = 0} \\ \text{kronecker} \left[ \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}^T, ~ \text{kronecker} \left[ \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}^T, ~ \text{I} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0.5 \end{pmatrix} & \frac{1}{2} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

As Haroche and Raimond write, "It is, however, one thing to compute potentially at once all the values of f and quite another to be able to exploit this quantum parallelism and extract from it more information than from a mundane classical computation. The final stage of information acquisition must always be a measurement."

In summary, this tutorial has demonstrated how a quantum circuit can function as an algorithm for the evaluation of a mathematical function, and how the same algorithm is capable of parallel evaluations of that function. The exploitation of quantum parallelism for practical outcomes such as factorization requires more elaborate quantum circuits than the one presented here.

Appendix

As promised earlier the matrix form of the quantum circuit is displayed here. As can be seen it is sparse!

\[ \text{QuantumCircuit} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \nonumber \]

An important property of circuits in quantum computation is reversibility. The reversibility of the quantum circuit is demonstrated by showing that using it twice is equivalent to the identity operator.

\[ \text{QuantumCircuit}^2 = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \nonumber \]

An alternative summary of the calculation uses the truth tables for the NOT, CNOT and CnNOT directly.

\[ \begin{matrix} \text{NOT} & \text{CNOT} & \text{CnNOT} \\ \begin{pmatrix} 0 & ' & 1 \\ 1 & ' & 0 \end{pmatrix} & \begin{pmatrix} \text{Decimal} & \text{Binary} & ' & \text{Binary} & \text{Decimal} \\ 0 & 00 & ' & 00 & 0 \\ 1 & 01 & ' & 01 & 1 \\ 2 & 10 & ' & 11 & 3 \\ 3 & 11 & ' & 10 & 2 \end{pmatrix} & \begin{pmatrix} \text{Decimal} & \text{Binary} & ' & \text{Binary} & \text{Decimal} \\ 0 & 000 & ' & 000 & 0 \\ 1 & 001 & ' & 001 & 1 \\ 2 & 010 & ' & 010 & 2 \\ 3 & 011 & ' & 011 & 3 \\ 4 & 100 & ' & 101 & 5 \\ 5 & 101 & ' & 100 & 4 \\ 6 & 110 & ' & 111 & 7 \\ 7 & 111 & ' & 110 & 6 \end{pmatrix} \end{matrix} \nonumber \]

The calculations are summarized in table format as follows. The CnNOT is a three-qubit gate, but only the four input states in which the third qubit is |0> are needed. The CNOT operates on the second and third qubits, while the NOT gate operates only on the third qubit.

\[ \begin{matrix} |000 \rangle & \xrightarrow{CnNOT} & |0 \rangle |00 \rangle & \xrightarrow{I \otimes CNOT} & |00 \rangle |0 \rangle & \xrightarrow{I \otimes I \otimes NOT} & |00 \rangle |1 \rangle & f(0) = 1 \\ |010 \rangle & ~ & |0 \rangle |10 \rangle & ~ & |01 \rangle |1 \rangle & ~ & |01 \rangle |1 \rangle & f(1) = 0 \\ |100 \rangle & ~ & |1 \rangle |01 \rangle & ~ & |10 \rangle |1 \rangle & ~ & |10 \rangle |0 \rangle & f(2) = 0 \\ |110 \rangle & ~ & |1 \rangle |11 \rangle & ~ & |11 \rangle |0 \rangle & ~ & |11 \rangle |1 \rangle & f(3) = 1 \end{matrix} \nonumber \]

A superposition of all four input states would behave as follows under the operation of the quantum circuit.

\[ \frac{1}{2} \begin{pmatrix} |00 \rangle |0 \rangle \\ + \\ |01 \rangle |0 \rangle \\ + \\ |10 \rangle |0 \rangle \\ + \\ |11 \rangle |0 \rangle \end{pmatrix} \xrightarrow{CnNOT} \frac{1}{2} \begin{pmatrix} |0 \rangle |00 \rangle \\ + \\ |0 \rangle |10 \rangle \\ + \\ |1 \rangle |01 \rangle \\ + \\ |1 \rangle |11 \rangle \end{pmatrix} \xrightarrow{I \otimes CNOT} \frac{1}{2} \begin{pmatrix} |0 \rangle |00 \rangle \\ + \\ |0 \rangle |11 \rangle \\ + \\ |1 \rangle |01 \rangle \\ + \\ |1 \rangle |10 \rangle \end{pmatrix} \xrightarrow{I \otimes I \otimes NOT} \frac{1}{2} \begin{pmatrix} |00 \rangle |1 \rangle \\ + \\ |01 \rangle |0 \rangle \\ + \\ |10 \rangle |0 \rangle \\ + \\ |11 \rangle |1 \rangle \end{pmatrix} \xrightarrow{Decimal} \frac{1}{2} \begin{pmatrix} |0 \rangle |1 \rangle \\ + \\ |1 \rangle |0 \rangle \\ + \\ |2 \rangle |0 \rangle \\ + \\ |3 \rangle |1 \rangle \end{pmatrix} \nonumber \]

Another feature of this circuit is that if the bottom wire is measured, it projects the top two wires into a superposition of inputs that give the bottom wire result.

\[ \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \frac{1}{2} \left[ \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \right] \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \frac{1}{2} \left[ \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \right] \begin{pmatrix} 0 \\ 1 \end{pmatrix} \nonumber \]

\[ \begin{matrix} ~ & \text{f(1) = f(2) = 0} \\ \text{kronecker} \left[ \text{I, kronecker} \left[ \text{I}, ~ \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0.5 \\ 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \end{pmatrix} & \frac{1}{2} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \right] \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ ~ & \text{f(0) = f(3) = 1} \\ \text{kronecker} \left[ \text{I, kronecker} \left[ \text{I}, ~ \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \right] \right] \text{QuantumCircuit} \frac{1}{2} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0.5 \end{pmatrix} & \frac{1}{2} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right] \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{matrix} \nonumber \]

Here's an alternative analysis of the circuit operation.

\[ \begin{matrix} \frac{1}{2} \left[ |00 \rangle + |01 \rangle + |10 \rangle + |11 \rangle \right] |0 \rangle = \frac{1}{2} \left[ |000 \rangle + |010 \rangle + |100 \rangle + |110 \rangle \right] \\ \text{CnNOT} \\ \frac{1}{2} \left[ |000 \rangle + |010 \rangle + |101 \rangle + |111 \rangle \right] = \frac{1}{2} \left[ |0 \rangle |00 \rangle + |0 \rangle |10 \rangle + |1 \rangle |01 \rangle + |1 \rangle |11 \rangle \right] \\ \text{I} \otimes \text{CNOT} \\ \frac{1}{2} \left[ |0 \rangle |00 \rangle + |0 \rangle |11 \rangle + |1 \rangle |01 \rangle + |1 \rangle |10 \rangle \right] = \frac{1}{2} \left[ |00 \rangle |0 \rangle + |01 \rangle |1 \rangle + |10 \rangle |1 \rangle + |11 \rangle |0 \rangle \right] \\ \text{I} \otimes \text{I} \otimes \text{NOT} \\ \frac{1}{2} \left[ |00 \rangle |1 \rangle + |01 \rangle |0 \rangle + |10 \rangle |0 \rangle + |11 \rangle |1 \rangle \right] \xrightarrow{ \text{Decimal}} \frac{1}{2} \left[ |0 \rangle |1 \rangle + |1 \rangle |0 \rangle + |2 \rangle |0 \rangle + |3 \rangle |1 \rangle \right] \end{matrix} \nonumber \]