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

that encodes two functions

and

, there is an

-bit string

for which

g(x)=f(x+s)

for all

. Find

.^[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_fH^⊗O_\hat{g

} H^|0^\rangle , where

is the Hadamard gate and

\hat{g}

is the Fourier transform of

, certain instantiations of this problem can be solved in a polynomial number of queries to

while taking exponential queries with a classical algorithm.

Notes and References

Regev . Oded . January 2004 . Quantum Computation and Lattice Problems . SIAM Journal on Computing . en . 33 . 3 . 738–760 . 10.1137/S0097539703440678 . 0097-5397.
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 .
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 . .