In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as 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. The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel R. Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries. This problem yields an oracle separation between the complexity classes BPP (bounded-error classical query complexity) and BQP (bounded-error quantum query complexity). This is the same separation that the Bernstein–Vazirani algorithm achieves, and different from the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential. Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value. However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.
Problem description Simon's problem considers access to a function f : { 0 , 1 } n → { 0 , 1 } m , m ≥ n {\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n} as implemented by a black box or an oracle. This function is promised to be either a one-to-one function, or a two-to-one function; if f {\displaystyle f} is two-to-one, it is furthermore promised that two inputs x {\displaystyle x} and x ′ {\displaystyle x'} evaluate to the same value if and only if x {\displaystyle x} and x ′ {\displaystyle x'} differ in a fixed set of bits. I.e.,
If f {\displaystyle f} is not one-to-one, it is promised that there exists a non-zero s {\displaystyle s} such that, for all x ≠ x ′ {\displaystyle x\neq x'} , f ( x ) = f ( x ′ ) {\displaystyle f(x)=f(x')} if and only if x ′ = x ⊕ s {\displaystyle x'=x\oplus s}
where ⊕ {\displaystyle \oplus } denotes bitwise exclusive-or. Simon's problem asks, in its decision version, whether f {\displaystyle f} is one-to-one or two-to-one. In its non-decision version, Simon's problem asks whether f {\displaystyle f} is one-to-one or what is the value of s {\displaystyle s} (as defined above). The goal is to solve this task with the least number of queries (evaluations) of f {\displaystyle f} . Note that if x ′ = x {\displaystyle x'=x} , then f ( x ′ ) = f ( x ) {\displaystyle f(x')=f(x)} and x ′ = x ⊕ s {\displaystyle x'=x\oplus s} with s = 0 {\displaystyle s=0} . On the other hand (because a ⊕ b ⊕ b = a {\displaystyle a\oplus b\oplus b=a} for all a {\displaystyle a} and b {\displaystyle b} ), x ′ = x ⊕ s ⟺ x ′ ⊕ x = s {\displaystyle x'=x\oplus s\iff x'\oplus x=s} . Thus, Simon's problem may be restated in the following form:
Given black-box or oracle access to f {\displaystyle f} , promised to satisfy, for some s {\displaystyle s} and all x , x ′ {\displaystyle x,x'} , f ( x ) = f ( x ′ ) {\displaystyle f(x)=f(x')} if and only if x ′ ⊕ x ∈ { 0 , s } {\displaystyle x'\oplus x\in \{0,s\}} , determine whether s ≠ 0 {\displaystyle s\neq 0} (decision version), or output s {\displaystyle s} (non-decision version). Note also that the promise on f {\displaystyle f} implies that if f {\displaystyle f} is two-to-one then it is a periodic function:
… excerpt ends here. Continue reading the full article.
