<p>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.</p>

CC BY-SA 3.0
2012-12-04T11:27:51.650Z
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
CC BY-SA 3.0
2012-12-04T20:55:34.113Z
@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
CC BY-SA 3.0
2012-12-04T21:18:38.233Z
But do not the cosets of H partition G into |G|/|H| disjoint subsets? Even in general Abelian groups?
Cris Stringfellow
CC BY-SA 3.0
2012-12-05T00:56:02.490Z
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
CC BY-SA 3.0
2012-12-05T13:00:22.343Z
Yes I guess you're right about that.
Cris Stringfellow
CC BY-SA 3.0
2017-04-30T23:20:53.020Z
@JoshuaGrochow Don't all HSP for abelian groups have qpoly time algorithms? Doesn't that mean your $\Theta(|G|^\alpha)$ bound for classical implies quantum - classical separation which is open?
Turbo
CC BY-SA 4.0
2024-02-14T11:30:26.757Z
If the group is given as a Cayley table then the hidden subgroup is solvable in polynomial time?
David
CC BY-SA 4.0
2024-02-14T13:58:53.630Z
@David yes it is true that Hidden Subgroup is solvable in polynomial time when the group G is given as a Cayley table.
Shi
CC BY-SA 3.0
2012-12-03T22:34:11.440Z
2012-12-03T22:34:11.440Z
Joshua Grochow
<p>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? </p>

CC BY-SA 3.0
2012-12-03T23:17:52.077Z
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
CC BY-SA 3.0
2012-12-04T11:28:33.273Z
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
<complexity-classes>
Complexity of Hidden Subgroup problems
Cris Stringfellow
# Complexity of Hidden Subgroup problems

(Asked by: username_0 on 2012-12-03)

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?

**Tags:** complexity-classes

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-12-03. Score: 4

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: @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...  
> **username_0**: But do not the cosets of H partition G into |G|/|H| disjoint subsets? Even in general Abelian groups?  
> **username_2**: 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.  
> **username_0**: Yes I guess you're right about that.  
> **username_3**: @JoshuaGrochow Don't all HSP for abelian groups have qpoly time algorithms? Doesn't that mean your $\Theta(|G|^\alpha)$ bound for classical implies quantum - classical separation which is open?  
> **username_4**: If the group is given as a Cayley table then the hidden subgroup is solvable in polynomial time?  
> **username_5**: @username_4 yes it is true that Hidden Subgroup is solvable in polynomial time when the group G is given as a Cayley table.  

---

