Author name cluster

Zekun Ye

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 2022 Journal Article

Deterministic algorithms for the hidden subgroup problem

Zekun Ye
Lvzhou Li

The hidden subgroup problem ( HSP ) plays a crucial role in the field of quantum computing, since several celebrated quantum algorithms including Shor's algorithm have a uniform description in the framework of HSP. The problem is as follows: for a finite group G and a finite set X, given a function f: G → X and the promise that for any g 1, g 2 ∈ G, f ( g 1 ) = f ( g 2 ) iff g 1 H = g 2 H for a subgroup H ≤ G, the goal of the decision version is to determine whether H is trivial, and the goal of the search version is to find H. Nayak (2021) asked whether there exist deterministic algorithms with O ( | G | | H | ) query complexity for HSP. We answer this problem for Abelian groups, which also extends the main results of Ye et al. (2021), since here the algorithms do not rely on any prior knowledge of H.

Details DOI

TCS Journal 2022 Journal Article

Sample complexity of hidden subgroup problem

Zekun Ye
Lvzhou Li

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.

Details DOI

I&C Journal 2021 Journal Article

Query complexity of generalized Simon's problem

Zekun Ye
Yunqi Huang
Lvzhou Li
Yuyi Wang

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP ( p, n, k ), is a natural extension of Simon's problem: Given a function f: Z p n → X where X is a finite set and the promise that for any x, y ∈ Z p n, f ( x ) = f ( y ) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k < n, the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O ( n − k ). However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP ( p, n, k ) has to query at least Ω ( max ⁡ { k, p n − k } ) values and any classical nonadaptive deterministic algorithm for GSP ( p, n, k ) has to query at least Ω ( max ⁡ { k, k ⋅ p n − k } ) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O ( max ⁡ { k, k ⋅ p n − k } ) on the classical deterministic query complexity of GSP ( p, n, k ), by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem.

Details DOI