8
$\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$
8
  • $\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
  • 2
    $\begingroup$ If the group is given as a Cayley table then the hidden subgroup is solvable in polynomial time? $\endgroup$
    – David
    Feb 14 at 11:30
  • 2
    $\begingroup$ @David yes it is true that Hidden Subgroup is solvable in polynomial time when the group G is given as a Cayley table. $\endgroup$
    – Shi
    Feb 14 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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