Quantum mechanical algorithms for the nonabelian hidden subgroup problem (Q705722)

The hidden subgroup problem is at present the keystone problem in quantum computations. In particular, two famous examples of the exponential quantum speedup, the discrete logarithm and factoring problems, are the partial cases of the abelian hidden subgroup problem. In general, the abelian hidden subgroup can be effectively found with a quantum computer by repetition of coset state preparation and Fourier sampling. At the same time many of the basic computational problems can be reduced to the nonabelian hidden subgroup problem, which remains open. It is natural to generalize the Fourier transform method to the case of nonabelian groups. Considering this way authors obtain the negative results: with respect to a random choice of basis the Fourier sampling reveal, in general, an exponentially small amount of information about the hidden subgroup. On the positive side, there were obtained effective solutions for several important special cases of the nonabelian hidden subgroup problem. These solutions are discussed in the paper.