Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite

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?

share|improve this question
4  
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

1 Answer

up vote 4 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.