  The hidden subgroup problem ($\mathsf{HSP}$) has been attracting much
attention in quantum computing, since several well-known quantum algorithms
including Shor algorithm can be described in a uniform framework as quantum
methods to address different instances of it. One of the central issues about
$\mathsf{HSP}$ is to characterize its quantum/classical complexity. For
example, from the viewpoint of learning theory, sample complexity is a crucial
concept. However, while the quantum sample complexity of the problem has been
studied, a full characterization of the classical sample complexity of
$\mathsf{HSP}$ seems to be absent, which will thus be the topic in this paper.
$\mathsf{HSP}$ over a finite group is defined as follows: For a finite group
$G$ and a finite set $V$, given a function $f:G \to V$ and the promise that for
any $x, y \in G, f(x) = f(xy)$ iff $y \in H$ for a subgroup $H \in
\mathcal{H}$, where $\mathcal{H}$ is a set of candidate subgroups of $G$, the
goal is to identify $H$.
  Our contributions are as follows: For $\mathsf{HSP}$, we give the upper and
lower bounds on the sample complexity of $\mathsf{HSP}$. Furthermore, we have
applied the result to obtain the sample complexity of some concrete instances
of hidden subgroup problem. Particularly, we discuss generalized Simon's
problem ($\mathsf{GSP}$), a special case of $\mathsf{HSP}$, and show that the
sample complexity of $\mathsf{GSP}$ is $\Theta\left(\max\left\{k,\sqrt{k\cdot
p^{n-k}}\right\}\right)$. Thus we obtain a complete characterization of the
sample complexity of $\mathsf{GSP}$.
