Sample complexity of hidden subgroup problem
share
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
