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?
$\begingroup$
$\endgroup$
2
asked Dec 3, 2012 at 18:04
-
4$\begingroup$ 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? $\endgroup$– Robin KothariDec 3, 2012 at 23:17
-
$\begingroup$ 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. $\endgroup$– Cris StringfellowDec 4, 2012 at 11:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
answered Dec 3, 2012 at 22:34
-
$\begingroup$ 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? $\endgroup$ Dec 4, 2012 at 11:27
-
$\begingroup$ @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... $\endgroup$ Dec 4, 2012 at 20:55
-
$\begingroup$ But do not the cosets of H partition G into |G|/|H| disjoint subsets? Even in general Abelian groups? $\endgroup$ Dec 4, 2012 at 21:18
-
$\begingroup$ 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. $\endgroup$ Dec 5, 2012 at 0:56
-
$\begingroup$ Yes I guess you're right about that. $\endgroup$ Dec 5, 2012 at 13:00