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.

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1327136940 under CC BY-SA 4.0; modifications have been made.