8.66: A Very Simple Example of Parallel Quantum 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 \\ \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{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \end{matrix} \nonumber \]

U_f (controlled-NOT, followed by a NOT operation on the lower wire) is a reversible operator. Doing it twice in succession on the initial two-qubit state is equivalent to the identity operation.

Kronecker is Mathcad's command for carrying out matrix tensor multiplication. Note that the identity operator is required when a wire is not involved in an operation. In what follows the quantum circuit is constructed, displayed and its reversibility demonstrated. In other words, repeating the circuit is equivalent to the identity operation. Reversibility is a crucial property in quantum computer circuitry.

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

\[ \begin{matrix} \text{QuantumCircuit} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} & \text{QuantumCircuit}^2 = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \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.707 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

\[ \frac{1}{ \sqrt{2}} \begin{pmatrix} 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} = \frac{1}{ \sqrt{2}} \left[ \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \right] = \frac{1}{ \sqrt{2}} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \right] \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."

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{CNOT}} & |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 + |11 \rangle \right] & ~ & \frac{1}{ \sqrt{2}} \left[ |01 \rangle + |10 \rangle \right] \end{matrix} \nonumber \]

However, as Haroche and Raimond note, 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. This is simulated with projection operators (|0><1|) on both registers for the four possible measurement outcomes for each value of x.

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

As Haroche and Raimond write, "It is, however, one thing to compute potentially at once all the values of f(x) 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." Therefore, the exploitation of quantum parallelism for practical purposes such as searches and factorization requires more elaborate quantum circuits than the one presented here.

Truth tables for quantum circuit elements:

\[ \begin{matrix} \text{Identity} & \begin{pmatrix} \text{0 to 0} \\ \text{1 to 1} \end{pmatrix} & \text{NOT} & \begin{pmatrix} \text{0 to 1} \\ \text{1 to 0} \end{pmatrix} & \text{CNOT} & \begin{pmatrix} \text{Decimal} & \text{Binary} & \text{to} & \text{Binary} & \text{Decimal} \\ 0 & 00 & \text{to} & 00 & 0 \\ 1 & 01 & \text{to} & 01 & 1 \\ 2 & 10 & \text{to} & \text{11} & 3 \\ 3 & 11 & \text{to} & 10 & 2 \end{pmatrix} \end{matrix} \nonumber \]