8.74: Aspects of Simon's Algorithm

Last updated
Save as PDF

Page ID: 148740

\( \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}}\)

A concealed quantum algorithm calculates f(x) from an input register containing a superposition of all x-values. Pairs of x-values (x, x') generate the same output. Simon's algorithm is an efficient method for finding the relationship between the pairs: \( \text{f(x) = f(x') = f(x} \oplus \text{s)}\), where s is a secret string and the addition on the right is bitwise modulo 2 . In a classical calculation one could compute f(x) until some pattern emerged and find the pairs by inspection. This approach is illustrated below.

\[ \begin{matrix} \text{Decimal} & \text{Binary} & ~ & \text{Binary} & \text{Decimal} \\ |0 \rangle & |000 \rangle & \xrightarrow{ f(0)} & |011 \rangle & |3 \rangle \\ |1 \rangle & |001 \rangle & \xrightarrow{f(1)} & |001 \rangle & |1 \rangle \\ |2 \rangle & |010 \rangle & \xrightarrow{f(2)} & |010 \rangle & |2 \rangle \\ |3 \rangle & |011 \rangle & \xrightarrow{f(3)} & |000 \rangle & |0 \rangle \\ |4 \rangle & |100 \rangle & \xrightarrow{f(4)} & |001 \rangle & |1 \rangle \\ |5 \rangle & |101 \rangle & \xrightarrow{f(5)} & |011 \rangle & |3 \rangle \\ |6 \rangle & |110 \rangle & \xrightarrow{f(6)} & |010 \rangle & |2 \rangle \end{matrix} \nonumber \]

The table of results reveals the pairs {(0,5), (1,4), (2,7), (3,6)} and that |s> = |101>. Adding |s> bitwise modulo 2 to any |x> reveals its partner |x'>.

The following quantum circuit is a rudimentary implementation of Simon's algorithm. The section in blue is the concealed algorithm. It has been discussed in two other tutorials: Quantum Parallel Calculation and An Illustration of the Deutsch-Jozsa Algorithm. Its operation yields the results shown in the following table.

\[ \begin{matrix} \begin{pmatrix} \text{x} & 0 & 1 & 2 & 3 \\ \text{f(x)} & 1 & 0 & 0 & 1 \end{pmatrix} \\ \begin{matrix} \text{Initial} & ~ & 1 & ~ & 2 & ~ & 3 & ~ & 4 & ~ & 5 & ~ & \text{Final} \\ |0 \rangle & \triangleright & \fbox{H} & \cdots & \cdot & \cdots & \cdots & \cdots & \cdots & \cdots & \fbox{H} & \triangleright \\ ~ & ~ & ~ & ~ & | \\ |0 \rangle & \triangleright & \fbox{H} & \cdots & | & \cdots & \cdot & \cdots & \cdots & \cdots & \fbox{H} & \triangleright \\ ~ & ~ & ~ & ~ & | & ~ & | \\ |0 \rangle & \triangleright & \cdots & \cdots & \oplus & \cdots & \oplus & \cdots & \fbox{NOT} & \cdots & \cdots & \triangleright & \text{Measure, 0 or 1} \end{matrix} \end{matrix} \nonumber \]

Next we prepare a table showing the results of a classical calculation. It is clear that the pairs are (0,3) and (1,2), and that |s> = |11>.

\[ \begin{matrix} \text{Decimal} & \text{Binary} & ~ & \text{Binary} & \text{Decimal} \\ |0 \rangle & |00 \rangle & \xrightarrow{f(0)} & |01 \rangle & |1 \rangle \\ |1 \rangle & |01 \rangle & \xrightarrow{ f(1)} & |00 \rangle & |0 \rangle \\ |2 \rangle & |10 \rangle & \xrightarrow{ f(2)} & |00 \rangle & |0 \rangle \\ |3 \rangle & |11 \rangle & \xrightarrow{ f(3)} & |01 \rangle & |1 \rangle \end{matrix} \nonumber \]

Now we examine the operation of the quantum circuit that implements Simon's algoritm by two different, but equivalent methods. The matrices representing the quantum gates in the circuit are:

\[ \begin{matrix} \text{I} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} & \text{NOT} = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix} & \text{H} = \frac{1}{ \sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \end{matrix} \nonumber \]

\[ \begin{matrix} \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 \]

The three qubit input state is: \( \Psi_{in} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}^T\)

The concealed algorithm: \( \text{U}_{ \text{f}} = \text{kronecker(I, kronecker(I, NOT)) kronecker(I, CNOT) CnNOT}\)

The complete quantum circuit: \( \text{QuantumCircuit = kronecker(H, kronecker(H, kronecker(H, I)) U}_{ \text{f}} \text{ kronecker(H, kronecker(H, I))}\)

The operation of the quantum circuit on the input state yields the following result:

\[ \begin{matrix} \text{QuantumCircuit} \Psi_{in} = \begin{pmatrix} 0.5 \\ 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ -0.5 \\ 0.5 \end{pmatrix} \begin{matrix} = \frac{1}{2} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right] \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \frac{1}{2} \left[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right] \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ = \frac{1}{2} \left[ |00 \rangle - |11 \rangle \right] |0 \rangle + \frac{1}{2} \left[ |00 \rangle +|11 \rangle \right] |1 \rangle \end{matrix} \end{matrix} \nonumber \]

The terms in brackets are superpositions of the x-values which are related by \( \text{x}' \text{x} = \oplus \text{s}\). Thus we see by inspection that |s> = |11>. The actual implementation of Simon's algorithm involves multiple measurements in order to determine the secret string. The Appendix modifies the quantum circuit to include the effect of measurement on the bottom wire.

The second method of analysis uses the following truth tables for the quantum gates and the operation of the Hadamard gate to trace the evolution of the input quibits through the quantum circuit.

\[ \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 \]

\[ \begin{matrix} \text{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} \end{matrix} \nonumber \]

\[ \begin{matrix} |000 \rangle \\ \text{H} \otimes \text{H} \otimes \text{I} \\ \frac{1}{ \sqrt{2}} \left[ |0 \rangle + |1 \rangle \right] \frac{1}{ \sqrt{2}} \left[ |0 \rangle + |1 \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] \\ \text{I} \otimes \text{CNOT} \\ \frac{1}{2} \left[ |000 \rangle + |011 \rangle + |101 \rangle + |110 \rangle \right] \\ \text{I} \otimes \text{I} \otimes \text{NOT} \\ \frac{1}{2} \left[ |001 \rangle + |010 \rangle + |100 \rangle + |111 \rangle \right] \\ \text{H} \otimes \text{H} \otimes \text{I} \\ \frac{1}{2} \left[ \left( |00 \rangle - |11 \rangle \right) |0 \rangle + \left( |00 \rangle + |11 \rangle \right) |1 \rangle \right] \end{matrix} \nonumber \]

Appendix

The circuit modification shown below includes the effect of measurement on the bottom wire.

Measure |0> on the bottom wire:

\[ \text{QuantumCircuit} = \text{kronecker} \left[ \text{H, kronecker} \left[ \text{H, } \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}^T \right] \right] \text{U}_f \text{kronecker(H, kronecker(H, I))} \nonumber \]

\[ \begin{matrix} \text{QuantumCircuit} \Psi_{in} = \begin{pmatrix} 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -0.5 \\ 0 \end{pmatrix} & \begin{pmatrix} 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -0.5 \\ 0 \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} 1 \\ 0 \end{pmatrix} \end{matrix} \nonumber \]

Measure |1> on the bottom wire:

\[ \text{QuantumCircuit} = \text{kronecker} \left[ \text{H, kronecker} \left[ \text{H, } \begin{pmatrix} 0 \\ 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}^T \right] \right] \text{U}_f \text{kronecker(H, kronecker(H, I))} \nonumber \]

\[ \begin{matrix} \text{QuantumCircuit} \Psi_{in} = \begin{pmatrix} 0 \\ 0.5 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0.5 \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 \]