This article is part of a series on topological quantum computing.

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.