# Simon's problem

In computational complexity theory and quantum computing, Simon's problem is a computational problem conceived to showcase the efficiency increase a quantum algorithm could have over a classic one. Although the problem itself is of little practical value, it is interesting because it provides an exponential speedup over any classical algorithm (in a black box model).[1]

The problem deals with the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994.[2] 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 computational power than the best classical probabilistic algorithm.

This problem yields an oracle separation between 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.

## Problem description and algorithm

The input to the problem is a function (implemented by a black box) ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$, promised to satisfy the property that for some ${\displaystyle s\in \{0,1\}^{n}}$ we have for all ${\displaystyle y,z\in \{0,1\}^{n}}$, ${\displaystyle f(y)=f(z)}$ if and only if ${\displaystyle y=z}$ or ${\displaystyle y\oplus z=s}$. Note that the case of ${\displaystyle s=0^{n}}$ is allowed, and corresponds to ${\displaystyle f}$ being a permutation. The problem then is to find ${\displaystyle s}$.

The set of n-bit strings is a ${\displaystyle \mathbb {Z} _{2}}$ vector space under bitwise XOR. Given the promise, the preimage of f is either empty, or forms cosets with n-1 dimensions. Using quantum algorithms, we can, with arbitrarily high probability determine the basis vectors spanning this n-1 subspace since s is a vector orthogonal to all of the basis vectors.

Quantum subroutine in Simon's algorithm

Consider the Hilbert space consisting of the tensor product of the Hilbert space of input strings, and output strings. Using Hadamard operations, we can prepare the initial state

${\displaystyle \sum _{x}\left|x\right\rangle \left|0\right\rangle }$

and then call the oracle to transform this state to

${\displaystyle \sum _{x}\left|x\right\rangle \left|f(x)\right\rangle }$

Hadamard transforms convert this state to

${\displaystyle \sum _{y}\sum _{x}(-1)^{x.y}\left|y\right\rangle \left|f(x)\right\rangle }$

The following is not a step in the algorithm, but we can understand this quantity better if we factorize out the ${\displaystyle \left|y\right\rangle }$s out to get

${\displaystyle \sum _{y}\left|y\right\rangle \sum _{x}(-1)^{x.y}\left|f(x)\right\rangle }$

and observe that there are exacly two ${\displaystyle x}$s, which we shall call ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$, for which ${\displaystyle f(x_{1})=f(x_{2})}$. Since ${\displaystyle x_{2}=s\oplus x_{1}}$, we can rewrite the above as

${\displaystyle \sum _{y}\left|y\right\rangle \sum _{x_{1},x_{2}}((-1)^{x_{1}.y}+(-1)^{x_{2}.y})\left|f(x_{1})\right\rangle }$ where ${\displaystyle x_{2}=x_{1}\oplus s}$

The coefficient of ${\displaystyle \left|f(x)\right\rangle }$ is only ${\displaystyle 0}$ when ${\displaystyle (-1)^{x_{1}.y}+(-1)^{x_{2}.y}}$ is ${\displaystyle 0}$. Using the fact that ${\displaystyle x_{2}=x_{1}\oplus s}$, we see that that's the case precisely when the left hand side

${\displaystyle (-1)^{x_{1}.y}+(-1)^{x_{2}.y}=(-1)^{x_{1}.y}+(-1)^{(x_{1}\oplus s).y}=(-1)^{x_{1}.y}(1+(-1)^{y.s})}$ is ${\displaystyle 0}$, which is only the case if ${\displaystyle y.s}$ is ${\displaystyle 1}$.

The final step in the algorithm is to measure both registers. The only ${\displaystyle y}$ that we can get back is one that satisfies ${\displaystyle s.y=0}$. This determines a subspace which ${\displaystyle s}$ must lie on. Given enough such samples ${\displaystyle y}$, ${\displaystyle s}$ is constrained to a ${\displaystyle 0}$-dimensional subspace, which means we've determined ${\displaystyle s}$.

## Complexity

Simon's algorithm requires ${\displaystyle O(n)}$ queries to the black box, whereas a classical algorithm would need at least ${\displaystyle \Omega (2^{n/2})}$ queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires ${\displaystyle \Omega (n)}$ queries.[3][4]