Hidden shift problem
The hidden shift problem states: Given an oracle [math]\displaystyle{ O }[/math] that encodes two functions [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math], there is an [math]\displaystyle{ n }[/math]-bit string [math]\displaystyle{ s }[/math] for which [math]\displaystyle{ g(x) = f(x + s) }[/math] for all [math]\displaystyle{ x }[/math]. Find [math]\displaystyle{ s }[/math].[1] Many functions, such as the Legendre symbol and bent functions, satisfy these constraints.[2] With a quantum algorithm that is defined as [math]\displaystyle{ |s\rangle = H^{\otimes n} O_{f} H^{\otimes n} O_{\hat{g}} H^{\otimes n}|0^{n}\rangle }[/math], where [math]\displaystyle{ H }[/math] is the Hadamard gate and [math]\displaystyle{ \hat{g} }[/math] is the Fourier transform of [math]\displaystyle{ g }[/math], this problem can be solved in a polynomial number of queries to [math]\displaystyle{ O }[/math] while taking exponential queries with a classical algorithm. The difference between the hidden subgroup problem and the hidden shift problem is that the former focuses on the underlying group while the latter focuses on the underlying ring or field.[1]
References
- ↑ 1.0 1.1 Dam, Wim van; Hallgren, Sean; Ip, Lawrence (2002). "Quantum Algorithms for some Hidden Shift Problems". SIAM Journal on Computing 36 (3): 763–778. doi:10.1137/S009753970343141X.
- ↑ Rötteler, Martin (2008). "Quantum algorithms for highly non-linear Boolean functions". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. 402. Society for Industrial and Applied Mathematics. pp. 448–457. doi:10.1137/1.9781611973075.37. ISBN 978-0-89871-701-3.
 |  |
