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

| last1 = Childs | first1 = Andrew M.

| last2 = van Dam | first2 = Wim

| editor1-last = Bansal | editor1-first = Nikhil

| editor2-last = Pruhs | editor2-first = Kirk

| editor3-last = Stein | editor3-first = Clifford

| arxiv = quant-ph/0507190

| contribution = Quantum algorithm for a generalized hidden shift problem

| contribution-url = https://dl.acm.org/citation.cfm?id=1283383.1283515

| pages = 1225–1232

| publisher = SIAM

| title = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007

| year = 2007}} 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.{{Citation |last=Lomont |first=Chris |title=The Hidden Subgroup Problem - Review and Open Problems |date=2004-11-04 |arxiv=quant-ph/0411037 }}{{Cite journal |last=Regev |first=Oded |date=January 2004 |title=Quantum Computation and Lattice Problems |url=http://epubs.siam.org/doi/10.1137/S0097539703440678 |journal=SIAM Journal on Computing |language=en |volume=33 |issue=3 |pages=738–760 |doi=10.1137/S0097539703440678 |issn=0097-5397}}

Problem statement

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

{{Cite journal | arxiv=quant-ph/0211140 |last1=Dam |first1=Wim van |last2=Hallgren |first2=Sean |last3=Ip |first3=Lawrence |title =Quantum Algorithms for some Hidden Shift Problems|year =2002 |journal= SIAM Journal on Computing |volume=36 |issue=3 |pages=763–778 |doi=10.1137/S009753970343141X|s2cid=11122780 }}

Functions such as the Legendre symbol and bent functions, satisfy these constraints.{{Cite book | arxiv=0811.3208 |last1=Rötteler |first1=Martin|title=Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms |chapter = Quantum algorithms for highly non-linear Boolean functions|year =2008 |volume=402 |pages=448–457 |doi=10.1137/1.9781611973075.37|isbn=978-0-89871-701-3 |s2cid=9615826 |publisher=Society for Industrial and Applied Mathematics }}

Algorithms

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.

References

Category:Quantum algorithms