Sample complexity of hidden subgroup problem
The hidden subgroup problem (๐ง๐ฒ๐ฏ) 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 ๐ง๐ฒ๐ฏ 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 ๐ง๐ฒ๐ฏ seems to be absent, which will thus be the topic in this paper. ๐ง๐ฒ๐ฏ over a finite group is defined as follows: For a finite group G and a finite set V, given a function f:G โ V and the promise that for any x, y โ G, f(x) = f(xy) iff y โ H for a subgroup H โโ, where โ is a set of candidate subgroups of G, the goal is to identify H. Our contributions are as follows: For ๐ง๐ฒ๐ฏ, we give the upper and lower bounds on the sample complexity of ๐ง๐ฒ๐ฏ. 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 (๐ฆ๐ฒ๐ฏ), a special case of ๐ง๐ฒ๐ฏ, and show that the sample complexity of ๐ฆ๐ฒ๐ฏ is ฮ(max{k,โ(kยท p^n-k)}). Thus we obtain a complete characterization of the sample complexity of ๐ฆ๐ฒ๐ฏ.
READ FULL TEXT