Quantum and classical query complexities for generalized Simon's problem

Abstract

Simon's problem conceived by Simon is one of the most important examples demonstrating the faster speed of quantum computers than classical computers for solving some problems, and the optimal separation between exact quantum and classical query complexities for Simon's Problem has been proved by Cai and Qiu. Generalized Simon's problem is a generalization of Simon's problem, and it can be described as: Given a Boolean function $f:{\{0, 1\}}^n \to {\{0, 1\}}^m$, $n\leq m$, promised to satisfy the property that, for some subgroup $S\subseteq {\{0, 1\}}^n$, we have, for any $x, y\in {\{0, 1\}}^n$, $f(x)=f(y)$ if and only if $x \oplus y\in S$, where $|S|=2^k$ for some $0\leq k\leq n$. The problem is to find $S$. For the case of $k=1$, it is the Simon's problem. In this paper, we propose an exact quantum algorithm with $O(n-k)$ queries, and an exact classical algorithm with $O(k\sqrt{2^{n-k}})$ queries for solving the generalized Simon's problem. Then we show that the lower bounds on its exact quantum and classical deterministic query complexities are $\Omega(n-k)$ and $\Omega(\sqrt{k2^{n-k}})$ respectively. Therefore, we obtain the tight exact quantum query complexity $\Theta(n-k)$,and the classical deterministic query complexities $\Omega(\sqrt{k2^{n-k}}) \sim O(k\sqrt{2^{n-k}})$ for the generalized Simon's problem.