# Query complexity of generalized Simon’s problem

Zekun Ye  Yunqi Huang  Lvzhou Li  Yuyi Wang  School of Data and Computer
Science, Sun Yat-Sen University, Guangzhou 510006, China  Ministry of
Education Key Laboratory of Machine Intelligence and Advanced Computing (Sun
Yat-sen University), Guangzhou 510006, China  Disco Group, ETH Zurich,
Switzerland

###### Abstract

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: Given a function $f:\mathbb{Z}_{p}^{n}\to X$
where $X$ is a finite set and the promise that for any
$x,y\in\mathbb{Z}_{p}^{n},f(x)=f(y)$ iff $x-y\in S$ for a subgroup
$S\leq\mathbb{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 $\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.

###### keywords:

Simon’s problem, query complexity, quantum computing, group theory

##  1 Introduction

Query complexity, also called decision tree complexity [22], is the
computational complexity of a problem or algorithm expressed in terms of the
decision tree model. It has been very useful for understanding the power of
different computational models. In contrast to the Turing machine world where
lower bounds and separations between complexity classes often have to rely on
unproven conjectures, using query complexity can often prove tight lower
bounds and have provable separations between different computational models.
For instance, quantum computing has been shown to have exponential advantages
over classical computing in terms of query complexity.

Simon’s problem is well known in the history of quantum algorithms. It shows
an exponential gap between classical and quantum computing. The definition of
Simon’s problem is as follows.

Given: An (unknown) function $f:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$.

Promise: There exists a nonzero element $s\in\\{0,1\\}^{n}$ such that for all
$g,h\in\\{0,1\\}^{n},f(g)=f(h)$ iff $g=h$ or $g=h\oplus s$.

Problem: Find $s$.

Simon [36] proposed a quantum algorithm to efficiently find $s$. Shortly
afterward, inspired by this algorithm, Shor discovered the celebrated quantum
algorithm for the integer factorization problem [35]. Actually, Simon’s
problem and its variants have attracted a lot of attention from the academic
community [4, 10, 14, 26, 28, 32, 34, 38]. More details will be introduced in
the section of related work soon.

###  1.1 Problem statement and our results

Several extended versions of Simon’s problem with a minor difference have been
studied from the viewpoint of quantum computing [4, 10, 26, 32, 38]. An
extended version of Simon’s problem can be described as: Given an (unknown)
function $f:\mathbb{Z}_{2}^{n}\to X$ with a finite set $X$ and a positive
integer $k<n$, it is promised that there exists a subgroup
$S\leq\mathbb{Z}_{2}^{n}$ of rank $k$ such that for any
$x,y\in\mathbb{Z}_{2}^{n},f(x)=f(y)$ iff $x\oplus y\in S$, and then the goal
is to find $S$. This problem is a natural extension since Simon’s problem is a
special case of it with $k=1$.

######  Example 1.

We present an example of the above generalized Simon’s problem in Table 1. In
this example, $n=4$, $k=2$, and we can find that
$S=\\{0000,0011,0110,0101\\}$.

Table 1: An example of the generalization of Simon’s problem $x$ | $f(x)$
---|---
0000 | 0011 | 0110 | 0101 | 0000
0001 | 0010 | 0111 | 0100 | 0001
1000 | 1011 | 1110 | 1101 | 0010
1001 | 1010 | 1111 | 1100 | 0011

In this paper, we consider a more general extension of Simon’s problem, called
a generalized Simon’s problem as follows. In this case, we generalize the
domain of $f$ from $\mathbb{Z}_{2}^{n}$ to $\mathbb{Z}_{p}^{n}$, where $p$ is
a prime.

Given: An (unknown) function $f:\mathbb{Z}_{p}^{n}\to X$, where $X$ is a
finite set, and a positive integer $k<n$.

Promise: There exists a subgroup $S\leq\mathbb{Z}_{p}^{n}$ of rank $k$ such
that for any $x,y\in\mathbb{Z}_{p}^{n},f(x)=f(y)$ iff $x-y\in S$.

Problem: Find $S$.

For convenience, we use $\mathsf{GSP}(p,n,k)$ to denote the above problem with
parameter $n,p,k$ throughout this paper. It is easy to see that Simon’s
problem is a special case of $\mathsf{GSP}(p,n,k)$ with $p=2$ and $k=1$.

To find the subgroup $S$, we need to design an algorithm that is allowed to
access the function $f$ by querying an oracle that, given $x$, outputs $f(x)$.
According to randomness, algorithms can be divided into deterministic
algorithms and randomized algorithms. Deterministic algorithms solve the
problem with certainty, whereas randomized algorithms solve the problem with
bounded error probability. Moreover, we also study a class of widely studied
algorithms, nonadaptive algorithms, where current queries are not allowed to
depend on the result of previous queries.

The deterministic query complexity of $\mathsf{GSP}(p,n,k)$ is the query
complexity of the optimal deterministic algorithm for that, and the query
complexity of an algorithm is the number of queries it makes in the worst
case. the randomized and nonadaptive deterministic query complexities of
$\mathsf{GSP}(p,n,k)$ can be defined in a similar way.

In this paper, we obtain some characterizations of the query complexity of
$\mathsf{GSP}(p,n,k)$ in the following theorems.

######  Theorem 1 (Lower bound).

Any classical (deterministic or randomized) algorithm solving
$\mathsf{GSP}(p,n,k)$ needs to make
$\Omega\left(\max\\{k,\sqrt{p^{n-k}}\\}\right)$ queries.

######  Theorem 2 (Lower bound).

Any nonadaptive classical deterministic algorithm solving
$\mathsf{GSP}(p,n,k)$ needs $\Omega\left(\max\\{k,\sqrt{k\cdot
p^{n-k}}\\}\right)$ queries.

######  Theorem 3 (Upper bound).

There exists a classical deterministic algorithm to solve
$\mathsf{GSP}(p,n,k)$ using $O\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$
queries.

######  Remark 1.

When $p=2$ and $k=1$, the query complexity is $\Theta(\sqrt{2^{n}})$ which is
the same as the result presented in [14, 16].

To prove the theorems above, we first use the double-counting method and the
adversary method to obtain the lower bounds. Furthermore, we design a
classical deterministic algorithm, obtaining the upper bound of the query
complexity. Our algorithm is based on group theory and the divide-and-conquer
technique.

Table 2: Known results about the query complexity of Simon’s problem and
generalized Simon’s problem. The randomized, deterministic and nonadaptive
deterministic query complexities of $\mathsf{GSP}(p,n,k)$ are obtained in this
paper.

| quantum | randomized/deterministic | nonadaptive deterministic
---|---|---|---
Simon’s problem |  $\Theta(n)$ [10, 14, 28, 32, 36] |  $\Theta(\sqrt{2^{n}})$[14, 16]
$\mathsf{GSP}(p,n,k)$ |  $\Theta(n-k)$111The work in [23] implies that $\mathsf{GSP}(p,n,k)$ can be solved in $O(n-k)$ queries by a quantum algorithm with bounded error. Moreover, it can be solved by an exact quantum algorithm with $O(n-k)$ queries, if we slightly adjust the algorithms in [10] (see A). Additionally, by generalizing the lower bound method of [28], it was found that any quantum algorithm for $\mathsf{GSP}(p,n,k)$ has to query at least $\Omega(n-k)$ times with $p=2$ [38]. It is trivial to obtain the same result for general $p$. |  $\Omega\left(\max\\{k,\sqrt{p^{n-k}}\\}\right)$, $O\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$ | $\Omega\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$

###  1.2 Motivation

Simon’s problem plays a key role in the history of quantum algorithms and
recently it has been found useful for applications in cryptography. First, the
quantum algorithm [36] for this problem inspired the discovery of Shor’s
algorithm [35] solving integer factorization in polynomial time, and also
inspired Buhrman et al. [12] to propose the first exponential speed-up for
quantum property testing. Furthermore, Simon’s algorithm can be used to show
the insecurity of commonly used cryptographic symmetric-key primitives. For
example, Kaplan et al. [25] showed that several classical attacks based on
finding collisions can be exponentially speeded up using Simon’s algorithm.
Moreover, it was used to break the 3-round Feistel construction [30] and then
to prove that the Even-Mansour construction [31] is insecure with
superposition queries. Also, it can be used to quantum related-key attacks
[33].

$\mathsf{GSP}(p,n,k)$ is a natural extended version of Simon’s problem and
also a special case of the hidden subgroup problem. The motivations for
studying $\mathsf{GSP}(p,n,k)$ are as follows.

  * 1.

First, from the viewpoint of quantum computing, characterizing the classical
query complexity of $\mathsf{GSP}(p,n,k)$ is necessary for clarifying the
computational power gap between quantum and classical computing on this
problem. Note that we have a comprehensive understanding of the quantum query
complexity for $\mathsf{GSP}(p,n,k)$ (see Table 2). However, as far as we
know, how well does a classical algorithm perform on this problem still needs
to be explored.

  * 2.

Second, from the viewpoint of classical computing, it is an interesting
problem to reveal the query complexity of $\mathsf{GSP}(p,n,k)$, as it
generalizes the well-studied Simon’s problem and the ideas to solve the
generalized problems are completely different from that for the original one.
$\mathsf{GSP}(p,n,k)$ is a more general problem in mathematics, and the hidden
law behind it is worth exploring. Based on our in-depth study, we find this
problem seems not so straightforward to solve, instead, it involves several
techniques, such as the double-counting method, the adversary method, and the
divide-and-conquer method.

###  1.3 Related work

Query complexity is a very successful measurement to study the relative power
of quantum and classical computing. For quantum computing, query models can be
divided into bounded-error and exact versions in terms of their outputs. A
bounded-error model requires that the algorithm gives the correct result with
some sufficiently high probability, while an exact model means that the
algorithm gives the correct result with certainty. For the bounded-error case,
there is much work showing the advantage of quantum algorithms over classical
ones in terms of query complexity, e.g., [2, 3, 13]. However, the results for
exact query algorithms seem more limited. For total Boolean functions, Beals
et al. [9] showed that quantum query algorithms only achieve polynomial speed-
up over classical counterparts. In 2013, Ambainis [5] presented the first
example that exact quantum computing has a superlinear advantage over
deterministic algorithms. This result has been further improved by [6] with a
quadratic gap between its quantum and deterministic query complexity. On the
other hand, for computing partial functions, there exists a super-exponential
separation as shown by the famous Deutsch-Jozsa algorithm [17]: constant
versus linear.

In 1994, Simon’s problem was shown to be solvable on quantum computers with
$O(n)$ queries in the bounded-error setting. The lower bound of query
complexity was proved to be $\Omega(n)$ in [28] by applying the polynomial
method [9]. For exact quantum query algorithms, Brassard and Høyer [10] solved
the problem with $O(n)$ queries. Compared with their algorithm, Mihara and
Sung [32] proposed a simpler exact quantum algorithm. Apart from quantum
algorithms, Cai and Qiu [14] designed a classical deterministic algorithm for
solving Simon’s problem with $O(\sqrt{2^{n}})$ queries and proved their
algorithm is optimal in terms of query complexity.

Moreover, Simon’s problem is a special case of a well-studied class of
problems, the so-called hidden subgroup problem. That is, given a function
$f:G\to X$, where $G$ is a finitely generated group and $X$ is a finite set,
such that $f$ is bijective on $G/S$ for a subgroup $S\leq G$, the goal is to
find $S$. Jozsa [24] provided a uniform description of several important
quantum algorithms such as Deutsch-Jozsa [17], Simon [36], and Shor [35]
algorithms in terms of the hidden subgroup problem. Indeed, this problem has
received a lot of attention, and many quantum algorithms were proposed for its
different variants, e.g., [8, 15, 18, 19, 20, 21, 27, 29].

In Simon’s problem, it is assumed that $G=\mathbb{Z}_{2}^{n}$ and $|S|=2$.
There are two directions to generalize Simon’s problem. Alagic et al. [4]
generalized Simon’s problem by assuming $G=K^{n}$, where $K$ is a non-Abelian
group of constant size, and $S$ is either trivial or $|S|=2$. Additionally,
they proposed an efficient quantum algorithm with time complexity
$2^{O(\sqrt{n\log n})}$ to solve this extended version of Simon’s problem.
Brassard and Høyer [10] proposed another extended version of Simon’s problem
by assuming $G=\mathbb{Z}_{2}^{n}$ and $S\leq G$, and solved this problem with
$O(n)$ query complexity. Also, a similar result has been obtained in [32].
Moreover, Brassard and Høyer [10] generalized their results to any finite
general additive group.

In this paper, we consider the generalized Simon’s problem similar to the
problem in [10]. It is assumed that $G=\mathbb{Z}_{p}^{n}$ and $rank(S)=k$,
and the problem is denoted by $\mathsf{GSP}(p,n,k)$ as mentioned before. It is
not difficult to see that $\mathsf{GSP}(p,n,k)$ can be solved exactly by
adjusting the algorithms of [10] slightly (see A), and be solved with bounded
error by a generalized Simon algorithm [23]. All these algorithms need
$O(n-k)$ queries. Meanwhile, by generalizing the method of [28], Wu et al.
[38] found that the lower bound of quantum complexity of $\mathsf{GSP}(p,n,k)$
is $\Omega(n-k)$ with $p=2$. It is easy to obtain the same result for general
$p$.

To clarify the computational power gap between quantum and classical computing
on this problem, there ought to be a characterization of the classical query
complexity of it. However, to our knowledge, almost no related result has been
obtained, except for the work [38]. Compared with this work, our results are
more general, since we consider the case $G=\mathbb{Z}_{p}^{n}$ rather than
$G=\mathbb{Z}_{2}^{n}$. Meanwhile, in terms of classical query complexity,
completely different techniques are used to obtain lower bounds, and we
construct a smarter algorithm to obtain a better upper bound. Furthermore, if
their lower bound proof was correct, then we could generalize their method to
obtain the tight bound of the classical query complexity of
$\mathsf{GSP}(p,n,k)$. However, it is unfortunate that we could not verify its
correctness.

###  1.4 Organization

The remainder of the paper is organized as follows. In Section 2, we review
some notations concerning group theory used in this paper. In Section 3, we
present the lower bounds of deterministic, randomized and nonadaptive
deterministic query complexity of $\mathsf{GSP}(p,n,k)$. In Section 4, an
upper bound is obtained by giving a deterministic algorithm. Finally, a
conclusion is made in Section 5. For completeness, an exact quantum query
algorithm for $\mathsf{GSP}(p,n,k)$ is given in A.

##  2 Preliminaries

In this section, we present some notations used in this paper. Let
$\mathbb{Z}_{p}$ denote the additive group of elements $\\{0,1,...,p-1\\}$
with addition modulo $p$, and $\mathbb{Z}_{p}^{*}$ denote the multiplication
group of elements $\\{1,2,...,p-1\\}$ with multiplication modulo $p$. In the
following, all the groups we mention are $\mathbb{Z}_{p}^{n}$ or its subgroup
without special instructions, where $p$ is a prime. Let
$x,y\in\mathbb{Z}_{p}^{n}$ with $x=(x_{1},x_{2},...,x_{n})$ and
$y=(y_{1},y_{2},...,y_{n})$. For $x,y\in\mathbb{Z}_{p}^{n}$ with
$x=(x_{1},x_{2},...,x_{n})$ and $y=(y_{1},y_{2},...,y_{n})$, we define

$x+y:=((x_{1}+y_{1})\bmod p,(x_{2}+y_{2})\bmod p,...,(x_{n}+y_{n})\bmod p),$
$x-y:=x+(-y).$

For $X,Y\subseteq\mathbb{Z}_{p}^{n},w\in\mathbb{Z}_{p}^{n}$, we define

$X\setminus Y:=\\{x\;|\;x\in X\land x\notin Y\\},$ $X+Y:=\\{x+y\;|\;x\in
X,y\in Y\\},$ $X+w:=\\{x+w\;|\;x\in X\\},$ $X-w:=X+(-w).$

We also use the abbreviated notation $X_{w}$ for $X+w$ and $X\cup w$ for
$X\cup\\{w\\}$. Let $\alpha x$ denote $x+x+\cdots+x$ (the number of $x$ is
$\alpha$). By $\langle X\rangle$, we denote the subgroup generated by $X$,
i.e.,

$\langle X\rangle:=\left\\{\sum_{i=1}^{k}\alpha_{i}x_{i}|x_{i}\in
X,\alpha_{i}\in\mathbb{Z}_{p}\right\\}.$

The set $X$ is called a generating set of $\langle X\rangle$. A set $X$ is
_linearly independent_ if $\langle X\rangle\neq\langle Y\rangle$ for any
proper subset $Y$ of $X$. In other words, a set $X$ is linearly independent if
$X$ is the smallest generating set of $\langle X\rangle$. Notice that the
cardinality $|\langle X\rangle|$ is $p^{|X|}$ if $X$ is linearly independent.

For any group $G$, the basis of $G$ is a maximal linearly independent subset
of $G$. The cardinality of the basis of $G$ is called its _rank_ , denoted by
$rank(G)$. If $H$ is a _subgroup_ of $G$, then we write $H\leq G$; if $H$ is a
_proper subgroup_ , then $H<G$.

######  Definition 1 (Complement Subgroup).

For a group $G$ and its subgroup $H$, a group $\overline{H}_{G}$ is called a
complement subgroup of $H$ in $G$ if
$H+\overline{H}_{G}=G\;\text{and}\;H\cap\overline{H}_{G}=\\{0^{n}\\}.$

In this paper, we abbreviate $\overline{H}_{G}$ as $\overline{H}$ when
$G=\mathbb{Z}_{p}^{n}$.

To obtain our results, we need the following facts to characterize the query
complexity of $\mathsf{GSP}$.

######  Fact 1.

Let $V,W$ be two subgroups of $\mathbb{Z}_{p}^{n}$ such that $V\cap
W=\\{0^{n}\\}$, $X$ be a basis of $V$ and $Y$ be a basis of $W$. Then
$rank(V+W)=rank(V)+rank(W)$ and $X\cup Y$ is a basis of $V+W$.

######  Fact 2.

Let $\\{x_{i}\\}\subseteq\mathbb{Z}_{p}^{n}$. If $\sum_{i}\alpha_{i}x_{i}=0$
implies $\alpha_{i}=0$ for any $i$, then $\\{x_{i}\\}$ is linearly
independent.

######  Fact 3.

Suppose $V,H$ is two subgroups of $\mathbb{Z}_{p}^{n}$ such that $V\cap
H=\\{0^{n}\\}$. For $w\notin V$, we have $\langle V\cup w\rangle\cap
H=\\{0^{n}\\}\Leftrightarrow V_{w}\cap H=\emptyset$.

###### Proof.

Suppose $\langle V\cup w\rangle\cap H=\\{0^{n}\\}$. Since
$V_{w}\subseteq\langle V\cup w\rangle$, we have $V_{w}\cap
H\subseteq\\{0^{n}\\}$. Because $0^{n}\notin V_{w}$, we have $V_{w}\cap
H=\emptyset$. Now suppose $\langle V\cup w\rangle\cap H\neq\\{0^{n}\\}$. Then
there exists a non-zero element $h\in\langle V\cup w\rangle\cap H$. Since
$V\cap H=\\{0^{n}\\}$, we assume that $h=\alpha w+v$, where $\alpha\in
Z_{p}^{*}$ and $v\in V$. Since $h\in H$, we have $\alpha^{-1}s\in H$. Because
$\alpha^{-1}s=w+\alpha^{-1}v\in V_{w}$, we have $\alpha^{-1}h\in V_{w}\cap H$.
Thus, $\langle V\cup w\rangle\cap H\neq\\{0^{n}\\}$ implies $V_{w}\cap
H\neq\emptyset$. ∎

##  3 Lower bound

In this section, we first present a lower bound by proving Theorem 1.

Theorem 1. Any classical (deterministic or randomized) algorithm solving
$\mathsf{GSP}(p,n,k)$ needs to make
$\Omega\left(\max\\{k,\sqrt{p^{n-k}}\\}\right)$ queries.

Without loss of generality, we only need to prove the randomized query
complexity, which consists of Lemma 1 and 2. Before proving Lemma 1, we first
give the results below (Claim 1 and 2). Claim 1 is a folklore conclusion that
can be found in the textbooks such as [37], and we give the proof for
completeness.

######  Claim 1.

Let $T_{1}$ denote the number of distinct subgroups of rank $k$ in
$\mathbb{Z}_{p}^{n}$. Then
$T_{1}=\frac{(p^{n}-1)(p^{n}-p^{1})\cdots(p^{n}-p^{k-1})}{(p^{k}-1)(p^{k}-p^{1})\cdots(p^{k}-p^{k-1})}$.

###### Proof.

We can specify a subgroup of rank $k$ by giving $k$ linearly independent
elements in it. Now we select $k$ linearly independent elements from
$\mathbb{Z}_{p}^{n}$ sequentially. Once we have selected $d$ elements, we can
not select the elements from the subgroup generated by these $d$ elements in
the next step. Thus, we have $p^{n}-p^{d}$ possible ways to pick $(d+1)$-th
elements. So the total number of possible ways to select $k$ linearly
independent elements is $(p^{n}-p^{1})(p^{n}-p^{2})\cdots(p^{n}-p^{k-1})$.

However, it is a double-counting process above. For a certain subgroup, there
are $(p^{k}-p^{1})(p^{k}-p^{2})\cdots(p^{k}-p^{k-1})$ ways to pick the
elements generating it. Thus, the total number of subgroups is

$\frac{(p^{n}-1)(p^{n}-p^{1})\cdots(p^{n}-p^{k-1})}{(p^{k}-1)(p^{k}-p^{1})\cdots(p^{k}-p^{k-1})}.$

∎

######  Claim 2.

Every non-zero element in $\mathbb{Z}_{p}^{n}$ belongs to
$T_{2}=\frac{(p^{n}-p^{1})(p^{n}-p^{2})\cdots(p^{n}-p^{k-1})}{(p^{k}-p^{1})(p^{k}-p^{2})\cdots(p^{k}-p^{k-1})}$
distinct subgroups of rank $k$.

###### Proof.

Now we count the number of subgroups of rank $k$ containing a certain non-zero
element $e$. Similar to the proof of Claim 1, we specify a subgroup of rank
$k$ by giving $k$ linearly independent elements in it. We also select $k$
linearly independent elements from $\mathbb{Z}_{p}^{n}$ sequentially.
Differently, we fix the first element as $e$. So the total number of possible
ways to select the following $k-1$ elements is
$(p^{n}-p^{1})(p^{n}-p^{2})\cdots(p^{n}-p^{k-1})$.

It is also a double-counting process above. For a certain subgroup containing
element $e$, there are $(p^{k}-p^{1})(p^{k}-p^{2})\cdots(p^{k}-p^{k-1})$ ways
to pick the remaining $k-1$ elements to generate it. Thus, the total number of
subgroups containing element $e$ is

$\frac{(p^{n}-p^{1})(p^{n}-p^{2})\cdots(p^{n}-p^{k-1})}{(p^{k}-p^{1})(p^{k}-p^{2})\cdots(p^{k}-p^{k-1})}.$

∎

In the following proof, let $Q$ be the set of queried elements in an algorithm
to solve $\mathsf{GSP}(p,n,k)$, and $T_{Q}=\\{q_{1}-q_{2}\ |\ q_{1},q_{2}\in
Q\\}$. It is easy to see $|T_{Q}|\leq|Q|^{2}$ and $0^{n}\in T_{Q}$.

######  Lemma 1.

Any classical randomized algorithm solving $\mathsf{GSP}(p,n,k)$ needs
$\Omega\left(\sqrt{p^{n-k}}\right)$ queries.

###### Proof.

In terms of the target subgroup $S$ of $\mathsf{GSP}(p,n,k)$, we define a
characteristic function $f_{S}:\mathbb{Z}_{p}^{n}\rightarrow\\{0,1\\}$
satisfying that $f_{S}(x)=1$ if and only if $x\in S$. Thus, for any
$x,y\in\mathbb{Z}_{p}^{n}$, if $f(x)=f(y)$, then $f_{S}(x-y)=1$; otherwise,
$f_{S}(x-y)=0$. In this way, we can obtain one function value of $f_{S}$ by a
pair of queries to $f$. By the truth table of $f_{S}$, we can view $f_{S}$ as
a ${p^{n}}$-bit Boolean string equivalently. As a result, querying a function
value of $f_{S}$ is equivalent to querying a bit of the corresponding Boolean
string of $f_{S}$. Furthermore, we define a promise function
$\mathscr{P}:\mathscr{F}\rightarrow\mathscr{S}$, where
$\mathscr{F}\subset{\\{0,1\\}}^{p^{n}}$ represents the set of all
characteristic functions above, $\mathscr{S}$ is the set of all possible
target subgroups in $\mathsf{GSP}(p,n,k)$, and $\mathscr{P}(f_{S})=S$. Thus,
$\mathsf{GSP}(p,n,k)$ can be reduced to the problem of computing
$\mathscr{P}(f_{S})$ by querying the bits of $f_{S}$. Denote the randomized
query complexity of $\mathscr{P}$ by $Q(\mathscr{P})$.

Next, we apply the relational adversary method [1, 7] to obtain a lower bound
of $Q(\mathscr{P})$. Let $R:\mathscr{F}\times\mathscr{F}\rightarrow R_{\geq
0}$ be a real-valued function such
$R(f_{S_{1}},f_{S_{2}})=R(f_{S_{1}},f_{S_{2}})$ for all
$f_{S_{1}},f_{S_{2}}\in\mathscr{F}$ and $R(f_{S_{1}},f_{S_{2}})=0$ whenever
$S_{1}=S_{2}$. Then for $f_{S_{1}}\in\mathscr{F}$ and
$x\in\mathbb{Z}_{p}^{n}$, let

$\theta(f_{S_{1}},x)=\frac{\sum_{f_{S_{2}}\in\mathscr{F}}R(f_{S_{1}},f_{S_{2}})}{\sum_{f_{S_{2}}\in\mathscr{F}:f_{S_{1}}(x)\neq
f_{S_{2}}(x)}R(f_{S_{1}},f_{S_{2}})},$

where $\theta(f_{S_{1}},x)$ is undefined if the denominator is $0$. Denote

$v_{min}=\min\limits_{f_{S_{1}},f_{S_{2}}\in\mathscr{F},x\in\mathbb{Z}_{p}^{n}:\\\
R(f_{S_{1}},f_{S_{2}})>0,f_{S_{1}}(x)\neq
f_{S_{2}}(x)}\max\\{\theta(f_{S_{1}},x),\theta(f_{S_{2}},x)\\}.$

Then $v_{min}$ is a lower bound of $Q(\mathscr{P})$.

Now we assign for $R$. For any distinct characteristic functions
$f_{S_{1}},f_{S_{2}}\in\mathscr{S}$, let $R(f_{S_{1}},f_{S_{2}})=1$. Let
$T_{1},T_{2}$ be the number in Claim 1 and 2, respectively. Then for any
$f_{S_{1}}$, $\sum_{f_{S_{2}}\in\mathscr{F}}R(f_{S_{1}},f_{S_{2}})=T_{1}-1$.
If $f_{S_{1}}(x)=0$,

$\sum_{f_{S_{1}}\in\mathscr{F}:f_{S_{1}}(x)\neq
f_{S_{2}}(x)}R(f_{S_{1}},f_{S_{2}})=T_{2}-1,$

and

$\theta(f_{S_{1}},x)=\frac{T_{1}-1}{T_{2}-1}.$

If $f_{S_{1}}(x)=1$,

$\sum_{f_{S_{1}}\in\mathscr{F}:f_{S_{1}}(x)\neq
f_{S_{2}}(x)}R(f_{S_{1}},f_{S_{2}})=T_{1}-T_{2}-1,$

and

$\theta(f_{S_{1}},x)=\frac{T_{1}-1}{T_{1}-T_{2}-1}.$

Next, we compute $v_{min}$. Because $f_{S_{1}}(x)\neq f_{S_{2}}(x)$, we have
$f_{S_{1}}(x)=0,f_{S_{2}}(x)=1$ or $f_{S_{2}}(x)=0,f_{S_{1}}(x)=1$. Since
$\frac{T_{1}-1}{T_{2}-1}>\frac{T_{1}-1}{T_{1}-T_{2}-1}$,
$\max\\{\theta(f_{S_{1}},x),\theta(f_{S_{2}},x)\\}=\frac{T_{1}-1}{T_{2}-1}>p^{n-k}-1$.
So $v_{min}>p^{n-k}-1$.

Suppose the number of queries to $f$ is $Q(f)$. Since a pair of queries to $f$
is equivalent to one query to $f_{S}$, we have $Q(f)^{2}\geq Q(\mathscr{P})$,
which means that
$Q(f)=\Omega(\sqrt{Q(\mathscr{P})})=\Omega(\sqrt{v_{min}})=\Omega(\sqrt{p^{n-k}})$.

∎

######  Lemma 2.

Any classical randomized algorithm solving $\mathsf{GSP}(p,n,k)$ needs
$\Omega\left(k\right)$ queries.

###### Proof.

Suppose an algorithm makes no more than $k/2$ queries. Let $S_{1}=\langle
T_{Q}\rangle,S_{2}=\langle T_{Q}\cap S\rangle,x=rank(S_{2}),y=rank(S_{1})$. It
is easy to see $y\leq k/2$. Similar $Q$ contains no more than $k/2$ queries,
$T_{Q}$ contains at most $y$ linear independent elements. Thus, $x\leq y\leq
k/2$. Now we count the number of possible target subgroups until now. We have
found a subgroup of rank $x$ of $S$. Thus, we only need to find other $k-x$
linear independent elements in $S$ in turn. In the first step, we try to find
first element $e$. There are at least $p^{n}-p^{y}$ candidate elements, i.e.,
those elements not in $S_{1}$. In the next step, there are at least
$p^{n}-p^{y+1}$ candidate elements, i.e., those elements not in $\langle
S_{1}\cup e\rangle$. In the end, we have
$(p^{n}-p^{y})(p^{n}-p^{y+1})\cdots(p^{n}-p^{y+(k-x+1)})$ ways to select these
$k-x$ elements. However, it is a double-counting process above. For a certain
subgroup of rank $k$, if we have known a subgroup of rank $x$ of it, there are
$(p^{k}-p^{x})(p^{k}-p^{x+1})\cdots(p^{k}-p^{k-1})$ ways to pick other $k-x$
linear independent elements. Thus, the total number of subgroups is no less
than

$\frac{(p^{n}-p^{y})(p^{n}-p^{y+1})\cdots(p^{n}-p^{y+(k-x+1)})}{(p^{k}-p^{x})(p^{k}-p^{x+1})\cdots(p^{k}-p^{k-1})}>(\frac{p^{n}-p^{y+k-x-1}}{p^{k}-p^{k-1}})^{k-x}>p^{(n-k)k/2},$

which means the success probability of the algorithm is less than
$\frac{1}{p^{(n-k)k/2}}$. Thus, $k/2$ queries is not enough to find the target
subgroup with a high probabilitiy.

∎

In the following, we give Claim 3 first. Then we present a lower bound for the
nonadaptive deterministic query complexity by proving Theorem 2.

######  Claim 3.

For any set $D\subseteq\mathbb{Z}_{p}^{n}$ such that $\\{0^{n}\\}\notin D$ and
$|D|<\frac{d(p^{n}-1)}{(p^{k}-1)}(1\leq d\leq k\leq n)$, there exists a
subgroup $S_{1}$ of rank $k$ of $\mathbb{Z}_{p}^{n}$ such that $|S_{1}\cap
D|<d$.

###### Proof.

We prove the result by contradiction. Suppose for any group $S_{1}$ of rank
$k$, there exist at least $d$ elements in $S_{1}\cap D$. Since
$\mathbb{Z}_{p}^{n}$ has $T_{1}$ distinct subgroups of rank $k$ by Claim 1,
the total number of elements is $T_{1}\cdot d$. However, some elements may be
counted repeatedly. Since every non-zero element in $\mathbb{Z}_{p}^{n}$
belongs to $T_{2}$ distinct subgroups of rank $k$ by Claim 2, we have
$T_{2}\cdot|D|\geq{T_{1}}\cdot d$, which means
$|D|\geq\frac{dT_{1}}{T_{2}}=\frac{d(p^{n}-1)}{(p^{k}-1)}$. It makes a
contradiction. Thus, there exists a subgroup $S_{1}$ of rank $k$ such that
$|S_{1}\cap D|<d$. ∎

Theorem 2. Any nonadaptive classical deterministic algorithm solving
$\mathsf{GSP}(p,n,k)$ needs $\Omega\left(\max\\{k,\sqrt{k\cdot
p^{n-k}}\\}\right)$ queries.

###### Proof.

It is easy to see any nonadaptive classical deterministic algorithm solving
$\mathsf{GSP}(p,n,k)$ needs $\Omega(k)$ queries by Lemma 2. Now we prove the
other part. Suppose there exists an nonadaptive algorithm $\mathcal{A}$ which
makes less than $\sqrt{\frac{k(p^{n}-1)}{(p^{k+1}-1)}}$ queries to solve
$\mathsf{GSP}(p,n,k)$ correctly. Then
$|Q|<\sqrt{\frac{k(p^{n}-1)}{(p^{k+1}-1)}}$, so we have
$|T_{Q}|<\frac{k(p^{n}-1)}{(p^{k+1}-1)}$. By Claim 3, there exists a subgroup
$\hat{S}$ of rank $k+1$ such that $|\hat{S}\cap T_{Q}|<k$. Let
$\hat{S^{\prime}}=\langle S_{1}\cap T_{Q}\rangle$. Then $rank(\hat{S})<k$. Let
$S_{1},S_{2}$ be two different subgroups of $k$ of $\mathbb{Z}_{p}^{n}$ such
that $\hat{S^{\prime}}<S_{1},S_{2}<\hat{S}$.

Now we pick a function $f_{1}$ satisfying that $f_{1}(x)=f_{1}(y)$ iff $x-y\in
S_{1}$ as the input of Algorithm $\mathcal{A}$. Since Algorithm $\mathcal{A}$
solves the problem correctly, its output is $S_{1}$. Next we construct a
function $f_{2}$ as the input of Algorithm $\mathcal{A}$, where $f_{2}$
satisfies that (i) $\forall x\in Q,f_{2}(x)=f_{1}(x)$, which means $\forall
x,y\in Q,f_{2}(x)=f_{2}(y)$ iff $x-y\in\hat{S^{\prime}}\cap T_{Q}$; (ii)
$f_{2}(x)=f_{2}(y)$ iff $x-y\in S_{2}$. Since $\hat{S}\cap T_{Q}\subseteq
S_{2}$, conditions (i) and (ii) are simultaneously satisfiable. Condition (i)
implies the output of Algorithm $\mathcal{A}$ is still $S_{1}$, which is a
wrong answer. Thus, Algorithm $\mathcal{A}$ does not solve the problem
correctly for any input, which makes a contradiction. Therefore, any classical
deterministic algorithm solving $\mathsf{GSP}(p,n,k)$ needs at least
$\sqrt{\frac{k(p^{n}-1)}{(p^{k+1}-1)}}$ queries, i.e., we need to make
$\Omega\left(\sqrt{k\cdot p^{n-k}}\right)$ queries. ∎

##  4 Algorithm and upper bound

In this section, we propose an algorithm to solve $\mathsf{GSP}(p,n,k)$ and
analyze its query complexity, which establishes the upper bound in Theorem 3.

Theorem 3. There exists a classical deterministic algorithm to solve
$\mathsf{GSP}(p,n,k)$ using $O\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$
queries.

For our problem, we say $x$ and $y$ collide iff $f(x)=f(y)$, which means
$x-y\in S$. Thus, $x$ and $y$ collide if $x$ and $y$ belong to the same coset
of $S$. So the probability of the collision in each pair of elements is
$\frac{1}{p^{n-k}}$. Once we find $k$ linearly independent elements in $S$, we
will determine what $S$ is. Thus, there exists a randomized algorithm in
intuition as follows. By making $O(\sqrt{k\cdot p^{n-k}})$ queries randomly
and uniformly, the expected number of collisions is
$O(kp^{n-k}\frac{1}{p^{n-k}})=O(k)$, from which it is likely to find a
generating set of $S$ with a high probability.

This randomized algorithm gives an intuitive guess on the upper bound of query
complexity. However, it seems hard to derandomize it directly. Therefore, we
give an ingenious construction of the query set to ensure that a generating
set of $S$ can be found in Algorithm 1, which is based on group theory and a
divide-and-conquer subroutine (i.e., Algorithm 2). The main idea of Algorithm
1 is as follows. First, we try to obtain two subgroups $A,B$ such that the
elements between $A$ and $B$ do not collide. We may find some collisions in
this process. Second, we try to find some other collisions between $B$ and
cosets of $A$. By the above collisions, we make sure that a generating set of
$S$ will be found.

Algorithm 1 Find $S$

0: $d\in\\{0,...,n-k\\}$;

0: subgroup $S$;

1: $(A,S_{1})\leftarrow findGroup(\\{0^{n}\\},\\{0^{n}\\},d)$;

2: $(B,S_{2})\leftarrow findGroup(A,S_{1},n-k-d)$;

3: $V\leftarrow A+B$, $W\leftarrow\overline{V+S_{2}}$, find a basis
$\\{w_{i}\\}$ of $W$;

4: for $i=1\ to\ rank(W)$ do

5: Query all the elements in $A_{w_{i}}$, and then we can find a pair of
$(a_{i},b_{i})$ s.t. $a_{i}\in A_{w_{i}},b_{i}\in B$ and $f(a_{i})=f(b_{i})$;

6: $s_{w_{i}}\leftarrow a_{i}-b_{i}$;

7: end for

8: return $\langle S_{2}\cup\\{s_{w_{i}}\\}\rangle$;

###  4.1 Correctness analysis

Whatever the value of $d$ is, Algorithm 1 will find $S$, but there exists an
optimal value such that the number of queries used is minimum. The details
will be discussed later. Now suppose Algorithm 2 is correct (which will be
proved later), and we show the correctness of Algorithm 1. Let
$rank(S_{i})=k_{i}$ for $i=1,2$. In Step 1, we find a subgroup $A$ such that
$A\cap S=\\{0^{n}\\}$ and $rank(A)=d$ by calling Algorithm 2. At the same
time, we find a subgroup $S_{1}\leq S$. In Step 2, we find a subgroup $B$ such
that $A\cap B=\\{0^{n}\\}$, $(A+B)\cap S=\\{0^{n}\\}$, and $rank(B)=n-k-d$ by
calling Algorithm 2 again. Simultaneously, we find a subgroup $S_{2}$ such
that $S_{1}\leq S_{2}\leq S$. In Step 3, we obtain $W$, a complement of
$V+S_{2}$ in $\mathbb{Z}_{p}^{n}$. Let $\\{w_{i}\\}$ be a basis of $W$. In
Step 4-7, we query all the elements in $A_{w_{i}}$ to obtain $s_{w_{i}}$ for
any $i$. Next we elaborate why we can obtain the desired $\\{s_{w_{i}}\\}$.
Suppose $f(a)\neq f(b)$ for any $a\in A_{w_{i}},b\in B$ in Step 5. Then we
have $a-b\notin S$ for any $a\in A,b\in B_{w_{i}}$. Since

$V_{w_{i}}=V+w_{i}=A+B+w_{i}=A-B+w_{i}=A+w_{i}-B=\\{a-b\ |\ a\in
A_{w_{i}},b\in B\\},$

we have $V_{w_{i}}\cap S=\emptyset$. However, Lemma 3 implies that
$V_{w_{i}}\cap S\neq\emptyset$, which makes a contradiction. Thus, there
exists $a_{i}\in A_{w_{i}},b_{i}\in B$ such that $f(a_{i})=f(b_{i})$. Then
$s_{w_{i}}=a_{i}-b_{i}$ is a non-zero element in $V_{w_{i}}\cap S$. Finally,
Lemma 4 implies $S_{2}\cup\\{s_{w_{i}}\\}$ is a generating set of $S$. Thus,
we find $S$.

######  Lemma 3.

Suppose $V$ is a subgroup of $\mathbb{Z}_{p}^{n}$ such that $V\cap
S=\\{0^{n}\\}$ and $rank(V)=n-k$. For $w\notin V$, we have $V_{w}\cap
S\neq\emptyset$.

###### Proof.

For $w\notin V$, $\langle V\cup w\rangle$ is a group of rank $n-k+1$. First we
prove $\langle V\cup w\rangle\cap S\neq\\{0^{n}\\}$ by contradiction. Suppose
$\langle V\cup w\rangle\cap S=\\{0^{n}\\}$. Then we have $rank(\langle V\cup
w\cup S\rangle)=n-k+1+k=n+1$. Since $\langle V\cup w\cup S\rangle$ is a
subgroup of $\mathbb{Z}_{p}^{n}$, we have $rank(\langle V\cup w\cup
S\rangle)\leq n$, which makes a contradiction. Now by combining $\langle V\cup
w\rangle\cap S\neq\\{0^{n}\\}$, $\langle V\cup w\rangle=V\cup V_{w}$ and
$V\cap S=\\{0^{n}\\}$, we have $V_{w}\cap S\neq\emptyset$. ∎

######  Lemma 4.

In Algorithm 1, $S_{2}\cup\\{s_{w_{i}}\\}$ is a generating set of $S$.

###### Proof.

Let $\\{v_{i}\\}$ be a basis of $V$, $\\{s_{i}\\}$ be a basis of $S_{2}$.
Since $V\cap S_{2}=\\{0^{n}\\}$, we have
$rank(V+S_{2})=rank(V)+rank(S_{2})=n-k+k_{2}$. Since $W$ is a complement
subgroup of $V+S_{2}$, we have $rank(W)=n-(n-k+k_{2})=k-k_{2}$ and
$\\{u_{i}\\}=\\{v_{i}\\}\cup\\{s_{i}\\}\cup\\{w_{i}\\}$ constructs a basis of
$\mathbb{Z}_{p}^{n}$ by Fact 1. Since $s_{w_{i}}\in V_{w_{i}}$, we have

$s_{w_{i}}=\sum_{j=1}^{n-k}\alpha_{ij}v_{j}+w_{i}.$

Suppose we have

$\sum_{i=1}^{k_{2}}\beta_{i}s_{i}+\sum_{i=1}^{k-k_{2}}\gamma_{i}s_{w_{i}}=0.$

That is,

$\sum_{i=1}^{k_{2}}\beta_{i}s_{i}+\sum_{i=1}^{k-k_{2}}\sum_{j=1}^{n-k}\gamma_{i}\alpha_{ij}v_{j}+\sum_{i=1}^{k-k_{2}}\gamma_{i}w_{i}=0,$

which implies $\beta_{i}=0$ for any $1\leq i\leq k_{2}$, and $\gamma_{i}=0$
for any $1\leq i\leq k-k_{2}$. Thus, $\\{s_{w_{i}}\\}\cup\\{s_{i}\\}$ is
linearly independent by Fact 2. Since $rank(S)=k$, the cardinality of a
linearly independent subset of $G$ is at most $k$. Thus,
$|\\{s_{w_{i}}\\}\cup\\{s_{i}\\}|=k$ implies $\\{s_{w_{i}}\\}\cup\\{s_{i}\\}$
consists of a basis of $S$. Since $\\{s_{i}\\}\subseteq S_{2}$,
$S_{2}\cup\\{s_{w_{i}}\\}$ constructs a generating set of $S$. ∎

###  4.2 Complexity analysis

Now we analyze the query complexity of Algorithm 1. Lemma 5 implies that the
number of queries in Step 1 is $p^{d}-1+k_{1}$, and the number of queries in
Step 2 is at most $p^{n-k-d}-1+(k_{2}-k_{1})\cdot p^{d}-1$. In addition, the
number of queries in Step 4-7 is $(k-k_{2})\cdot p^{d}$. Let $TQ$ denote the
total number of queries. Then

$\displaystyle TQ$ $\displaystyle\leq
p^{d}-1+k_{1}+p^{n-k-d}-1+(k_{2}-k_{1})\cdot(p^{d}-p^{d-1})+(k-k_{2})\cdot
p^{d}$ $\displaystyle\leq p^{n-k-d}+(k+1)\cdot p^{d}.$

If $n\geq k+\log_{p}k$, let $d=(n-k-\log_{p}k)/2$. Then we get

$TQ\leq\sqrt{k\cdot p^{n-k}}+\frac{k+1}{\sqrt{k}}\sqrt{p^{n-k}}=O(\sqrt{k\cdot
p^{n-k}}).$

Otherwise, let $d=0$, we have

$TQ\leq p^{n-k}+k+1<2k+1=O(k).$

That is, the number of queries of our algorithm is

$TQ=\left\\{\begin{array}[]{lrr}O(\sqrt{k\cdot p^{n-k}})&n\geq k+\log_{p}k&\\\
O(k)&n<k+\log_{p}k&\end{array}\right..$

It is equivalent to

$TQ=O(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}),$

which meets the upper bound in Theorem 3.

###  4.3 Critical subroutine

Next, we only need to show the correctness of Algorithm 2 and analyze its
query complexity. In Algorithm 2, given a subgroup $S_{1}\leq S$, a subgroup
$A$ such that $A\cap S=\\{0^{n}\\}$ and an integer $d$, we wish to find a
subgroup $B$ of rank $d$ such that $A\cap B=\\{0^{n}\\}$ and $(A+B)\cap
S=\\{0^{n}\\}$. Also, we query all the elements in $B$. Meanwhile, we find a
subgroup $S_{2}$ such that $S_{1}\leq S_{2}\leq S$, which is an extra bonus.
We use the idea of recursion. First, we find a subgroup $B^{\prime}$ of rank
$d-1$ such that $A\cap B=\\{0^{n}\\},(A+B^{\prime})\cap S=\\{0^{n}\\}$ and a
subgroup $S^{\prime}\leq S$. We also query all the elements in $B^{\prime}$.
Next, we query an element
$u\in\mathbb{Z}_{p}^{n}\setminus(S^{\prime}+A+B^{\prime})$. If there exists an
element $b\in B^{\prime}$ such that $f(b)=f(u)$, then we have $b-u\in S$.
Thus, we expand $S^{\prime}$, and query an element
$u\in\mathbb{Z}_{p}^{n}\setminus(S^{\prime}+A+B^{\prime})$ again. We repeat
this procedure until for any $b\in B^{\prime}$ we have $f(b)\neq f(u)$. Then
we query all the elements in $\langle B^{\prime}\cup
u\rangle\setminus(B^{\prime}\cup u)$, i.e., the elements not queried in
$\langle B^{\prime}\cup u\rangle$. Similarly, if there exists $a\in A$,
$b\in\langle B^{\prime}\cup u\rangle\setminus\\{0^{n}\\}$ such that
$f(a)=f(b)$, then we have $b-u\in S$. So we expand $S^{\prime}$ and go back to
Step 6. Only if for any $a\in A,b\in\langle B^{\prime}\cup
u\rangle\setminus\\{0^{n}\\}$ we have $f(a)\neq f(b)$, we exit the outer loop.
Then we obtain $B=\langle B^{\prime}\cup u\rangle$ and return
$(B,S^{\prime})$. At this point, all the elements in $B$ have been queried.

Algorithm 2 findGroup

0: $A,S_{1},d$ s.t. $0\leq d\leq n-k,S_{1}\leq S,A\cap S=\\{0^{n}\\}$;

0: $B,S_{2}$ s.t. $rand(B)=d,A\cap B=\\{0^{n}\\},(A+B)\cap S=\\{0^{n}\\}$;

1: if d = 0 then

2: return $(\\{0^{n}\\},S_{1})$;

3: end if

4: $(B^{\prime},S^{\prime})\leftarrow findGroup(A,S_{1},d-1);$

5: repeat

6: repeat

7: Query a non-zero element $u$ s.t. $u\in\mathbb{Z}_{p}^{n}$ and
$u\notin(S^{\prime}+A+B^{\prime})$;

8: if $\exists b\in B^{\prime}$ s.t. $f(b)=f(u)$ then

9: $S^{\prime}\leftarrow\langle S^{\prime}\cup(b-u)\rangle$;

10: end if

11: until $\forall b\in B^{\prime}$ s.t. $f(b)\neq f(u)$

12: Query all the elements in $\langle B^{\prime}\cup
u\rangle\setminus(B^{\prime}\cup u)$;

13: if $\exists a\in A,b\in\langle B^{\prime}\cup
u\rangle\setminus\\{0^{n}\\}$ s.t. $f(a)=f(b)$ then

14: $S^{\prime}\leftarrow\langle S^{\prime}\cup(a-b)\rangle$;

15: end if

16: until $\forall a\in A,b\in\langle B^{\prime}\cup
u\rangle\setminus\\{0^{n}\\}$ s.t. $f(a)\neq f(b)$

17: $B\leftarrow\langle B^{\prime}\cup u\rangle$;

18: return $(B,S^{\prime})$;

We show that the algorithm obtains the desired output below. Since
$u\notin(A+B^{\prime})$, we have $A\cap B^{\prime}_{u}=\emptyset$, which
implies $A\cap\langle B^{\prime}\cup u\rangle=\\{0^{n}\\}$, i.e., $A\cap
B=\\{0^{n}\\}$ by Fact 3. Since $f(a)\neq f(b)$ implies $a-b\notin S$ for any
$a\in A,b\in B\setminus\\{0^{n}\\}$, we have $((A+B)\setminus\\{0^{n}\\})\cap
S=\emptyset$. In addition, because $0^{n}\in S$, we have $(A+B)\cap
S=\emptyset$. Moreover, while we expand $S^{\prime}$, $S^{\prime}$ is always a
subgroup of $S$. Thus, we obtain desired $B$ and $S^{\prime}$.

Now, we analyze the query complexity of Algorithm 2 by proving Lemma 5.

######  Lemma 5.

In Algorithm 2, suppose $rank(S_{i})=k_{i}$ for $i=1,2$. If $A=\\{0^{n}\\}$,
the number of queries is $p^{d}-1+(k_{2}-k_{1})\cdot(p^{d}-p^{d-1})$. If
$A\neq\\{0^{n}\\}$, the number of queries is at most $p^{d}-1+(k_{2}-k_{1})$.

###### Proof.

We consider the following two cases: $A\neq\\{0^{n}\\}$ and $A=\\{0^{n}\\}$.

Case 1: $A\neq\\{0^{n}\\}$. In Step 7 and 12, we make $p^{d}-p^{d-1}$ queries
to query all the element in $\langle B^{\prime}\cup u\rangle\setminus
B^{\prime}$. Suppose we never execute Step 9 and 14. When we recursively call
the algorithm itself, the number of queries is
$(p^{d}-p^{d-1})+(p^{d-1}-p^{d-2})+\cdots+(p^{1}-p^{0})=p^{d}-1$ in total.
However, once we execute Step 9, we will go back to the inner loop and make
one extra query. Once we execute Step 14, we will go back to the outer loop
and make at most $p^{d}-p^{d-1}$ extra queries. Moreover, every time we
execute Step 9 or 14, the rank of $S^{\prime}$ adds one. Since we input
$S_{1}$ and obtain $S_{2}$, the total number we execute Step 9 and 14 is
$k_{2}-k_{1}$. Thus, we need at most extra $(k_{2}-k_{1})\cdot(p^{d}-p^{d-1})$
queries in order to expand $S_{1}$ to $S_{2}$. Finally, the total number of
queries is at most $p^{d}-1+(k_{2}-k_{1})\cdot(p^{d}-p^{d-1})$.

Case 2: $A=\\{0^{n}\\}$. Different from Case 1, we never execute Step 14 in
this case. Suppose we go into Step 13. At this time, we have $f(b)\neq f(u)$
for any $b\in B^{\prime}$. Since $f(b)\neq f(u)$ implies $b+u\notin S$, we
have $B^{\prime}_{u}\cap S=\emptyset$, which implies $\langle B^{\prime}\cup
u\rangle\cap S=\\{0^{n}\\}$. Hence, we have $f(a)\neq f(b)$ for any
$a\in\\{0^{n}\\},b\in\langle B^{\prime}\cup u\rangle\setminus\\{0^{n}\\}$.
Therefore, the if-statement is always judged to be false, and then we jump out
of Step 14. On the other hand, similar to Case 1, if we never execute Step 9,
then the number of queries is $p^{d}-1$. Once we execute Step 9, we will go
back to the inner loop and make one extra query. Thus, we need extra
$k_{2}-k_{1}$ queries in order to expand $S_{1}$ to $S_{2}$. Finally, the
total number of queries is $p^{d}-1+(k_{2}-k_{1})$.

∎

##  5 Conclusion

In this paper, we obtain an almost full characterization of the classical
query complexity for the generalized Simon’s problem $\mathsf{GSP}(p,n,k)$. We
prove that any classical (deterministic or randomized) algorithm has to make
$\Omega\left(\max\\{k,\sqrt{p^{n-k}}\\}\right)$ queries. Also, we prove that
any classical nonadaptive deterministic algorithm has to make
$\Omega\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$ queries. Moreover, we
devise an deterministic algorithm for this problem with query complexity of
$O\left(\max\\{k,\sqrt{k\cdot p^{n-k}}\\}\right)$. These results clarify the
computational power gap between quantum and classical computing on this
problem. Furthermore, two open problems remain:

  * 1.

It still has a gap between the lower bound and the upper bound for classical
query complexity of the generalized Simon’s problem.

  * 2.

If we generalize the domain of $f$ from $\mathbb{Z}_{p}^{n}$ to an arbitrary
finite Abelian group
$\mathbb{Z}_{m_{1}}\oplus\mathbb{Z}_{m_{2}}\oplus\cdots\oplus\mathbb{Z}_{m_{n}}$,
where $\mathbb{Z}_{m_{i}}$ denotes the additive cyclic group of order $m_{i}$,
what is the optimal classical query complexity in this case?

## References

  * [1] Scott Aaronson.  Lower bounds for local search by quantum arguments.  SIAM Journal on Computing, 35(4):804–824, 2006.
  * [2] Scott Aaronson and Andris Ambainis.  Forrelation:a problem that optimally separates quantum from classical computing.  SIAM Journal on Computing, 47(3):982–1038, 2018.  doi:10.1137/15M1050902.
  * [3] Scott Aaronson, Shalev Ben-David, and Robin Kothari.  Separations in query complexity using cheat sheets.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pages 863–876, 2016.  doi:10.1145/2897518.2897644.
  * [4] Gorjan Alagic, Cristopher Moore, and Alexander Russell.  Quantum algorithms for Simon’s problem over general groups.  In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 1217–1224, 2007.  URL: http://dl.acm.org/citation.cfm?id=1283383.1283514.
  * [5] Andris Ambainis.  Superlinear advantage for exact quantum algorithms.  SIAM Journal on Computing, 45(2):617–631, 2016.  doi:10.1137/130939043.
  * [6] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs.  Separations in query complexity based on pointer functions.  Journal of the ACM (JACM), 64(5):32:1–32:24, 2017.  doi:10.1145/3106234.
  * [7] Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs.  All classical adversary methods are equivalent for total functions.  In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, pages 8:1–8:14, 2018.
  * [8] Dave Bacon, Andrew M. Childs, and Wim van Dam.  From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.  In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), pages 469–478, 2005.  doi:10.1109/SFCS.2005.38.
  * [9] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM (JACM), 48(4):778–797, 2001.  doi:10.1145/502090.502097.
  * [10] Gilles Brassard and Peter Høyer.  An exact quantum polynomial-time algorithm for Simon’s problem.  In Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems (ISTCS 1997), pages 12–23, 1997.  doi:10.1109/ISTCS.1997.595153.
  * [11] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [12] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig.  Quantum property testing.  SIAM Journal on Computing, 37(5):1387–1400, 2008.  doi:10.1137/S0097539704442416.
  * [13] Mark Bun, Robin Kothari, and Justin Thaler.  The polynomial method strikes back: tight quantum query bounds via dual polynomials.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 297–310, 2018.  doi:10.1145/3188745.3188784.
  * [14] Guangya Cai and Daowen Qiu.  Optimal separation in exact query complexities for Simon’s problem.  Journal of Computer and System Sciences, 97:83–93, 2018.  doi:10.1016/j.jcss.2018.05.001.
  * [15] Andrew M. Childs and Wim van Dam.  Quantum algorithm for a generalized hidden shift problem.  In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 1225–1232, 2007.  doi:10.1137/S009753970139450X.
  * [16] Ronald de Wolf.  Quantum Computing: Lecture Notes.  arXiv preprint arXiv:1907.09415, 2019.
  * [17] David Deutsch and Richard Jozsa.  Rapid solution of problems by quantum computation.  Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992.
  * [18] Mark Ettinger, Peter Høyer, and Emanuel Knill.  The quantum query complexity of the hidden subgroup problem is polynomial.  Information Processing Letters, 91(1):43–48, 2004.  doi:10.1016/j.ipl.2004.01.024.
  * [19] Demerson Nunes Goncalves, Tharso D. Fernandes, Carlos Cosme, and Martins Magno.  An efficient quantum algorithm for the hidden subgroup problem over some non-abelian groups.  Trends in Applied and Computational Mathematics, 18(2):215–223, 2017.  doi:10.5540/03.2015.003.02.0045.
  * [20] Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, and Umesh V. Vazirani.  Quantum mechanical algorithms for the nonabelian hidden subgroup problem.  Combinatorica, 24(1):137–154, 2004.  doi:10.1007/s00493-004-0009-8.
  * [21] Sean Hallgren, Alexander Russell, and Amnon Tashma.  The hidden subgroup problem and quantum computation using group representations.  SIAM Journal on Computing, 32(4):916–934, 2003.
  * [22] Buhrman Harry and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  doi:10.1016/S0304-3975(01)00144-X.
  * [23] Mika Hirvensalo.  Quantum Computing.  Springer-Verlag, 2001.
  * [24] Richard Jozsa.  Quantum algorithms and the fourier transform.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):323–337, 1998.
  * [25] Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia.  Breaking symmetric cryptosystems using quantum period finding.  In Proceedings of the 36th Annual International Cryptology Conference (CRYPTO 2016), pages 207–237, 2016.  doi:10.1007/978-3-662-53008-5_8.
  * [26] Phillip Kaye, Raymond Laflamme, and Michele Mosca.  An Introduction to Quantum Computing.  Oxford University Press, 2006.
  * [27] Julia Kempe and Aner Shalev.  The hidden subgroup problem and permutation group theory.  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 1118–1125, 2005.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070592.
  * [28] Pascal Koiran, Vincent Nesme, and Natacha Portier.  A quantum lower bound for the query complexity of Simon’s problem.  In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP 2005), pages 1287–1298, 2005.  doi:10.1007/11523468_104.
  * [29] Greg Kuperberg.  A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.  SIAM Journal on Computing, 35(1):170–188, 2005.  doi:10.1137/s0097539703436345.
  * [30] Hidenori Kuwakado and Masakatu Morii.  Quantum distinguisher between the 3-round feistel cipher and the random permutation.  In Proceedings of the IEEE International Symposium on Information Theory (ISIT 2010), pages 2682–2685, 2010.  doi:10.1109/ISIT.2010.5513654.
  * [31] Hidenori Kuwakado and Masakatu Morii.  Security on the quantum-type even-mansour cipher.  In Proceedings of the International Symposium on Information Theory and its Applications (ISITA 2012), pages 312–316, 2012.  URL: http://ieeexplore.ieee.org/document/6400943/.
  * [32] Takashi Mihara and Shao Chin Sung.  Deterministic polynomial-time quantum algorithms for Simon’s problem.  Computational Complexity, 12(3-4):162–175, 2003.  doi:10.1007/s00037-003-0181-z.
  * [33] Martin Roetteler and Rainer Steinwandt.  A note on quantum related-key attacks.  Information Processing Letters, 115(1):40–44, 2015.  doi:10.1016/j.ipl.2014.08.009.
  * [34] Thomas Santoli and Christian Schaffner.  Using Simon’s algorithm to attack symmetric-key cryptographic primitives.  Quantum Information & Computation, 17(1&2):65–78, 2017.  URL: http://www.rintonpress.com/xxqic17/qic-17-12/0065-0078.pdf.
  * [35] Peter W. Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pages 124–134, 1994.
  * [36] Daniel R. Simon.  On the power of quantum computation.  In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pages 116–123, 1994.  doi:10.1109/SFCS.1994.365701.
  * [37] Richard P. Stanley.  Enumerative Combinatorics, Volume 1.  Cambridge University Press, 2000.
  * [38] Zhenggang Wu, Daowen Qiu, Guangya Cai, Yinuo Lin, and Yikang Zhu.  Quantum and classical query complexities for generalized Simon’s problem.  arXiv preprint arXiv:1905.08549, 2019.

##  Appendix A An exact quantum algorithm for generalized Simon problem

Brassard and Høyer [10] provided an algorithm to solve Simon problem with
$O(n)$ queries exactly. In this section, we review the algorithm and make some
small adjustments to the algorithm to solve $\mathsf{GSP}(p,n,k)$.
Particularly, we replace the method of improving the success probability in
[10] with a more general method, amplitude amplification [11], such that the
algorithm needs to only make $O(n-k)$ queries.

We first give some notation. Define quantum query oracle $O_{f}$:
$O_{f}\ket{g}\ket{y}=\ket{g}\ket{f(g)+y}$. The query complexity of a quantum
algorithm is the number of $O_{f}$ used in the algorithm. Let
$G=\mathbb{Z}_{p}^{n}$ and $T_{0}$ be a transversal of $S$ in $G$, i.e,
$T_{0}$ consists of exactly one representative form each coset of $S$. For
$g,h\in G$, let

$g\cdot h=(\sum_{i=1}^{n}g_{i}h_{i})\mod p,$

where $g=(g_{1},...,g_{n})$ and $h=(h_{1},...,h_{n})$. For $H\leq G$, let

$H^{\perp}=\\{g\in G|g\cdot h=0\text{ for all }h\in H\\}$

denote the orthogonal subgroup of $H$. Let

$\mu(g,h)=e^{\frac{2\pi i}{p}gh},$ $F_{G}=\frac{1}{\sqrt{|G|}}\sum_{g,h\in
G}\mu(g,h)\ket{g}\bra{h},$ $\phi_{h}=\sum_{g\in G}\mu(h,g)\ket{g}\bra{g}.$

For $X\subseteq G$ and $g\in G$, let

$\ket{\phi_{g}X}=\frac{1}{|X|}\sum_{x\in X}\mu(g,x)\ket{x}.$

Next, we introduce the algorithm process. It is worth noting that the idea of
the quantum algorithm is to find a basis of $S^{\perp}$. Then
$S={(S^{\perp})}^{\perp}$. We give Algorithm 3 first, which is a subroutine in
Simon algorithm and generalized to the case of $\mathbb{Z}_{p}$. The goal of
Algorithm 3 is to obtain $\ket{\Psi}$. When we measure the first register of
$\ket{\Psi}$, we can get an element in $S^{\perp}$ with certain.

Algorithm 3 Simon subroutine

Input: Quantum state $\ket{0^{n}}\ket{0}$;

Procedure:

  1. 1.

Apply the inverse of transform $F_{G}$ to the first register producing an
equally-weighted superposition of all elements in the group $G$:

$\frac{1}{\sqrt{|G|}}\sum_{g\in G}\ket{g}\ket{0}.$

  2. 2.

Apply $O_{f}$, producing a superposition of all cosets of $H_{0}$:

$\frac{1}{|G|}\sum_{g\in G}\ket{g}\ket{f(g)}=\frac{1}{\sqrt{T_{0}}}\sum_{t\in
T_{0}}\ket{t+S}\ket{f(t)}.$

  3. 3.

Apply $F_{G}$ to the first register, producing a superposition over the
orthogonal subgroup $S^{\perp}$:

$\ket{\Psi}=\frac{1}{|T_{0}|}\sum_{t\in
T_{0}}\ket{\phi_{t}S^{\perp}}\ket{f(t)}.$

Output: Quantum state $\ket{\Psi}$.

Suppose we have obtained some element $y$ in $S^{\perp}$, we do not wish to
obtain it again. Instead, we wish to find a basis of $S^{\perp}$ as soon as
possible. Thus, Algorithm 4 is proposed to shrink the range of superposition
and avoiding obtaining the same elements. The input of Algorithm 4 can be
obtained from Algorithm 3.

Algorithm 4 Shrinking a subgroup

Input: Quantum state $\ket{\phi_{g}H}\ket{0}$; $H\leq G$ be a nontrivial
subgroup; $y\in H/\\{0^{n}\\}$; $j$ such that $y_{j}\neq 0$ and $K=\\{h\in
H|h_{j}=0\\}$.

Procedure:

  1. 1.

Apply operation $U_{1}:U_{1}\ket{x}\ket{z}=\ket{x}\ket{x+z}$ to the $j$th
qubit in the first register and the second register of
$\ket{\phi_{g}H}\ket{0}$, producing the state:

$\displaystyle\frac{1}{\sqrt{|H|}}\sum_{h\in H}\mu(g,h)\ket{h}\ket{h_{j}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{p}}\sum_{i\in\mathbb{Z}_{p}}\mu(g,iy)\left(\frac{1}{\sqrt{|K|}}\sum_{k\in
K}\mu(g,k)\ket{iy+k}\right)\ket{i}.$

  2. 2.

Apply operator $U_{2}:$ $U_{2}\ket{x}\ket{i}=\ket{x+iy}\ket{i}$ to the above
state. This produces

$\displaystyle\frac{1}{\sqrt{p}}\sum_{i\in\mathbb{Z}_{p}}\mu(g,iy)\left(\frac{1}{\sqrt{|K|}}\sum_{k\in
K}\mu(g,k)\ket{k}\right)\ket{i}$ $\displaystyle=$
$\displaystyle\ket{\phi_{g}K}\left(\frac{1}{\sqrt{p}}\sum_{i\in\mathbb{Z}_{p}}\mu(g,iy)\ket{i}\right).$

  3. 3.

Apply $F_{G}$ to the second register, producing a superposition:

$\ket{\phi_{g}K}\ket{g\cdot y}.$

Output: Quantum state $\ket{\phi_{g}K}\ket{g\cdot y}$.

Suppose $Y=\\{y_{1},...,y_{m}\\}$ is a known linearly independent set in
$S^{\perp}$ ($0\leq m<n-k$). Then there exists a subgroup $K_{m}\leq
S^{\perp}$ such that $S^{\perp}=K_{m}+\langle Y\rangle$ and a quantum routine
$\mathcal{A}_{m}$ such that
$\mathcal{A}_{m}\ket{\phi_{g}S^{\perp}}\ket{0^{m}}=\ket{\phi_{g}K_{m}}\ket{g\cdot
y_{1},...,g\cdot y_{m}}$ by applying Algorithm 4 repeatedly. Moreover, we have
a quantum routine $\mathcal{A}^{\prime}_{m}$ such that
$\mathcal{A}^{\prime}_{m}\ket{0^{n}}\ket{0}\ket{0^{m}}=\frac{1}{\sqrt{|T_{0}|}}\sum_{t\in
T_{0}}\ket{\phi_{t}K_{m}}\ket{f(t)}\ket{t\cdot y_{1},...,t\cdot y_{m}}$ by
applying Algorithm 3 and $\mathcal{A}_{m}$. Algorithm 3 makes one query,
$\mathcal{A}_{m}$ does not make queries, thus $\mathcal{A}^{\prime}_{m}$ makes
one query.

If we can measure the first register of the final state in
$\mathcal{A}^{\prime}_{m}$, we can obtain an element $y\in K_{m}$. Once $y$ is
nonzero, we can add $y$ into $Y$ to get a larger known linearly independent
set in $S^{\perp}$. Thus, we say Algorithm $\mathcal{A}^{\prime}_{m}$ is
successful if the measurement result of the first register of the final state
is a nonzero element in $K_{m}$. The success probability of
$\mathcal{A}^{\prime}_{m}$ is $1-1/|K_{m}|=1-1/p^{n-k-m}$.

Furthermore, we wish to avoid obtaining zero element after measurement. Since
$\frac{1}{\sqrt{1-1/p^{n-k-m}}}\leq\frac{1}{\sqrt{1-1/p}}\leq\sqrt{2}$, we use
$O(\frac{1}{\sqrt{1-1/p^{n-k-m}}})=O(1)$ applications of
$\mathcal{A}^{\prime}_{m}$ and ${\mathcal{A}^{\prime}_{m}}^{-1}$ to get an
algorithm $\mathcal{A}^{\prime\prime}_{m}$ that can obtain a nonzero element
in $K_{m}$ with certain by the amplitude amplification technique of [11].
${\mathcal{A}^{\prime}_{m}}^{-1}$ needs to use $O^{-1}_{f}$ and other
operations not related to $f$. Since $O_{f}^{2}=I$ by definition,
$O^{-1}_{f}=O_{f}$. Thus, $\mathcal{A}^{\prime\prime}_{m}$ makes $O(1)$
queries.

Finally, we gave Algorithm 5 to solve $\mathsf{GSP}(p,n,k)$ exactly. During
the iteration of each time, an element is added into $Y$ to consist of a
larger linearly independent set in $S^{\perp}$. Finally, $\langle
Y\rangle=S^{\perp}$.

Algorithm 5 An exact quantum algorithm for $\mathsf{GSP}(p,n,k)$

1: $Y=\emptyset$;

2: for $i=0\ to\ n-k-1$ do

3: For a subgroup $K_{i}\leq S^{\perp}$ satisfying that
$S^{\perp}=K_{i}+\langle Y\rangle$, perform Algorithm
$\mathcal{A}^{\prime\prime}_{i}$ to obtain a nonzero element $y_{i}\in K_{i}$;

4: $Y=Y\cup\\{y_{i}\\}$;

5: end for

6: return $\langle Y\rangle^{\perp}$;

Since $\mathcal{A}^{\prime\prime}_{i}$ makes $O(1)$ queries for $1\leq i\leq
k$, the total number of queries is $O(n-k)$.