Solving Shift Problems and Hidden Coset Problem Using the Fourier Transform

Lawrence Ip

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 factorizat…