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

satisfying

with a constant, can we determine c?

First, let’s note that applying the Hadamard transform on an arbitrary n-qubit

which defines the n-Hadamard transform .

Put and start with a ground state of twice n-qubits and apply on the first n-qubits:

then apply the black-box function holding the result in the second register

applying the Hadamard treansform again

.

Now, the period divides the N kets into cosets containing each two elements (because of the addition ). The value on these cosets is constant and if we take in each coset a representative value we can reduce the sum over k by summing only over these representatives. Hence

.

If is not orthogonal to the term drops out, so measuring things will always reveal states which are orthogonal to . In fact, if you compute the probability of getting one of these states, call it , you get

.

If you repeatedly measure the first register you end up with a collection of vectors spanning a space orthogonal to the period 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.