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 {\displaystyle O} that encodes two functions f {\displaystyle f} and g {\displaystyle g} , there is an n {\displaystyle n} -bit string s {\displaystyle s} for which g ( x ) = f ( x + s ) {\displaystyle g(x)=f(x+s)} for all x {\displaystyle x} . Find s {\displaystyle s} . Functions such as the Legendre symbol and bent functions satisfy these constraints.
Algorithms With a quantum algorithm that is defined as | s ⟩ = H ⊗ n O f H ⊗ n O g ^ H ⊗ n | 0 n ⟩ {\displaystyle |s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle } , where H {\displaystyle H} is the Hadamard gate and g ^ {\displaystyle {\hat {g}}} is the Fourier transform of g {\displaystyle g} , certain instantiations of this problem can be solved in a polynomial number of queries to O {\displaystyle O} while taking exponential queries with a classical algorithm.
References
