  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 $\mathsf{GSP}(p,n,k)$, is a natural
extension of Simon's problem. In this paper we consider the query complexity of
$\mathsf{GSP}(p,n,k)$. 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 $\mathsf{GSP}(p,n,k)$ has to query at least
$\Omega\left(\max\{k, \sqrt{p^{n-k}}\}\right)$ values and any classical
nonadaptive deterministic algorithm for $\mathsf{GSP}(p,n,k)$ has to query at
least $\Omega\left(\max\{k, \sqrt{k \cdot p^{n-k}}\}\right)$ 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\left(\max\{k, \sqrt{k \cdot
p^{n-k}}\}\right)$ on the classical deterministic query complexity of
$\mathsf{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.
