# 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

$latex f:\{0,1\}^n\mapsto\{0,1\}^n$

satisfying

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

with $latex 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

$latex \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 $latex H^{(n)}$.

Put $latex N=2^n$ and start with a ground state of twice n-qubits $latex \psi_0 = |0\ldots 0\rangle|0\ldots 0\rangle$ and apply $latex H^{(n)}$ on the first n-qubits:

$latex \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

$latex \displaystyle\psi_2 = U_f\,|\psi_1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle|f(k)\rangle$

$latex \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 $latex c$ divides the N kets into cosets containing each two elements (because of the $latex \mathbb{Z}_2$ addition $latex \oplus$). The value on these cosets is constant and if we take in each coset a representative value $latex z$ we can reduce the sum over k by summing only over these representatives. Hence
$latex \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 $latex u$ is not orthogonal to $latex c$ the term drops out, so measuring things will always reveal states which are orthogonal to $latex c$. In fact, if you compute the probability of getting one of these states, call it $latex v$, you get
$latex \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 $latex 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.