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? –  Robin Kothari Dec 3 '12 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. –  Cris Stringfellow Dec 4 '12 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.

-
Well the order of H is actually what we are looking for. In fact if you know the order of H then you know H, since you know ord(G), since H is just the set of equivalent periods of elements of G under f. Also, it should be finding equivalent elements in different cosets of H, or simply any element of H. So where does that leave us? –  Cris Stringfellow Dec 4 '12 at 11:27
@CrisStringfellow: Did you mean the HSP in cyclic groups? Otherwise, for general abelian groups, knowing the order of H is not sufficient for knowing H, as in the example in my answer... –  Joshua Grochow Dec 4 '12 at 20:55
But do not the cosets of H partition G into |G|/|H| disjoint subsets? Even in general Abelian groups? –  Cris Stringfellow Dec 4 '12 at 21:18
Yes, but that does not imply that knowing |H| is the same as knowing H. The HSP is to find generators for the subgroup H, not just its order. However, in a cyclic group there is a unique subgroup of each order, which led to my suggestion in my previous comment. Note that the HSP for cyclic groups is enough for factoring, so factoring is a lower bound for cyclic HSP. –  Joshua Grochow Dec 5 '12 at 0:56
Yes I guess you're right about that. –  Cris Stringfellow Dec 5 '12 at 13:00