9.10 Simon’s algorithm
We’ll cover one more algorithm using an oracle before leaving this chapter: Simon’s algorithm. It may seem like an odd use of an oracle, but the techniques are further used in section 10.6 when we develop function period finding before tackling Shor’s factoring algorithm. algorithm$Simon’s Simon’s algorithm
We do not study Simon’s algorithm for its wide applicability. Rather, it demonstrates how a quantum algorithm can demonstrate an exponential improvement over the classical approach. So while this particular algorithm may not have much use, it gives people confidence that future quantum computing algorithms will perform significantly better than anything we can do today on problems of societal or commercial importance.
9.10.1 The problem
Our problem is finding how a function’s values on the whole numbers W repeat themselves.
A function
...
