Sample complexity of hidden subgroup problem

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 Simons problem ($mathsf{GSP}$), a special case of $mathsf{HSP}$, and show that the sample complexity of $mathsf{GSP}$ is $Thetaleft(maxleft{k,sqrt{kcdot p^{n-k}}right}right)$. Thus we obtain a complete characterization of the sample complexity of $mathsf{GSP}$.