Encyclopedia

Hidden shift problem

Problem in computer science

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated December 12, 2025

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.

01Problem 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.

02Algorithms

With a quantum algorithm that is defined as $|s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle$ , 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.

Watch videos about Hidden shift problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Hidden shift problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.