Sample complexity of hidden subgroup problem

The hidden subgroup problem ( HSP ) has been attracting much attention in quantum computing, since several well-known quantum algorithms including Shor's algorithm can be described in a uniform framework as quantum methods to address different instances of it. One of the central issues about 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 HSP seems to be absent, which will thus be the topic in this paper. HSP 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 ( x y ) iff y ∈ H for a subgroup H ∈ H, where H is a set of candidate subgroups of G, the goal is to identify H. Our contributions are as follows: i) For HSP, we show that the number of uniform examples necessary to learn the hidden subgroup with bounded error is at least Ω ( min H ∈ H ′ ⁡ max ⁡ { log ⁡ | H ′ | log ⁡ | G | | H |, | G | | H | log ⁡ | H ′ | log ⁡ | G | | H | } ), where H ′ = H ∖ { G }; on the other hand, O ( max H ∈ H ⁡ { r ( H ), | G | | H | r ( H ) } ) uniform examples are sufficient, where r ( H ) is the rank of H. ii) By concretizing the parameters of HSP, we consider a class of restricted Abelian hidden subgroup problem ( rAHSP ) and obtain the upper and lower bounds for the sample complexity of rAHSP. iii) We continue to discuss a special case of rAHSP, generalized Simon's problem ( GSP ), and show that the sample complexity of GSP is Θ ( max ⁡ { k, k ⋅ p n − k } ). Thus we obtain a complete characterization of the sample complexity of GSP.

Authors

• Zekun Ye
• Lvzhou Li

Keywords

• Hidden subgroup problem
• Sample complexity
• Finite group
• Quantum computing