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
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.