8.67: Another Simple Example of Parallel Quantum Computation

This tutorial deals with quantum function evaluation and parallel computation. A certain function of x yields the following table of results.

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

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

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

The top wire carries the value of x and the bottom wire is initially set to |0 >. After operation of the controlled-NOT and NOT gates, x remains on the top wire while the bottom wire carries the value of the function, f(x). In other words,

\[ \hat{U}_f |x \rangle |0 \rangle = |x \rangle | f(x) \rangle \nonumber \]

The quantum gates in matrix form are:

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

\[ \begin{matrix} \text{QuantumCircuit = kronecker(I, NOT) ICNOT} & \text{QuantumCircuit} = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \end{matrix} \nonumber \]

Given the simplicity of the matrix representing the circuit, the following calculations can easily be done by hand.

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

These calculations demonstrate that the quantum circuit is a valid algorithm for the calculation of f(x). We now demonstrate parallel computation by putting |x> in a balanced superposition of |0> and |1>. As shown below, the operation of the circuit yields a superposition of the previous results. The function has been evaluated for both values of x in a single pass through the circuit.

\[ \begin{matrix} \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} & \text{QuantumCircuit} \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0.707 \\ 0 \\ 0.707 \end{pmatrix} \end{matrix} \nonumber \]

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

In summary, simple calculations have demonstrated how a quantum circuit can function as an algorithm for the evaluation of a mathematical function, and how the same circuit is capable of parallel evaluations of that function.

\[ \begin{matrix} \text{Input} & \text{Operation} & \text{Intermediate} & \text{Operation} & \text{Output} \\ |00 \rangle & ~ & |00 \rangle & ~ & |01 \rangle \\ |10 \rangle & \xrightarrow{ \text{ICNOT}} & |11 \rangle & \xrightarrow{ \text{I} \otimes \text{NOT}} & |10 \rangle \\ \frac{1}{ \sqrt{2}} \left[ |0 \rangle + |1 \rangle \right] |0 \rangle = \frac{1}{ \sqrt{2}} \left[ |00 \rangle + |10 \rangle \right] & ~ & \frac{1}{ \sqrt{2}} \left[ |00 \rangle + |10 \rangle \right] & ~ & \frac{1}{ \sqrt{2}} \left[ |01 \rangle + |11 \rangle \right] \end{matrix} \nonumber \]

However, on a practical level only one result can be realized for each operation of the circuit because on measurement the superposition created by the circuit collapses to one of the states forming the superposition.