Hidden shift problem

In quantum computing, the hidden shift problem is a type of oracle-based problem. Various versions of this problem have quantum algorithms which can run much more quickly than known non-quantum methods for the same problem. In its general form, it is equivalent to the hidden subgroup problem for the dihedral group. It is a major open problem to understand how well quantum algorithms can perform for this task, as it can be applied to break lattice-based cryptography.

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}$.

Functions such as the Legendre symbol and bent functions, satisfy these constraints.

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.