Sample complexity of hidden subgroup problem

07/07/2021
โˆ™
by   Zekun Ye, et al.
โˆ™
0
โˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset