Simon's problem

Suppose $s\in\{0,1\}^n$ is nonzero, and $f:\{0,1\}^n\to\{0,1\}^n$ satisfies $f(x)=f(y)$ if and only if $x=y$ or $y=x\oplus s$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum algorithm that determines $s$ using expected $\mathcal{O}(n)$ queries to $O_f$, $\mathcal{O}(n^2)$ Hadamard gates, and $\mathcal{O}(n^3)$ classical operations over $\mathbb{F}_2$.