9.9 Simon’s algorithm
There is one more algorithm using an oracle that we now cover before we leave this chapter and that is Simon’s algorithm. It may seem like an odd use of an oracle but the techniques are further used in section 10.5
9.9.1 The problem
Our problem is to find how the values of a function on whole numbers repeat themselves. Recall that by {0, 1}n we mean a string or sequence of n 0s and 1s. For example, if n = 2 then
{0, 1}2 = {00, 01, 10, 11} .
A function
f: {0, 1}n → {0, 1}n
takes such binary strings of length n to other such binary strings. For any two x and y in {0, 1}n, when does f(x) = f(y)?
In general, we don’t know, but we could require that there exists some r in {0, 1}n such that f(x) = f(y) if and only if x ⊕ y is in {0n, r}.
Here we have ‘‘⊕’’ being the binary xor function, which is addition modulo 2. (We covered modular...
