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.[1] 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.[2][3]
With a quantum algorithm that is defined as , where is the Hadamard gate and 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.
References
↑ Childs, Andrew M.; van Dam, Wim (2007), "Quantum algorithm for a generalized hidden shift problem", in Bansal, Nikhil; Pruhs, Kirk; Stein, Clifford (eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, SIAM, pp.1225–1232, arXiv:quant-ph/0507190
↑ Lomont, Chris (November 4, 2004), The Hidden Subgroup Problem - Review and Open Problems, arXiv:quant-ph/0411037
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.