Solving Shift Problems and the Hidden Coset Problem Using the Fourier Transform

ps (151kB), ps.gz (57kB), pdf (170kB) or djvu (81kB). Also quant-ph/0205034.

We give a quantum algorithm for solving a shifted multiplicative character problem over Z/nZ and finite fields. We show that the algorithm can be interpreted as a matrix factorization or as solving a deconvolution problem and give sufficient conditions for a shift problem to be solved efficiently by our algorithm. We also show that combining the shift problem with the hidden subgroup problem results in a hidden coset problem. This naturally captures the redundancy in the shift due to the periodic structure of multiplicative characters over Z/nZ.

Last modified November 25, 2003