8.69: Another Example of Deutsch's Algorithm

Last updated
Save as PDF

Page ID: 148509

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

See the previous tutorial "A Simple Solution to Deutsch's Problem" in this section for further detail on Deutsch's algorithm. This tutorial presents a similar example, so only a brief outline will be provided.

A certain function of x maps {0,1} to {0,1}. The four possible outcomes of the evaluation of f(x) are given in tabular form.

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

From the classical perspective, if the question (as asked by Deutsch) is whether f(x) is constant \((f(0) = f(1))\) or balanced \((f(0) \neq f(1))\) then one must calculate both f(0) and f(1) to answer the question as shown below.

The following circuit carries out,

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

where U_f (inverse controlled-NOT, followed by a NOT operation on the lower wire) is a unitary operator that accepts input |x> on the top wire and places f(x) on the bottom wire.

\[ \begin{matrix} |x \rangle & \cdots & \oplus & \cdots & \cdots & |x \rangle \\ ~ & ~ & | \\ |0 \rangle & \cdots & \cdot & \fbox{NOT} & \cdots & | f(x) \rangle \end{matrix} \nonumber \]

The required circuit elements in matrix format are:

\[ \begin{matrix} \text{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} & \text{H} = \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -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} = \text{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 \]

\[ \begin{matrix} ~ & \text{Input} & \text{Calculation} & \text{Output} \\ 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} \\ f(1) = 1 & \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 \\ 0 \\ 1 \end{pmatrix} & \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{matrix} \nonumber \]

We see by these operations of the circuit that f(x) is constant:

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

A quantum computer can also process a superposition of inputs, in this case a superposition of 0 and 1. The circuit produces a superposition of the outputs calculated above.

\[ \begin{matrix} \text{Input state}: & \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} \\ \text{Output state:} & \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] \end{matrix} \nonumber \]

However, this does not answer the balanced/constant question because observation of the output causes it to collapse to one value of the other, either |0>|1> or |1>|1>. Running the circuit just once will not answer the question.

Deutsch pointed out that quantum superpositions and the interference effects between them allow the answer to be given with one pass through a modified version of the circuit shown here.

\[ \begin{matrix} |0 \rangle & \triangleright & \fbox{H} & \cdots & \oplus & \cdots & \fbox{H} & \triangleright & \text{measure} \frac{|0 \rangle \text{ constant}}{|1 \rangle \text{ balanced}}\end{matrix} \nonumber \]

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

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

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

The appearance of |0 > on the top wire confirms that the function is constant with one pass through the circuit.

It is also possible using the following truth tables to trace the evolution of the input quibits through the quantum circuit.

Hadamard operation:

\[ \begin{bmatrix} 0 & ' & \text{H} & ' & \frac{1}{ \sqrt{2}} (0 + 1) & ' & \text{H} & ' & 0 \\ 1 & ' & \text{H} & ' & \frac{1}{ \sqrt{2}} (0-1) & ' & \text{H} & ' & 1 \end{bmatrix} \nonumber \]

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

\[ \begin{matrix} |01 \rangle \\ \text{H} \otimes \text{H} \\ \frac{1}{ \sqrt{2}} \left[ |0 \rangle + |1 \rangle \right] \frac{1}{ \sqrt{2}} \left[ |0 \rangle - |1 \rangle \right] = \frac{1}{2} \left[ |00 \rangle - |01 \rangle + |10 \rangle - |11 \rangle \right] \\ \text{ICNOT} \\ \frac{1}{2} \left[ |00 \rangle - |11 \rangle + |10 \rangle - |01 \rangle \right] = \frac{1}{2} \left( |0 \rangle +|1 \rangle \right) \left( |0 \rangle -|1 \rangle \right) \\ \text{I} \otimes \text{NOT} \\ \frac{1}{2} \left[ \left( |0 \rangle + |1 \rangle \right) \left( |1 \rangle - |0 \rangle \right) \right] \\ \text{H} \otimes \text{I} \\ |0 \rangle \frac{1}{ \sqrt{2}} \left( |1 \rangle - |0 \rangle \right) \end{matrix} \nonumber \]