Complexity of Hidden Subgroup problems

Has anyone classified the (non-quantum) complexity of the hidden subgroup problem for finite Abelian groups? Is it known to be in any classical (not quantum) complexity classes?

• The problem is, of course, contained in some classical complexity class. Could you be more precise about what kind of answer you're looking for? Dec 3, 2012 at 23:17
• The kind of answer I want is : for some way of looking at the HSP for some finite Abelian group ( it does not matter which ), then there is a classical algorithm (unknown is fine) that solves HSP in time X with space Y. Decision problem : Given G, H, and f, and given n : is the order of any (unknown) element of H less than n? Or function problem is fine. The results on this with the smallest time/space requirements. Dec 4, 2012 at 11:28

If $G=\mathbb{Z}_{2}^{n}$ and the hidden subgroup $H$ has order $2$, then finding the hidden subgroup is equivalent to finding two elements in the same coset of $H$. The latter is in turn a birthday paradox-type problem, so should require $\Theta(\sqrt{|G|})$ queries for a randomized algorithm and $\Theta(|G|)$ queries for a deterministic algorithm. Note that $|G|=2^{n}$ is exponential in the input size.