The hidden subgroup problem

The topic of my research is the Hidden Subgroup Problem. The problem can be stated as follows: Problem. (Hidden Subgroup Problem) Let G be a finite group and H a subgroup. Given a black-box function f : G → S which is constant on (left)-cosets gH of H and takes different values for different cosets, determine a set of generators for H.;Efficient classical algorithms for the Hidden Subgroup Problem are not known. However, efficient quantum algorithms are known for this problem in some cases. One such algorithm implies Shor's famous efficient method for breaking the RSA cryptosystem.;An efficient solution of this problem in all cases would have wide implications in the field of theoretical computer science. For example it would most likely solve some classical problems which are neither NP-complete nor are in P. A solution would also imply a solution for Graph Isomorphism problem which is a long standing problem in computer science.;In the present thesis, we study some quantum algorithms for the Hidden Subgroup Problem. We discuss Quantum Fourier Tranform and its applications to the Hidden Subgroup Problem. We discuss Almost Abelian groups and show that there is a quantum algorithm that solves the Hidden Subgroup Problem for them. We also study the decision version of the problem. We compare two different formalizations of this concept. We show that these formalizations coincide in the case of abelian and Frobenius groups. We conclude with a family of groups where the formalizations may not coincide.