Simon's Algorithm

Simon's Algorithm

In computational complexity theory and quantum computing, Simon's problem is a computational problem in the model of decision tree complexity or query complexity, conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm, usually called Simon's algorithm that solves the problem exponentially faster than any (deterministic or probabilistic) classical algorithm.

Simon's algorithm uses queries to the black box, whereas the best classical probabilistic algorithm necessarily needs at least queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires queries. This problem yields an oracle separation between BPP and BQP, unlike the separation provided by the Deutsch-Jozsa algorithm, which separates P and EQP.

Although the problem itself is of little practical value it is interesting because it provides an exponential speedup over any classical algorithm. Moreover, it was also the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.