Hidden shift problem explained

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.^[1]

Problem statement

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 .^[2]

Functions such as the Legendre symbol and bent functions, satisfy these constraints.^[3]

Algorithms

With a quantum algorithm that is defined as

|s\rangle = H ^{⊗} O _{f} H ^{⊗} O _{\hat{g} } H^|0^\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.

Notes and References

1. Regev . Oded . January 2004 . Quantum Computation and Lattice Problems . SIAM Journal on Computing . en . 33 . 3 . 738–760 . 10.1137/S0097539703440678 . 0097-5397.
2. quant-ph/0211140 . Dam . Wim van . Hallgren . Sean . Ip . Lawrence . Quantum Algorithms for some Hidden Shift Problems. 2002 . . 36 . 3 . 763–778 . 10.1137/S009753970343141X. 11122780 .
3. Book: 0811.3208 . Rötteler . Martin. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms . Quantum algorithms for highly non-linear Boolean functions. 2008 . 402 . 448–457 . 10.1137/1.9781611973075.37. 978-0-89871-701-3 . 9615826 . .