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.

Problem statement

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

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

Algorithms

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