We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm ...