Hidden shift problem

The hidden shift problem states: Given an oracle ${\displaystyle O}$ that encodes two functions ${\displaystyle f}$ and ${\displaystyle g}$, there is an ${\displaystyle n}$-bit string ${\displaystyle s}$ for which ${\displaystyle g(x)=f(x+s)}$ for all ${\displaystyle x}$. Find ${\displaystyle s}$.^[4]

Functions such as the Legendre symbol and bent functions satisfy these constraints.^[5]

With a quantum algorithm that is defined as ${\displaystyle |s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle }$, where ${\displaystyle H}$ is the Hadamard gate and ${\displaystyle {\hat {g}}}$ is the Fourier transform of ${\displaystyle g}$, certain instantiations of this problem can be solved in a polynomial number of queries to ${\displaystyle O}$ while taking exponential queries with a classical algorithm.