Simons problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simons problem has been proved by Cai $&$ Qiu. Generalized Simons problem can be described as follows. Given a function $f:{{0, 1}}^n to {{0, 1}}^m$, with the property that there is some unknown hidden subgroup $S$ such that $f(x)=f(y)$ iff $x oplus yin S$, for any $x, yin {{0, 1}}^n$, where $|S|=2^k$ for some $0leq kleq n$. The goal is to find $S$. For the case of $k=1$, it is Simons problem. In this paper, we propose an exact quantum algorithm with $O(n-k)$ queries and an non-adaptive deterministic classical algorithm with $O(ksqrt{2^{n-k}})$ queries for solving the generalized Simons problem. Also, we prove that their lower bounds are $Omega(n-k)$ and $Omega(sqrt{k2^{n-k}})$, respectively. Therefore, we obtain a tight exact quantum query complexity $Theta(n-k)$ and an almost tight non-adaptive classical deterministic query complexities $Omega(sqrt{k2^{n-k}}) sim O(ksqrt{2^{n-k}})$ for this problem.
Download