7
$\begingroup$

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?

$\endgroup$
2
  • 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$ Dec 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$ Dec 4, 2012 at 11:28

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
6
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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