Simon's algorithm

Simon's algorithm is one of the first Quantum algorithms discovered which outperforms any known classical algorithm. Let $f:\{0,1\}^n\; ightarrow\; \{0,1\}^n$ be such that for some $xin\; \{0,1\}^n$ we have for all $y,zin\{0,1\}^n$

$f(y)=f(z)$ if and only if $y=z$ or $yoplus\; z\; =x$.

Although the problem itself is of little practical value it provides an exponential improvement in time over any known classical algorithm. To find $x$ using a classical randomized algorithm $Omega(2^\{n/2\})$ queries of $f$ would be required. Using Simon's algorithm we are able to find a solution with high probability using $O(n)$ queries of $f$. It was also the inspiration for Shor's algorithm