Simon's problem

In the computational complexity theory and quantum computing, Simon's problem is a computational problem that can be solved exponentially faster on a quantum computer than on a classical (or traditional) computer. Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm. In the computational complexity theory and quantum computing, Simon's problem is a computational problem that can be solved exponentially faster on a quantum computer than on a classical (or traditional) computer. Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm. The problem is set in the model of decision tree complexity or query complexity and was 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, requiring exponentially less computation time (or more precisely, queries) than the best classical probabilistic algorithm. This problem yields an oracle separation between the complexity classes BPP and BQP, unlike the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Simon's algorithm 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. Given a function (implemented by a black box or oracle) f : { 0 , 1 } n → { 0 , 1 } n {displaystyle f:{0,1}^{n} ightarrow {0,1}^{n}} , promised to satisfy the property that, for some s ∈ { 0 , 1 } n {displaystyle sin {0,1}^{n}} , we have, for all x , y ∈ { 0 , 1 } n {displaystyle x,yin {0,1}^{n}} , In the case s = 0 n {displaystyle s=0^{n}} , then f {displaystyle f} is required to be a one-to-one function (otherwise it is a two-to-one function, that is, two inputs map to the same output). Note that x ⊕ y = 0 n {displaystyle xoplus y=0^{n}} if and only if x = y {displaystyle x=y} . So, in other words, f {displaystyle f} is a function such that f ( x ) = f ( x ⊕ s ) {displaystyle f(x)=f(xoplus s)} , for all x ∈ { 0 , 1 } n {displaystyle xin {0,1}^{n}} and given some fixed and unknown s ∈ { 0 , 1 } n {displaystyle sin {0,1}^{n}} . The problem is to find s {displaystyle s} . For example, if n = 3 {displaystyle n=3} , then the following function is an example of a function that satisfies the required and just mentioned property: