  One of the central issues in the hidden subgroup problem is to bound the
sample complexity, i.e., the number of identical samples of coset states
sufficient and necessary to solve the problem. In this paper, we present
general bounds for the sample complexity of the identification and decision
versions of the hidden subgroup problem. As a consequence of the bounds, we
show that the sample complexity for both of the decision and identification
versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden
subgroups in the case that the candidate subgroups have the same prime order
$p$, which implies that the decision version is at least as hard as the
identification version in this case. In particular, it does so for the
important instances such as the dihedral and the symmetric hidden subgroup
problems. Moreover, the upper bound of the identification is attained by the
pretty good measurement. This shows that the pretty good measurement can
identify any hidden subgroup of an arbitrary group with at most $O(\log|\HH|)$
samples.
