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.
Read more about Simon's Algorithm: Problem Description and Algorithm, See Also
Famous quotes containing the word simon:
“Given for one instant an intelligence which could comprehend all the forces by which nature is animated and the respective positions of the beings which compose it, if moreover this intelligence were vast enough to submit these data to analysis, it would embrace in the same formula both the movements of the largest bodies in the universe and those of the lightest atom; to it nothing would be uncertain, and the future as the past would be present to its eyes.”
—Pierre Simon De Laplace (1749–1827)