# Simon’s quantum algorithm

The Deutsch algorithm helped discovering the total value of a binary function. The Josza extension helped discover whether a function is constant or balanced. The Simon algorithm deals with discovering periodic patterns in a function. Specifically, given a function $f:\{0,1\}^n\mapsto\{0,1\}^n$

satisfying $f(x)=f(y) \Leftrightarrow x = y \oplus c$

with $c = c_0\dots c_{n-1}$ a constant, can we determine c?

First, let’s note that applying the Hadamard transform on an arbitrary n-qubit $\displaystyle H\,|k_{n-1}\dots k_0\rangle = \frac{1}{2^{n/2}}\big((|0\rangle + (-)^{k_{n-1}}|1\rangle)\ldots (|0\rangle + (-)^{k_0}|1\rangle) \big) \\\;=\displaystyle \frac{1}{2^{n/2}}\sum_u (-)^{k.u}\,|u\rangle = H^{(n)}\,|k\rangle$

which defines the n-Hadamard transform $H^{(n)}$.

Put $N=2^n$ and start with a ground state of twice n-qubits $\psi_0 = |0\ldots 0\rangle|0\ldots 0\rangle$ and apply $H^{(n)}$ on the first n-qubits: $\displaystyle\psi_1 = H^n\,|0\rangle|0\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle|0\rangle$

then apply the black-box function holding the result in the second register $\displaystyle\psi_2 = U_f\,|\psi_1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle|f(k)\rangle$

applying the Hadamard treansform again $\displaystyle\psi_3 = U_f\,|\psi_1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\big(\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}(-)^{m.k}|m\rangle\big)|f(k)\rangle$.

Now, the period $c$ divides the N kets into cosets containing each two elements (because of the $\mathbb{Z}_2$ addition $\oplus$). The value on these cosets is constant and if we take in each coset a representative value $z$ we can reduce the sum over k by summing only over these representatives. Hence $\displaystyle\psi_3 = \frac{1}{N}\sum_{u=0}^{N-1}|u\rangle\,\sum_m|f(m)\rangle(-)^{m.u}\big(1+(-)^{c.u}\big)$.

If $u$ is not orthogonal to $c$ the term drops out, so measuring things will always reveal states which are orthogonal to $c$. In fact, if you compute the probability of getting one of these states, call it $v$, you get $\displaystyle\frac{1}{N^2}\sum_m\,\langle f(m)|\, f(m)\rangle\,|1+(-)^{c.v}|^2 = \frac{1}{2^{n-1}}$.

If you repeatedly measure the first register you end up with a collection of vectors spanning a space orthogonal to the period $c$ which hence delivers the period. Note that the measurement collapses the state in each case and the procedure is destructive. So, this algorithm is not as magical as the Deutsch-Josza algorithm but still requires exponentially less power than any classical version.