# Zero sum subsequences and hidden subgroups

Muhammad Imran
Department of Algebra,
Budapest University of Technology and Economics,
Egry József u. 1, H-1111 Budapest, Hungary.
E-mail<EMAIL_ADDRESS>Gábor Ivanyos
Computer and Automation Research Institute,
Eötvös Loránd Research Network,
Kende u. 13-17, H-1111 Budapest, Hungary.
E-mail<EMAIL_ADDRESS>
###### Abstract

We propose a method for solving the hidden subgroup problem in nilpotent
groups. The main idea is iteratively transforming the hidden subgroup to its
images in the quotient groups by the members of a central series, eventually
to its image in the commutative quotient of the original group; and then using
an abelian hidden subgroup algorithm to determine this image. Knowing this
image allows one to descend to a proper subgroup unless the hidden subgroup is
the full group. The transformation relies on finding zero sum subsequences of
sufficiently large sequences of vectors over finite prime fields. We present a
new deterministic polynomial time algorithm for the latter problem in the case
when the size of the field is constant. The consequence is a polynomial time
exact quantum algorithm for the hidden subgroup problem in nilpotent groups
having constant nilpotency class and whose order only have prime factors also
bounded by a constant.

#### Keywords:

hidden subgroup problem, nilpotent group, zero sum subsequence, exact quantum
algorithm.

#### Acknowledgments.

The research of the second author was supported by the Hungarian Ministry of
Innovation and Technology NRDI Office within the framework of the Artificial
Intelligence National Laboratory Program.

##  1 Introduction

The standard version of the hidden subgroup problem (HSP for short) is the
following. Given a function $f$ on the group $G\rightarrow\\{0,1\\}^{r}$ with
the property that there is a subgroup $H$ such that $f(x)=f(y)$ if and only if
$x$ and $y$ are in the same left coset of $H$, find the subgroup $H$. Perhaps
Kitaev was the first who observed that Shor’s factoring and discrete logarithm
algorithms can be generalized to solve the HSP in finite abelian groups (and
also in certain infinite commutative groups) in polynomial time. Much less is
known about the complexity of the problem in non-commutative groups. The most
general result is due to Ettinger, Hoyer and Knill. They showed in [EHK04]
that the query complexity of the problem in finite not necessarily abelian
groups is polynomial. Regarding the time complexity, Kuperberg’s
subexponential time quantum algorithm [Kup05] for the HSP in dihedral and very
similar groups is perhaps the best known result. It has a remarkable extension
by Alagic, Moore and Russell [AMR07]to a special HSP in a class including non-
solvable groups. There are some classes of groups in which the HSP can be
solved in polynomial time. See the survey papers by Lomont [Lom04] and by Wang
[Wan10] for early results of this kind. The paper [LK07b] by Lomonaco and
Kauffman proposes interesting derivatives and generalizations of the Shor-
Kiteav algorithm. The paper [HK18] by Horan and Kahrobaei discusses
cryptographic aspects of the HSP and reports also on more recent results. The
hidden shift problem in abelian groups (and hence the HSP in the related
semidirect product groups) appears to be quite popular in post-quantum
cryptography, see, e.g., [CM23] by Castryck and Vander Meeren and [AR17] by
Alagic and Russell. In [BL21], Bae and Lee propose a polynomial time solution
to a continuous version of the hidden shift problem.

A quantum procedure is exact if it returns a correct output (after a final
measurement) with probability one. Besides that exact quantum algorithms can
be considered as counterparts of deterministic classical methods, their
measurement-free versions can serve as ingredients of larger unitary
procedures. The method of [EHK04] has an exact version, so it is natural to
ask that in which classes of groups can the HSP be solved by an exact quantum
algorithm in polynomial time. Brassard and Hoyer [BH97] presented a polynomial
time exact method that works in ${\mathbb{Z}}_{2}^{n}$. In [CQ18], Cai and Qiu
proposed a simpler efficient exact method for Simon’s problem (a special,
though arguably the hardest instance of the HSP in ${\mathbb{Z}}_{2}^{n}$).
Efficient exact algorithms with optimal query complexity for the HSP in
${\mathbb{Z}}_{2}^{n}$ appeared independently in [Bon21] by Bonnetain and in
[WQT+22] by Wu et al. Mosca and Zalka in [MZ03] proposed an efficient exact
solution of the discrete logarithm problem in cyclic groups of known order. An
exact quantum algorithm for the HSP in ${\mathbb{Z}}_{m^{k}}^{n}$ for general
$m$ was presented recently in [II22], settling the case of abelian groups
under the assumption that a multiple of the prime factors of the order of the
group is known.

In this paper we present an approach to solving the hidden subgroup problem in
nilpotent groups that have nilpotency class $O(1)$. Our main result is a
polynomial time exact quantum algorithm for the HSP in such groups only having
prime factors also of size $O(1)$ in their order. We assume that the group $G$
is given as a black-box group with unique encoding. The main strategy of our
algorithm is essentially a reduction to instances of the hidden subgroup
problem in quotient groups of subgroups of $G$. We choose an input model
suitable for such a reduction.

In the standard version, the input is given by an oracle which is a unitary
map computing $\lvert x\rangle\lvert f(x)\rangle$ from $\lvert x\rangle\lvert
0\rangle$. The usual hidden subgroup algorithms start with computing the
superposition $\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert
x\rangle\lvert f(x)\rangle$ using the oracle and most of them ignore the
second register that holds the value of $f$ and work with the coset
superpositions $\lvert xH\rangle=\frac{1}{\sqrt{\lvert H\rvert}}\sum_{y\in
H}\lvert xy\rangle$ in the sequel, see e.g., [LK07b]. These methods, as noted
in [Kup05], remain applicable in the context where the oracle is assumed to
generate copies of a mixture of the coset superpositions. This holds in
particular in the case of the exact abelian hidden subgroup algorithm of
[II22].

Specifically, we consider the state $\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in
G}\lvert x\rangle\lvert f(x)\rangle$ as a purification of the mixed state
$\Xi_{G,H}=\frac{1}{\lvert G:H\rvert}\sum_{x\in X}\lvert xH\rangle\langle
xH\rvert$, where $X$ is any left transversal of $H$ in $G$, in order to have a
unitary oracle. The state $\Xi_{G,H}$ is referred to as a (hidden) subgroup
state. We assume that our hidden subgroup $H$ is given by a unitary map
(referred as oracle) that, on zero input, returns a copy of an arbitrary
(though fixed) purification of the subgroup state $\Xi_{G,H}$.

It will be convenient to introduce a subtask of the HSP, namely computing the
hidden subgroup modulo the commutator subgroup of $G$, that is, the subgroup
$HG^{\prime}$ where $H$ is the hidden subgroup. We use the shorthand HSMC for
this problem. To illustrate the power of HSMC in nilpotent groups note that it
naturally includes the commutative case of the HSP and that having computed
the subgroup $HG^{\prime}$ and it is a proper subgroup of $G$ then we can
descend to it to compute $H$, while if $HG^{\prime}=G$ then $H=G$ because in a
nilpotent group every maximal subgroup contains the commutator.

We give a high-level description of a strategy for solving the problem HSMC in
a class of nilpotent groups. We call a group $G$ semi-elementary if $G$ is a
$p$-group for some prime $p$ such that $G/G^{\prime}$ is elementary abelian.
In a semi-elementary group $G$, our strategy for computing the hidden subgroup
modulo the commutator is based on iterating the following procedure. Assume
that $L$ is an elementary abelian subgroup contained in the center of $G$.
Then we create a copy of the subgroup state corresponding to $HL/L$ in the
quotient group $G/L$ from sufficiently many copies of the subgroup state for
$H$ in $G$. We refer to this procedure (as well as some simpler ones) as
subgroup state conversion. This conversion is based on finding zero sum
subsequences of sufficiently long sequences of elements of $L$. Eventually, in
$c-1$ rounds of iteration, where $c$ is the nilpotency class of $G$, we
compute a copy of the subgroup state corresponding to $HG^{\prime}/G^{\prime}$
in $G$. (The semi-elementary property ensures the existence of a standard
central series of length $c$ with elementary abelian factors.) Finally, from
sufficiently many copies of such subgroup states we compute
$HG^{\prime}/G^{\prime}$ using the exact abelian hidden subgroup algorithm of
[II22]. Fortunately, semi-elementary groups occur as factor groups of
subgroups of nilpotent groups frequently enough to make a reduction from the
HSP to the special case of HSMC possible, see Proposition 1 for details. The
main result we obtain is the following.

######  Theorem 1.

Suppose that $G$ is a nilpotent group of class bounded by a constant and that
the prime factors of $\lvert G\rvert$ are also bounded by a constant. We
assume that $G$ is a black-box group with unique encoding of elements by
$\ell$-bit strings. Then there is an exact quantum algorithm that solves the
hidden subgroup problem in $G$ using $\operatorname{\mathrm{poly}}(\ell)$
operations and $\operatorname{\mathrm{poly}}(\log\lvert G\rvert)$ calls to the
subgroup state creating oracle and its inverse.

Related results. In the exact setting, [II22] efficiently solves the abelian
case without the restriction on the prime factors of $\lvert G\rvert$. There
are quite a few related non-exact polynomial-time algorithms. Among them, the
result of [FIM+14], which solves the HSP in solvable groups that have derived
series and exponent bounded by constants, is perhaps the closest to Theorem 1.
This class of groups covers the groups for which our result is applicable,
except those that have exponent divisible by large powers of small primes.
Note however, that the case of these groups could be efficiently treated by a
combination of the reduction of Proposition 1 with the algorithm of [FIM+14].
We remark that the semidirect product group in which the HSP is equivalent to
the hidden shift problem over ${\mathbb{Z}}_{2^{k}}^{n}$ is a nilpotent group
of class $k$. Bonnetain and Naya-Plasencia [BNP18] propose a non-exact method
whose main ingredient can be considered as a combination of Kuperberg’s sieve
with finding zero sum subsequences in ${\mathbb{Z}}_{2}^{n}$ using linear
algebra.

The case of nilpotency class at most two is efficiently treated by the non-
exact method of [ISS12], without any restriction on the size of the prime
factors of $\lvert G\rvert$. It is worth mentioning that by technical content,
[ISS12] can be considered as the closest relative of the present paper. The
idea of reducing the HSP to HSMC stems from there and many ingredients of the
reduction appeared in that paper. Also, the key tool of [ISS12], using several
coset superpositions and the quantum Fourier transform of a central subgroup
can be considered as some (though less transparent) form of subgroup state
conversion. In the class two case, however, there is a more powerful tool to
cancel out characters of the subgroup: one can also apply twists with certain
nice automorphisms of the group that do not change the hidden subgroup too
much. Unfortunately, such automorphisms do not exist in general nilpotent
groups of class greater than two.

The methods of [DHIS14, IS17] offer efficient solution to the HSP in certain
nilpotent groups of higher class, again with potentially large prime factors
in there orders. These groups have a normal subgroup with an abelian factor
group of restricted kind (e.g., cyclic). These methods as well as that of
[FIM+14] are of highly non-exact nature. Probably, the technique of [DHIS14]
can be made exact with some efforts.

The Davenport constant $S(A)$ of a finite abelian group$A$ is the smallest
number $s$ such that any sequence of $s$ elements of $A$ contains a nonempty
subsequence adding up to the zero element of $A$. The name comes from that H.
Davenport proposed determining $S(A)$ in the case when $A$ is the ideal class
group of a number field as a measure for non-uniqueness of factorization of
the integers of the field. The general problem has become a famous question of
additive combinatorics. Olson [Ols69] determined the exact value of the
Davenport constant of $p$-groups; in particular for ${\mathbb{Z}}_{p}^{n}$ it
is $1+n(p-1)$. What we are looking for is an ”effective” Davenport constant:
what is the smallest number $S^{\prime}=S^{\cal B}(A)$ such that from any
sequence of $S^{\prime}$ elements of $A$, algorithm ${\cal B}$ finds a non-
empty zero sum subsequence in time polynomial in $S^{\prime}\log\lvert
A\rvert$ (roughly this is the bit size of the input sequence). In this paper
we give a deterministic algorithm $\cal B$ running in time
$\operatorname{\mathrm{poly}}(n)$, that, for $p=O(1)$, given a sequence of
$S^{\cal B}({\mathbb{Z}}_{p}^{n})=\operatorname{\mathrm{poly}}(n)$ vectors
from ${\mathbb{Z}}_{p}^{n}$, returns a zero sum subsequence.

The structure of the rest of the paper is the following. In Section 2, we give
some background material on exact quantum procedures, on nilpotent black-box
groups and on computations with them, on (hidden) subgroups states and their
purifications and present methods to convert subgroup states in the entire
group to those in subgroups and - in certain very easy cases - in factor
groups. Proposition 1, the existence of an exact polynomial time reduction
from the HSP in general nilpotent groups to the problem HSMC in semi-
elementary groups is proved in Section 3. Section 4 is devoted to converting
several copies of a subgroup state in a semi-elementary group to a copy of a
subgroup state in the abelian factor of the group. As an application of the
technique, we prove Proposition 2 which tells us that we can solve by a
polynomial time exact quantum algorithm the problem HSMC in a semi-elementary
$p$-group of constant nilpotency class provided that we can find zero sum
subsequences of sequences consisting of $\operatorname{\mathrm{poly}}(n\log
p)$ vectors from ${\mathbb{Z}}_{p}^{n}$ in time
$\operatorname{\mathrm{poly}}(n\log p)$. In Section 5, we prove Theorem 2 on
efficiently solvability the latter task in the case when $p$ is bounded by a
constant. Propositions 1 and 2, together with Theorem 2, immediately imply
Theorem 1. Section 6 is devoted to concluding remarks.

##  2 Preliminaries

###  2.1 On exact quantum computations

To obtain sufficiently general intermediate results, we use the model of
uniform circuit families described by Nishimura and Ozawa [NO05]. This is
because some of the exact methods of [II22] as well as our main conversion
technique work under the assumption that the quantum Fourier transforms and
their inverses modulo the prime factors of $\lvert G\rvert$ can be exactly
implemented. As it is pointed out in [NO02], this task cannot be accomplished
using a fixed finite gate set. For the sake of transparency, we state our
intermediate result using assumptions on availability of the quantum Fourier
transforms rather than on gates required by the exact implementations of them.
(See the implementation of the Fourier transform modulo general numbers
proposed by Mosca and Zalka [MZ03].) Note however, that for the case of our
Theorem 1, where these primes are assumed to be bounded by a constant, a
constant number of gates are sufficient and hence, by [NO09], the theorem
remains valid in the quantum Turing machine model of Bernstein and Vazirani
[BV97].

###  2.2 Groups

For standard notations and concepts from group theory such as subgroups,
normal subgroups, cosets, conjugates, commutators, commutator subgroup,
center, etc., we refer the reader to the textbooks, e.g., to [Rob95]. For
subsets $U$ and $V$ of $G$ we denote by $UV$ the set $\\{uv:u\in U,v\in V\\}$.
If both $U$ and $V$ are subgroups and either $U$ or $V$ is normal in $G$ then
$UV$ is a subgroup. For subgroups $U,V$, by $[U,V]$ we denote the subgroup
generated by the commutators $[u,v]$ ($u\in U,v\in V$). Recall that the lower
central series of a finite group $G$ is the sequence
$G=G_{0}>G_{1}>\ldots>G_{c}$ of normal subgroups $G_{i}\lhd G$ recursively
defined as $G_{i}=[G,G_{i-1}]$. Here we assume that $c$ is the smallest index
$i$ such that $G_{i}=[G,G_{i}]$. The group $G$ is nilpotent if $G_{c}=\\{1\\}$
and then $c$ is called the (nilpotency) class of $G$. A finite group is
nilpotent if and only if it is the direct product of its Sylow subgroups.

To obtain sufficiently general results, we work over black-box groups with
unique encoding of elements. The concept captures various ”real” groups such
as permutation groups and matrix groups over finite fields. Elements of a
black-box group are represented by binary strings of a certain length $\ell$
and the group operations are given by oracles and as input, a generating set
for the group is given. Subgroups will also be given by sets of generators.
One can use the exact polynomial time quantum membership test of [II22] to
reduce the size of generating sets to at most $\log\lvert G\rvert$.

During the rest of this part, we assume that $G$ is a nilpotent black-box
group of class $c$ and the prime factors of $\lvert G\rvert$ are known.

For a normal subgroup $N$ of $G$, the subgroup $[G,N]$ is a normal subgroup of
$G$ contained in $N$. If $\Gamma$ and $\Delta$ are sets of generators for $G$
and $N$, respectively, a generating set for $[G,N]$ can be obtained by taking
the commutators $[x,y]$ for $x\in\Gamma,y\in\Delta$ and then adding iterated
commutators with elements of $\Gamma$ until the subgroup generated by the
elements stabilizes. For testing stabilization, one can use the exact quantum
subgroup membership algorithm of [II22]. This gives a polynomial time exact
method in particular to compute the lower central series.

Below we describe efficient solutions to some further group theoretic tasks
that we use in our hidden subgroup algorithm. The $p$-Sylow subgroup of $G$
can be computed as follows. Let $\Gamma$ be a generating set for $G$. Then for
each $g\in\Gamma$ we compute the order $o_{g}$ of $g$ and decompose $o_{g}$ as
the product $p^{\alpha}{o_{g}}^{\prime}$ where ${o_{g}}^{\prime}$ is coprime
with $p$. Then the $g^{{o_{g}}^{\prime}}$ ($g\in\Gamma$) generate the (unique)
$p$-Sylow subgroup of $G$. We shall compute hidden subgroups in $G$ by
computing the intersections with the Sylow subgroups.

The normalizer of a subgroup of $G$ can be computed using the deterministic
polynomial method of Kantor and Luks [KL90]. It was originally described for
nilpotent permutation groups but it also finds normalizers in any nilpotent
black box group of order having small prime factors only.

Assume that $L$ is a subgroup of $G$. It will be useful to decompose elements
$x$ of $G$ as products of the form $\alpha_{L}(x)\beta_{L}(x)$ where
$\beta_{L}(x)\in L$ and $\alpha_{L}(x)$ depend only on the coset $xL$. (Thus
the range of $\alpha_{L}$ is a transversal of $L$ in $G$.) To this end,
compute a chief series (a series of normal subgroups with cyclic factors of
prime order) $G=K_{0}>K_{1}>\ldots>K_{r}=1$. Perhaps the easiest way to obtain
such series is taking a refinement of the lower central series. By taking the
subgroups $K_{i}L$, and removing repeated elements, we obtain a subnormal
series $G=M_{0}>M_{1}>\ldots>M_{s}=L$ with cyclic factors of prime order. Also
take elements $a_{i}\in M_{i-1}\setminus M_{i}$ and denote by $p_{i}$ the
order of ${M_{i-1}/M_{i}}$ ($i=1,\ldots,s$). Then the elements
$a_{1}^{\gamma_{1}}a_{2}^{\gamma_{2}}\ldots a_{s}^{\gamma_{s}}$
($(\gamma_{1},\ldots\gamma_{s})\in\prod_{i=1}^{s}{\mathbb{Z}}_{p_{i}}$) are a
left transversal of $L$ in $G$. For an element $x\in G$, the representative of
the coset in this transversal can be computed as follows. First we find the
smallest non-negative integer $\gamma_{1}$ such that $xa_{1}^{-\gamma_{1}}\in
M_{1}$ by computing the base $a_{1}$ discrete logarithm of $x$ modulo $M_{1}$.
This can be done by solving an instance of the hidden subgroup problem in
${\mathbb{Z}}_{p_{1}}^{2}$. Specifically, we define the function
$(\beta,\gamma)\mapsto\lvert x^{\gamma}\rangle\lvert
a_{1}^{-\beta}M_{1}\rangle$. The function can be evaluated with the aid of
computing the uniform superposition $\lvert M_{1}\rangle$ using the exact
version [II22] of Watrous’s method [Wat01]. The values are $p$ pairwise
orthogonal states and the hidden subgroup is
$\\{(\delta,\gamma):x^{\delta}a_{1}^{-\gamma}\in M_{1}\\}$. We use the exact
hidden subgroup algorithm of [II22] to find a generator of this group. From
this, $\gamma_{1}$ can be obtained in an obvious way. Now we proceed with
$xa_{1}^{-\gamma_{1}}$ to compute $\gamma_{2}$, and so on. We set
$\alpha_{L}(x)=a_{1}^{\gamma_{1}}\ldots a_{r}^{\gamma_{r}}$ and
$\beta_{L}(x)=\alpha_{L}(x)^{-1}x$.

If $L$ is a normal subgroup of $G$, we can encode the coset $xL$ by
$\alpha_{L}(x)$. This makes the factor group $G/L$ a black-box group: the
elements are encoded by the elements of the transversal $\\{\alpha(x);x\in
G\\}$ and the multiplication oracle is obtained as a composition of the
multiplication oracle for $G$ with the computation of the function
$\alpha_{L}$.

###  2.3 Subgroup states and purifications

Let $G$ be a finite group and let $H$ be a subgroup of $G$. We consider
elements of the group algebra $\mathbb{C}G$ as pure quantum states. (The
”natural” scalar product $(\sum_{x}\alpha_{x}\lvert
x\rangle,\sum_{y}\alpha_{y}\lvert
y\rangle)=\sum\alpha{\overline{\beta}}xy^{-1}$ makes $\mathbb{C}G$ a Hilbert
space where the group elements form an orthonormal basis.)

A (left) coset superposition of $H$ in $G$ is the uniform superposition
$\lvert aH\rangle=\frac{1}{\sqrt{\lvert H\rvert}}\sum_{h\in H}\lvert
ah\rangle$ where $a\in G$. The (left) subgroup state of $H$ in $G$ is the
mixed state with the density matrix

$\Xi_{G,H}=\frac{1}{\lvert G\rvert}\sum_{a\in G}\lvert aH\rangle\langle
aH\rvert=\frac{1}{\lvert G:H\rvert}\sum_{a\in X}\lvert aH\rangle\langle
aH\rvert,$

where $X$ is any left transversal (a set of representatives of the left
cosets) of $H$ in $G$.

A purification of $\Xi_{G,H}$ is any pure state
$\lvert\psi\rangle\in\mathbb{C}G\otimes V$ for some Hilbert space $V$ such
that $\Xi_{G,H}$ is the relative trace of $\lvert\psi\rangle\langle\psi\rvert$
with respect to the second subsystem. For general facts about purification of
mixed states, in particular for the connection with Schmidt decompositions, we
refer the reader to Section 2.5 of [NC10]. The following lemma gives a
characterization of purifications of subgroup states.

######  Lemma 1.

The pure state $\lvert\psi\rangle\in\mathbb{C}G\otimes V$ is a purification of
the subgroup state $\Xi_{G,H}$ if and only if it can be written as

$\lvert\psi\rangle=\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert
x\rangle\lvert v(x)\rangle,$

where the states $\lvert v(x)\rangle$ and $\lvert v(y)\rangle$ are equal if
$x$ and $y$ are in the same left coset of $H$ and orthogonal otherwise.

###### Proof.

The ”if” part follows easily from that the conditions on $\lvert v()\rangle$
imply $\lvert\psi\rangle=\frac{1}{\sqrt{k}}\sum_{a\in X}\lvert aH\rangle\lvert
v(a)\rangle$.

To see the the ”only if” part, recall that a Schmidt decomposition of a state
$\lvert\psi\rangle\in\mathbb{C}G\otimes V$ is of the form
$\lvert\psi\rangle=\sum_{i=1}^{m}\lambda_{i}\lvert u_{i}\rangle\lvert
v_{i}\rangle$ where $m=\lvert G\rvert$, $\lvert u_{1}\rangle,\ldots,\lvert
u_{m}\rangle$ is an arbitrary orthonormal basis of $\mathbb{C}G$ in which the
relative trace of $\lvert\psi\rangle\langle\psi\rvert$ w.r.t. to the second
subsystem is diagonal (with entries $\lambda_{1},\ldots,\lambda_{m}$) and the
system of the vectors $v_{i}$ corresponding to nonzero eigenvalues
$\lambda_{i}$ is an orthonormal system of vectors in $V$. The vectors $v_{i}$
depend on the choice of the basis $\lvert u_{i}\rangle$ ($i=1,\ldots,m$).
Notice that the only nonzero eigenvalue of $\Xi_{G,H}$ is $\frac{1}{k}$ with
multiplicity $k$, where $k=\lvert G:H\rvert$. The coset superpositions give an
orthonormal basis of the corresponding eigenspace. Thus, if
$\lvert\psi\rangle$ is a purification of $\Xi_{G,H}$ then a Schmidt
decomposition of $\lvert\psi\rangle$ which is a purification of $\Xi_{G,H}$ is
of the form $\lvert\psi\rangle=\frac{1}{\sqrt{k}}\sum_{i=1}^{k}\lvert
u_{i}\rangle\lvert v_{i}\rangle$ where $\lvert u_{1}\rangle,\ldots,\lvert
u_{k}\rangle$ is an arbitrary orthonormal basis of the
$\frac{1}{k}$-eigenspace of $\Xi_{G,H}$ and $\lvert v_{1}\rangle,\ldots,\lvert
v_{k}\rangle$ is an orthonormal system of $V$. In particular, if
$X=\\{a_{1},\ldots,a_{k}\\}$ then by taking $\lvert u_{i}\rangle=\lvert
a_{i}H\rangle$ and by defining $\lvert v(x)\rangle=\lvert v_{i}\rangle$ for
$x\in a_{i}H$, we obtain $\lvert\psi\rangle=\frac{1}{\sqrt{k}}\sum_{a\in
X}\lvert aH\rangle\lvert v(a)\rangle=\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in
G}\lvert x\rangle\lvert v(x)\rangle$. ∎

###  2.4 Basic subgroup state conversions

Given a subgroup $L$ of $G$, a copy of (a purification of) the subgroup state
$\Xi_{G,H}$ can be ”converted” to a copy of (a purification of) $\Xi_{L,H\cap
L}$ by replacing $\lvert x\rangle$ with the decomposition
$\lvert\beta_{L}(x)\rangle\lvert\alpha_{L}(x)\rangle$ obtained by the method
outlined in Subsection 2.2 for $x\in G$, and ”ignoring”
$\lvert\alpha_{L}(x)\rangle$ (passing this part to the purifying subsystem).
To see this, let $\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert
x\rangle\lvert\psi(x)\rangle$ be a purification of $\Xi_{G,H}$, with
$\lvert\psi(x)\rangle$ and $\lvert\psi(y)\rangle$ are equal if and only if
$y^{-1}x\in H$, and orthogonal otherwise. Then, the substitution gives the
state $\frac{1}{\sqrt{\lvert L\rvert}}\sum_{x\in L}\lvert
x\rangle\frac{1}{\sqrt{\lvert G:L\rvert}}\sum_{y\in Y}\lvert
y\rangle\lvert\psi(yx)\rangle$ where $Y=\\{\alpha_{L}(z):z\in G\\}$. Now if
$x_{1},x_{2}\in L$ are from the same left coset of $H\cap L$ then
$\lvert\psi(yx_{1})\rangle=\lvert\psi(yx_{2})\rangle$ for every $y\in Y$ and
hence the states $\frac{1}{\sqrt{\lvert G:L\rvert}}\sum_{y\in Y}\lvert
y\rangle\lvert\psi(yx_{i})\rangle$ are equal ($i=1,2$), while otherwise they
do not overlap as for $y_{1},y_{2}\in Y$ either $\lvert y_{1}\rangle$ and
$\lvert y_{2}\rangle$ are orthogonal or (for $y_{1}=y_{2}$)
$\lvert\psi(y_{1}x_{1})\rangle$ and $\lvert\psi(y_{1}x_{2})\rangle$ are
orthogonal. We shall refer to this procedure as restriction. The term is
justified by that in the standard version of the HSP, one could obtain an
instance of the HSP in the subgroup $L$ by restricting the “hiding function”
to $L$.

Similarly, assume that $L$ is a normal subgroup of $G$ contained in $H$. Then
a copy of (a purification of) the subgroup sate $\Xi_{G,H}$ can be converted
to a copy of (a purification of) $\Xi_{G/L,H/L}$ by replacing $x$ with
$\lvert\alpha_{L}(x)\rangle\lvert\beta_{L}(x)\rangle$ and passing
$\lvert\beta_{L}(x)\rangle$ to the purifying subsystem. This corresponds to
the technique called ”pushing” in [LK07a, LK07b].

##  3 A group-theoretic reduction

In this section we prove the following.

######  Proposition 1.

Let $G$ be a nilpotent black-box group of class at most $c$ and assume that
the prime factors of $\lvert G\rvert$ are given as part of the input and that
for each such prime $p$ the quantum Fourier transform modulo a multiple of $p$
and its inverse can be implemented by an efficient exact quantum procedure.
Then, the HSP in $G$ can be reduced by an exact procedure in time
$\operatorname{\mathrm{poly}}(\log\ell)$ to
$\operatorname{\mathrm{poly}}(\log\lvert G\rvert)$ instances of the problem
HSMC in semi-elementary quotient groups of subgroups of $G$. (The elements of
$G$ are assumed to be uniquely encoded by strings of length $\ell$.)

###### Proof.

A finite nilpotent group $G$ is the direct product of its Sylow subgroups.
Therefore any subgroup $H$ is the product of its Sylow subgroups. The
$p$-Sylow subgroup of $H$ is $P\cap H$ where $P$ is the $p$-Sylow subgroup of
$G$. The Sylow subgroups of $G$ can be computed using the method outlined in
Subsection 2.2. One can convert subgroup states in $G$ to subgroup states in
$P$ using restriction, see Subsection 2.4.

In the rest of the description of the reduction we assume that $G$ is a
$p$-group. We maintain a subgroup $H_{0}$ of $H$. Initially
$H_{0}=\\{1_{G}\\}$. In each round of an outer loop of the algorithm $H_{0}$
will be increased if $H_{0}<H$. If $H_{0}$ is already $G$ then we can
obviously stop. We will also maintain a subgroup $K$ of $G$ such that if
$H_{0}<H$ then even $H_{0}<K\cap H$. Initially $K=N_{G}(H_{0})$. This is a
good choice because in a nilpotent group every proper subgroup has a strictly
larger normalizer, therefore if $H_{0}<H$ then $H_{0}<N_{H}(H_{0})=H\cap
N_{G}(H_{0})$. In an inner loop $K$ will be decreased until either $H_{0}$ is
increased or $K$ becomes identical with $H_{0}$. In the latter case we can
conclude that $H=H_{0}$ and stop the whole procedure. If the abelian factor
$K/(K^{\prime}H_{0})$ is not elementary then we can replace $K$ with a proper
subgroup as follows. Let $L>K^{\prime}H_{0}$ be the subgroup of $K$ such that
$L/(K^{\prime}H_{0})$ contains all the elements of order $p$ of
$K/(K^{\prime}H_{0})$. To compute $L$, first compute $K^{\prime}$ and
$K^{\prime}H_{0}$. Then take the set of generators $\Gamma$ for $K$ and for
each element $g\in\Gamma$, compute the smallest positive integer $\alpha_{g}$
such that $g^{p^{\alpha_{g}}}\in K^{\prime}H_{0}$. The elements
$g^{p^{\alpha_{g}-1}}$ ($g\in\Gamma$) generate $L$. If $L$ is a proper
subgroup of $K$ then we replace $K$ with $L$ and repeat the step above.
(Correctness of this is justified by observing that $L/H_{0}$ contains all the
elements of order $p$ of $K/H_{0}$, whence if $H\cap K>H_{0}$ then also $H\cap
L>H_{0}$.) Otherwise we have achieved that $K/(K^{\prime}H_{0})$ is elementary
abelian. Then we compute $(H\cap K)K^{\prime}/H_{0}$ using HSMC. If $(H\cap
K)K^{\prime}=K$ then $H\cap K=K$ because $K^{\prime}$ is contained in every
maximal subgroup of $K$. Then we can increase $H_{0}$ by replacing $H_{0}$
with $K$ and continue the outer loop. If $(H\cap K)K^{\prime}<K$ we can
replace $K$ with $(H\cap K)K^{\prime}$ and continue the inner loop.

Based on the descriptions above, we summarize the exact algorithm in the
pseudocode below.

Algorithm 1 Reduction to HSMC

1:Initialize: $H_{0}\leftarrow 1_{G}$;

2:while $H_{0}<G$ do

3: $K\leftarrow N_{G}(H_{0})$;

4: ${Found}\leftarrow\mbox{False}$;

5: while ${Found}=\mbox{False}$ do

6: if $K/(K^{\prime}H_{0})$ is elementery then

7: Use HSMC to compute $(H\cap K)K^{\prime}/H_{0}$;

8: if $(H\cap K)K^{\prime}=K$ then

9: $H_{0}\leftarrow K$;

10: ${Found}\leftarrow\mbox{True}$;

11: else

12: $K\leftarrow(H\cap K)K^{\prime}$;

13: if $K=H_{0}$ then

14: return $H=K$.

15: end if

16: end if

17: else

18: For each $g\in\Gamma_{K}$ compute the smallest positive integer
$\alpha_{g}$ with $g^{p^{\alpha_{g}}}\in K^{\prime}H_{0}$;

19: Compute $L=\langle g^{p^{\alpha_{g}-1}}~{}|~{}g\in\Gamma_{K}\rangle$;

20: $K\leftarrow L$;

21: end if

22: end while

23:end while

If $\lvert G\rvert=p^{n}$ then the outer loop is executed at most $n$ times
while within each round of the outer loop the inner loop has at most $n$
rounds. Thus we need at most $n^{2}$ calls to the HSMC procedure for factors
of subgroups of $G$ and further $n^{2}\operatorname{\mathrm{poly}}(\ell)$
group and other operations. Note that all the groups we need to apply the HSMC
procedure are of class at most $c$ because the family of nilpotent groups of
class at most $c$ is closed under taking subgroups and factor groups. ∎

##  4 The main conversion

Let $L$ be a subgroup of the center of $G$ isomorphic to
${\mathbb{Z}}_{p}^{n}$ where $p$ is a prime. Then $L$ is a normal subgroup of
$G$. Our aim is to convert a copy of the subgroup state $\Xi_{G,H}$ to a copy
of $\Xi_{G/L,HL/L}$. In the light of the second conversion (”pushing”)
described in Subsection 2.4, one could do it by converting first to a copy of
$\Xi_{G,HL}$.

To this end, it would be desirable to have a procedure that converts the coset
superposition $\lvert aH\rangle$ to $\lvert aHL\rangle$. A possible approach
would be computing $\lvert L\rangle=\frac{1}{\sqrt{\lvert L\rvert}}\sum_{z\in
L}\lvert z\rangle$ in a new register, multiplying $\lvert aH\rangle$ with it
to obtain $\frac{1}{\sqrt{\lvert HL\rvert}}\sum_{z\in L}\sum_{x\in H}\lvert
azx\rangle\lvert z\rangle$ and then trying to ”disentangle” $\lvert z\rangle$
from $\lvert azx\rangle$. The quantum Fourier transform of $L$ almost does
this job: if we apply it to the second register, we obtain the state

$\frac{1}{\sqrt{\lvert L\rvert}}\sum_{y\in
L}\frac{\omega^{(y,z)}}{\sqrt{\lvert HL\rvert}}\sum_{z\in L}\sum_{x\in
H}\lvert azx\rangle\lvert y\rangle,$

where $\omega=e^{\frac{2\pi i}{p}}$ and by $(,)$ we denote the standard scalar
product of $L$ modulo $p$. For $y\in L$, let us denote by $P_{y}$ the linear
transformation of $\mathbb{C}G$ mapping $\lvert x\rangle$ to
$\frac{1}{\sqrt{\lvert L\rvert}}\sum_{z\in L}\omega^{(y,z)}\lvert xz\rangle$.
With this notation, the state we have can be rewritten as

$\frac{1}{\sqrt{\lvert L\rvert}}\sum_{y\in L}\lvert P_{y}(aH)\rangle\lvert
y\rangle.$

Using the assumption that $L$ is in the center of $G$, a direct calculation
shows that for every $x_{1},x_{2}\in G$, we have

$\lvert P_{y}(x_{1}x_{2})\rangle=\lvert
x_{1}P_{y}(x_{2})\rangle=\lvert(P_{y}(x_{1})x_{2})\rangle.$ (1)

It is also straightforward to see that for every $x\in G$ and for every $w\in
L$, we have

$\lvert wP_{y}(x)\rangle=\lvert P_{y}(x)w\rangle=\omega^{-(y,w)}\lvert
P_{y}(x)\rangle.$ (2)

We define the support of an element $\lvert u\rangle$ of $\mathbb{C}G$ as the
set of elements appearing with nonzero coefficient in the decomposition of
$\lvert u\rangle$ as a linear combination of group elements. Using equality
(1), one can show that if $x_{1}$ and $x_{2}$ are not in the same left coset
of $LH$ then the states $\lvert P_{y}(aH)x_{1}^{-1}\rangle$ and $\lvert
P_{y}(aH)x_{2}^{-1}\rangle$ are orthogonal. This is because the support of
$\lvert P_{y}(aH)x_{i}^{-1}\rangle$ is contained in
$LHx_{i}^{-1}=(x_{i}LH)^{-1}$ ($i=1,2$). On the other hand, if
$x_{1}H=x_{2}H$, then $Hx_{1}^{-1}=Hx_{2}^{-1}$ and the two states are equal.
By the characterization given in Lemma 1, it follows that for any left coset
$aH$, the state $\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert
x\rangle\lvert P_{0}(aHx^{-1})\rangle$ is a purification of $\Xi_{G,LH}$.

Of course it is hopeless to enforce $y=0$ in $\lvert
P_{y}(aH)x_{1}^{-1}\rangle$. However, we can compute a state with essentially
the same effect using several copies of the subgroup state and by applying an
algorithm that finds zero sum subsequences of sufficiently long sequences of
elements of $L$. Assume that we have a procedure that, for some $S=S(p,n)$,
given an element ${\underline{y}}=(y_{1},\ldots,y_{S})\in L^{S}$ computes a
non-empty subset $J({\underline{y}})$ of $\\{1,\ldots,S\\}$ such that
$\sum_{j\in J(\underline{y})}y_{j}=0$.

Then, for a sequence $\lvert a_{1}H\rangle\ldots\lvert a_{S}H\rangle$ we
compute first

${\lvert L\rvert}^{-S/2}\sum_{{\underline{y}}\in
L^{S}}\lvert{\underline{y}}\rangle\lvert P_{y_{1}}(a_{1}H)\rangle\ldots\lvert
P_{y_{S}}(a_{S}H)\rangle$

by applying the Fourier method outlined above component-wise. We next compute
$\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert x\rangle$ in a fresh
register and multiply by $x^{-1}$ the $j$th component of $\lvert
P_{y_{1}}a_{1}H\rangle\ldots\lvert P_{y_{S}}a_{S}H\rangle$ if $j\in
J({\underline{y}})$. Let
$\chi_{\underline{y}}:\\{1,\ldots,S\\}\rightarrow\\{0,1\\}$ denote the
characteristic function of $J({\underline{y}})$. Then the state we obtained is
$\frac{1}{\sqrt{\lvert G\rvert}}\sum_{x\in G}\lvert
x\rangle\lvert\psi(x)\rangle$, where

$\lvert\psi(x)\rangle={\lvert L\rvert}^{-S/2}\sum_{{\underline{y}}\in
L^{S}}\lvert{\underline{y}}\rangle\lvert
P_{y_{1}}a_{1}Hx^{-\chi_{\underline{y}}(1)}\rangle\ldots\lvert
P_{y_{S}}a_{S}Hx^{-\chi_{\underline{y}}(S)}\rangle.$

Consider the term of $\lvert\psi(x)\rangle$ corresponding to any
${\underline{y}}$. As $J({\underline{y}})$ is non-empty, we have that for
$x_{1},x_{2}$ not in the same left coset of $LH$, the appropriate terms of
$\lvert\psi(x_{i})\rangle$ are orthogonal. As $\lvert\underline{y}\rangle$
also appears in the corresponding term, we have that
$\lvert\psi(x_{i})\rangle$ are also orthogonal. On the other hand, if
$x_{1},x_{2}$ are in the same left coset of $H$ then these states are equal
term by term. Finally, for $x\in L$, by (2, the term for ${\underline{y}}$
only gets a phase change by $\prod_{j\in
J}({\underline{y}})\omega^{-(y_{j},x)}=\omega^{\sum_{j\in
J({\underline{y}})}(y_{j},x)}=\omega^{0}=1$ by the choice of
$J({\underline{y}})$. It follows that if $x_{1}$ and $x_{2}$ are in the same
left coset of $LH$, $\lvert\phi(x_{1})\rangle=\lvert\phi(x_{2}\rangle$. Thus
our state is a purification of $\Xi_{G,LH}$. As this holds for any fixed
$S$-tuple of left cosets of $H$, by linearity we also obtain a purification of
$\Xi_{G,LH}$ if we apply the procedure to copies of a purification of
$\Xi_{G,H}$. We obtained the following.

######  Lemma 2.

Assume that we have an exact quantum procedure (e.g., a deterministic
polynomial time algorithm) that, given any sequence $y_{1},\ldots,y_{S}$ of
$S=S(p,n)$ elements of ${\mathbb{Z}}_{p}^{n}$, in time $T(p,n)\geq S(p,n)$
finds a non-empty subset of $\\{1,\ldots,S\\}$ such that $\sum_{j\in
J}y_{j}=0$. Then we have an exact quantum procedure using $n$ quantum Fourier
transforms modulo $p$ that converts $S(p,n)$ copies of (a purification) of
$\Xi_{G,H}$ to a copy of (a purification of) $\Xi_{G/L,HL/L}$ where $L$ is
subgroup of the center of $G$ isomorphic to ${\mathbb{Z}}_{p}^{n}$ in time
$T(p,n)\operatorname{\mathrm{poly}}(\log{\lvert G\rvert})$.

Using the lemma in iteration and applying the exact abelian hidden subgroup
algorithm of [II22], we can derive the following.

######  Proposition 2.

Let $G$ be a semi-elementary black-box group with unique encoding of order
$p^{n}$. Assume that the quantum Fourier transform modulo $p$ and its inverse
can be implemented by an efficient exact algorithm and that, like in Lemma 2,
we have an exact method to find zero sum subsequences of sequences of $S(p,n)$
elements of ${\mathbb{Z}}_{p}^{n}$ in time $T(p,n)\geq S(p,n)$. Then the
problem HSMC can be solved by an exact quantum algorithm that uses
$\operatorname{\mathrm{poly}}(T(p,n)^{O(c)}\ell)$ elementary operations,
$\operatorname{\mathrm{poly}}(T(p,n)^{O(c)}\log{\lvert G\rvert})$ applications
of the group oracle, calls to the oracle computing the purification of the
subgroup state; and the inverses of these. (The elements of $G$ are assumed to
be uniquely encoded by strings of length $\ell$.)

###### Proof.

We compute the lower central series $G=G_{0}>G_{1}>\ldots>G_{c}=\\{1\\}$ using
the method presented in Subsection 2.2. As $G/G^{\prime}$ is elementary
abelian, so are the factors $G_{i-1}/G_{i}$ ($i=1,\ldots,c$). This is because
the factor groups $G_{i-1}/G_{i}$ are homomorphic images of tensor powers (as
${\mathbb{Z}}$-modules) of the $G/G^{\prime}$, see Theorem 5.2.5 of [Rob95].
Also, isomorphisms of $G_{i-1}/G_{i}$ with ${\mathbb{Z}}_{p}^{n_{i}}$ can be
efficiently computed using the method of [II22]. Iteration of Lemma 2 gives a
procedure to convert $\prod_{i=2}^{c}S(n_{i})$ copies of a purification of
$\Xi_{G,H}$ to a copy of a purification of
$\Xi_{G/G^{\prime},HG^{\prime}/G^{\prime}}$. The composition of instances of
the original subgroup state creating procedure (the calls to the oracle) with
the conversion gives a procedure for creating a purification of
$\Xi_{G/G^{\prime},HG^{\prime}/G^{\prime}}$. We can use this as the oracle
input for the exact hidden subgroup algorithm of [II22] in
${\mathbb{Z}}_{p}^{n_{1}}$. For $i=1,\ldots,c$, we have $S(p,n_{i})\leq
S(p,n)$ and $T(p,n_{i})\leq T(p,n)$ because ${\mathbb{Z}}_{p}^{n_{i}}$ can be
embedded in ${\mathbb{Z}}_{p}^{n}$ as a subgroup. ∎

In the non-exact setting, essentially the same proof gives the following.

######  Proposition 3.

Let $G$ be a semi-elementary black-box group with unique encoding of order
$p^{n}$. Assume that there exists a quantum (or a randomized) algorithm that
finds zero sum subsequences of sequences of $S(p,n)$ elements of
${\mathbb{Z}}_{p^{n}}$ in time $T(p,n)\geq S(p,n)$ with high probability. Then
the problem HSMC can be solved by a quantum algorithm that uses
$\operatorname{\mathrm{poly}}(T(p,n)^{O(c)}\ell)$ elementary operations,
$\operatorname{\mathrm{poly}}(T(p,n)^{O(c)}\log{\lvert G\rvert})$ applications
of the group oracle and calls to the oracle computing the purification of the
subgroup state.

##  5 Zero sum subsequences in ${\mathbb{Z}}_{p}^{n}$

In this section, we assume that our input is a sequence of vectors from
${\mathbb{Z}}_{p}^{n}$. We also assume that $p$ is an odd prime as for $p=2$ a
zero sum subsequence can be obtained from $n+1$ vectors in the form of a zero
linear combination. As subsequences can be represented as subsets of the index
set, it will not be too misleading to use the term (sub)set for a
(sub)sequence. Our strategy will be finding $p$ pairwise disjoint subsets of
input vectors having equal sums. We will achieve this goal by designing a
method for finding a nontrivial pair of subsets having equal sum and then,
like in [IS17], applying the algorithm recursively to obtain $4$, $8$, $16$,
etc. disjoint subsets with equal sum.

Note that a pair of disjoint subsets with equal sum can be interpreted as a
representation of the zero vector by a linear combination of the input vectors
with nonzero coefficients $1$ or $-1$ only. Based on this, it will be
convenient to use the term signed subsets and signed subset sums. A signed
subset of a set $S$ of vectors is formally a function from $S$ to the set
$\\{0,1,-1\\}$. The support of such a signed subset is the set of elements on
which the function takes nonzero values. With some sloppiness, we use the term
signed subset sum to refer both to the signed subset and to the value of the
signed sum. (Technically, a signed subset sum could be a data structure
consisting of the description of the signed subset and the value.) We call two
or more subset sums disjoint if their supports are pairwise disjoint. Based on
the observation that a signed subset sum of vectors that are results of
pairwise disjoint subset sums is again a signed subset sum of the original
vectors, one can build signed subset sums hierarchically from smaller disjoint
signed subset sums. The trivial subset sum corresponds to the empty set with
the zero vector as value.

A linear relation (or just relation for short) among a collection of vectors
is an array of coefficients such that the corresponding linear combination is
the zero vector. It is often useful to omit the vectors to which coefficient
zero are assigned. By taking the signed subsets of the vectors having the same
or the opposite coefficient in a linear relation, we obtain a linear relation
among pairwise disjoint signed subset sums in which the coefficients are form
$\\{1,\ldots,\frac{p-1}{2}\\}$ and each coefficient appears at most once. We
call such a relation of signed subset sums standard.

We shall build standard linear relations among signed subset sums with smaller
and smaller coefficients (among increasingly larger subset sums). The key idea
is constructing first $\frac{(p-1)^{2}}{4}$ pairwise signed subset sums
arranged in a square matrix having a relation in each row as well as in each
column and subtracting the sum of higher half of ”horizontal” relations from
the sum of the higher half of the ”vertical” relations to obtain a relation
with coefficients between $1$ and $\frac{p-1}{4}$, and iterating the
construction. We give the details in the following lemma and its proof. (We
present a version that even saves up maintaining the first half of vertical
relations.)

######  Lemma 3.

Let $d$ be a positive integer. Assume that there is a deterministic procedure
$\cal A$ that, given $h(d,n)$ vectors from ${\mathbb{Z}}_{p}^{n}$, in time
$\operatorname{\mathrm{poly}}(h(d,n)\log p)$ finds $d$ pairwise disjoint
signed subset sums $v_{1},\ldots,v_{d}$ of the input vectors, not all empty,
such that $\sum_{i=1}^{d}iv_{i}=0$. Then there also exists a deterministic
procedure that, given $h(d,n)h(d,\lceil d/2\rceil n)$ vectors, in time
$\operatorname{\mathrm{poly}}(h(d,n)h(d,\lceil d/2\rceil n)\log p)$ finds
pairwise disjoint signed subset sums
$w^{\prime}_{1},\ldots,w^{\prime}_{\lfloor d/2\rfloor}$, not all empty, such
that $\sum_{i=1}^{\lfloor d/2\rfloor}iw^{\prime}_{i}=0$.

###### Proof.

We divide the input set into $h(d,\lceil d/2\rceil n)$ pairwise disjoint parts
of size $h(d,n)$. We apply procedure $\cal A$ within each part. This way for
each $k=1,\ldots,h(d,\lceil d/2\rceil n)$, we get $d$ pairwise disjoint subset
sums $u_{k1},\ldots,u_{kd}$, not all empty, such that
$\sum_{j=1}^{d}ju_{kj}=0$. For each $k$ we consider the concatenation $u_{k}$
of the vectors $u_{kj}$ ($j=\lfloor d/2\rfloor+1,\ldots,d$). These are vectors
of dimension $\lceil d/2\rceil n$. We apply procedure $\cal A$ to find
pairwise disjoint signed subsets $M_{1},\ldots,M_{d}$ such that
$\sum_{i=1}^{d}iu_{i}^{\prime}=0$, where $u_{i}^{\prime}$ is the signed sum of
the $u_{k}$s corresponding to the signed subset $M_{i}$. Now for each $1\leq
i\leq d$, $u_{i}^{\prime}$ is the concatenation of vectors $w_{ij}$
($j=\lfloor d/2\rfloor+1,\ldots,d$). Here, for $1\leq i,j\leq d$, $w_{ij}$
stands for the signed subset sum obtained by joining the signed subset sums
$u_{kj}$ according to the signed subset $M_{i}$. The signed subset sums
$w_{ij}$ are pairwise disjoint, not all of them are empty and they satisfy the
relations

$\sum_{i=1}^{d}iw_{ij}=0\;\;(j=\lfloor d/2\rfloor+1,\ldots,d)$

and

$\sum_{j=1}^{d}jw_{ij}=0\;\;(i=1,\ldots,d).$

We subtract the sum of the last $\lceil d/2\rceil$ (”horizontal”) relations of
the second kind from the sum the $\lceil d/2\rceil$ (”vertical”) relations of
the first kind and obtain the relation

$\sum_{i=1}^{\lfloor d/2\rfloor}\sum_{j=\lfloor
d/2\rfloor+1}^{d}iw_{ij}-\sum_{i=\lfloor d/2\rfloor+1}^{d}\sum_{j=1}^{\lfloor
d/2\rfloor}jw_{ij}+\sum_{i,j=\lfloor d/2\rfloor+1}^{d}(i-j)w_{ij}=0.$

Notice that for $\lfloor d/2\rfloor+1\leq i,j\leq d$, we have
$|i-j|\leq\lfloor d/2\rfloor$. Therefore, by flipping signs where appropriate
and then joining the signed subsets with equal coefficients, we obtain
pairwise disjoint subset sums $w^{\prime}_{1},\ldots,w^{\prime}_{\lfloor
d/2\rfloor}$ with $\sum_{i=1}^{\lfloor d/2\rfloor}iw^{\prime}_{i}=0$.

The subset sums $w_{i}^{\prime}$ can all be empty only if each $w_{ij}$ is
empty when $i\neq j$ and at least one of $i$ and $j$ is greater than $\lfloor
d/2\rfloor$. Assume that this is the case. Then, if there is an index
$i>\lfloor d/2\rfloor$ such that $w_{ii}$ is non-empty then $w_{ii}$ must be
itself a nontrivial zero subset sum and gives a one-term solution. Otherwise
not all $w_{ij}$ are empty for $i,j\leq\lfloor d/2\rfloor$ and
$\sum_{i,j=1}^{\lfloor d/2\rfloor}iw_{ij}=0$. ∎

Iterated application of the method of Lemma 3 gives the following result.

######  Proposition 4.

Given $S_{\pm}(p,n)=p^{O(p\log p)}n^{O(p)}$ vectors from
${\mathbb{Z}}_{p}^{n}$, a nontrivial signed subset sum representing the zero
vector can be found in deterministic time
$\operatorname{\mathrm{poly}}(S_{\pm}(p,n))$.

###### Proof.

Put $d_{0}=\frac{p-1}{2}$, $h_{0}(n)=n+1$ and define $d_{i}=\lfloor
d_{i-1}/2\rfloor$ and $h_{i}(n)=h_{i-1}(n)h_{i-1}(\lceil d_{i-1}/2\rceil n)$
recursively for $i=1,\ldots,\lfloor\log d_{0}\rfloor$. As among any
$h_{0}(n)=n+1$ vectors from ${\mathbb{Z}}_{p}^{n}$ a nontrivial linear
relation can be found in time $\operatorname{\mathrm{poly}}(n\log p)$,
recursive applications of Lemma 3 gives that among $h_{\lfloor\log
d_{0}\rfloor}(n)$ vectors a single nontrivial signed subset sum (that is, a
linear relation with nonzero coefficients $\pm 1$ only) can be found in time
$\operatorname{\mathrm{poly}}(h_{\lfloor\log d_{0}\rfloor}(n)\log p)$. We show
by induction that

$h_{i}(n)\leq\left(\prod_{j=0}^{i-1}\lceil
d_{j}/2\rceil\right)^{2^{i-1}}(n+1)^{2^{i}}.$ (3)

For $i=0$, both sides are equal to $n+1$. Assume that the inequality holds for
$0\leq i<\lfloor\log d_{0}\rfloor$. Then we also have

$h_{i}(\lceil d_{i}/2\rceil n)\leq\left(\prod_{j=0}^{i-1}\lceil
d_{j}/2\rceil\right)^{2^{i-1}}(\lceil d_{i}/2\rceil n+1)^{2^{i}}.$

Using $\lceil d_{i}/2\rceil n+1\leq\lceil d_{i}/2\rceil(n+1)$, we obtain

$h_{i}(\lceil d_{i}/2\rceil n)\leq\lceil
d_{i}/2\rceil^{2^{i-1}}\left(\prod_{j=0}^{i}\lceil
d_{j}/2\rceil\right)^{2^{i-1}}(n+1)^{2^{i}}.$ (4)

Multiplying inequalities (3) and (4) and using
$h_{i+1}(n)=h_{i}(n)h_{i}(\lceil d_{i}/2\rceil n)$, we obtain

$h_{i+1}(n)\leq\left(\prod_{j=0}^{i}\lceil
d_{j}/2\rceil\right)^{2^{i}}(n+1)^{2^{i+1}},$

which is inequality (3) for $i+1$ in place of $i$. Using $d_{j}\leq
d_{0}/2^{j}\leq d_{0}=\frac{p-1}{2}$, inequalities (3) for $i=\lfloor\log
d_{0}\rfloor$ gives

$h_{\lfloor\log
d_{0}\rfloor}\leq\left(\prod_{j=0}^{\left\lceil\log\frac{p-1}{2}\right\rceil-1}\left\lceil\frac{p-1}{4}\right\rceil\right)^{2^{\left\lceil\log\frac{p-1}{2}\right\rceil-1}}(n+1)^{2^{\left\lceil\log\frac{p-1}{2}\right\rceil}}$

$=\left\lceil\frac{p-1}{4}\right\rceil^{\left\lceil\frac{p-1}{4}\right\rceil\left\lceil\log\frac{p-1}{2}\right\rceil}(n+1)^{\left\lceil\frac{p-1}{2}\right\rceil}.$

Therefore, we have

$h_{\lfloor\log d_{0}\rfloor}(n)=p^{O(p\log p)}n^{O(p)}.$

∎

We interpret a non-empty zero sum signed subset as a non-trivial collision
between two disjoint subset sums. (Non-trivial means that at most one of the
subsets can be empty.) We use the short term collision for such a pair. We
have the following.

######  Proposition 5.

Suppose that there is an algorithm $\cal B$ that, given a set of vectors from
${\mathbb{Z}}_{p}^{n}$ of size $S_{\pm}(p,n)$ finds a collision. Then there is
a deterministic procedure that, given ${S_{\pm}(p,n)}^{\lceil\log p\rceil}$
vectors, finds a nontrivial zero sum subset using less than
$S_{\pm}^{\lceil\log p\rceil}$ applications of algorithm $\cal B$ and
$\operatorname{\mathrm{poly}}((S_{\pm}(p,n))^{\lceil\log p\rceil})$ other
operations.

###### Proof.

Put $S=S_{\pm}(p,n)$ and $\ell=\lceil\log p\rceil$. We start with finding a
collision $(H_{1}^{+},H_{1}^{-})$ among the first $S$ vectors with common sum
$w_{1}$ using algorithm $\cal B$. We continue with the next $S$ input vectors
and find a collision $(H_{2}^{+},H_{2}^{-})$ with sum $w_{2}$, and so on. We
then take the first $S$ subset sums $w_{1},\ldots,w_{S}$ and find a pair of
disjoint subsets $(K^{+},K^{-})$ of $\\{1,\ldots,S\\}$, not both empty, such
that $\sum_{i\in K^{+}}w_{i}=\sum_{i\in K^{-}}w_{i}=w$. The four subsets
$L^{++}=\bigcup_{i\in K^{+}}H_{i}^{+}$, $L^{+-}=\bigcup_{i\in
K^{+}}H_{i}^{-}$, $L^{-+}=\bigcup_{i\in K^{-}}H_{i}^{+}$, and
$L^{--}=\bigcup_{i\in K^{-}}H_{i}^{-}$ of input vectors are pairwise disjoint,
not all empty and have common sum $w$. Iterating this we end up with at least
$p$ pairwise disjoint subsets (not all empty) with equal sum. If one of these
sets is empty then the common sum is zero and we can take any of the non-empty
subsets. Otherwise the union of the first $p$ of the subsets has zero sum. The
total number of applications of the collision finding algorithm $\cal B$ is
$S^{\ell-1}+\ldots+S+1<S^{\ell}$. ∎

Propositions 4 and 5, together with the remark on the case $p=2$ immediately
give the following.

######  Theorem 2.

There is a deterministic algorithm that, given a sequence of
$S(p,n)=p^{O(p\log^{2}p)}n^{O(p\log p)}$ vectors from ${\mathbb{Z}}_{p}^{n}$,
finds a non-trivial zero sum subsequence in time
$\operatorname{\mathrm{poly}}(S(p,n))$.

We remark that in [IS17], an algorithm for a more general task is given. This
task is finding a nontrivial representation of the zero vector as a linear
combination of the input vectors with $d$th power coefficients. This includes
our problem as the special case $d=p-1$. The algorithm of [IS17] for $d=p-1$
would give $S(p,n)=p^{O(p^{2}\log p)}n^{O(p\log p)}$, a parameter somewhat
worse than that we have in Theorem 2, though would be still polynomial in $n$
for $p=O(1)$. The method of [IS17] for finding a collision is more complicated
than the present one: it is based on collecting relations organized in a
$d$-dimensional hypercube rather than a square. (The method of doubling
collisions is essentially identical with that described here in Proposition
5.)

##  6 Concluding remarks

We have shown that the hidden subgroup problem in a nilpotent group $G$ of
class bounded by a constant can be solved in polynomial time by an exact
quantum algorithm provided that there is a polynomial time (that is, time
$\operatorname{\mathrm{poly}}(n\log p)$) exact method that finds zero sum
subsequences in sequences consisting of polynomially many elements of
${\mathbb{Z}}_{p}^{n}$ for prime divisors $p$ of $\lvert G\rvert$. We have
such a method for $p=O(1)$. By Olson’s theorem [Ols69], the shortest length
for which a not necessarily polynomial time zero sum subsequence finding
algorithm exists is around $np$.

We propose the question of existence of a
$\operatorname{\mathrm{poly}}(np)$-time algorithm for finding zero sum
subsequences from sequences of length $(np)^{d}$ for a sufficiently large
constant $d$ as a problem for further research. A positive answer would imply
existence of an exact polynomial time quantum algorithm for the case when
$\lvert G\rvert$ is smooth, that is, the prime factors of $\lvert G\rvert$ are
of size bounded by a polynomial in $\log\lvert G\rvert$. Even a non-exact
method (e.g., a randomized algorithm) would be of great interest as, by
Proposition 3, it would give a new result in the non-exact setting: existence
of an efficient ”probabilistic” quantum hidden subgroup algorithm for
nilpotent groups of smooth order having $O(1)$-bounded nilpotency class. Even
somewhat worse results would potentially lead to quantum hidden subgroup
algorithms faster than the known ones.

For the purposes of ”probabilistic” quantum hidden subgroup algorithms even a
method that finds a zero sum subsequence ”on average”, that is for at least a
$1/\operatorname{\mathrm{poly}}(np)$ proportion of the possible sequences
would be sufficient. However, as the following simple worst-case to average-
case reduction shows, at least in the randomized setting, the gain cannot be
better than polynomial. Assume that the classical randomized algorithm $\cal
A$ finds in time $T=T(p,n)$ with probability at least $\delta$ a subsequence
of a random sequence of length $S=S(p,n)$ of vectors from
${\mathbb{Z}}_{p}^{n}$. Here, probability is taken for the uniform
distribution of the array of the vectors together with the random bits of
$\cal A$. Then we can do the following. We start with an arbitrary sequence of
$\frac{1}{\delta}\cdot S^{2}$ input vectors, we draw $\frac{1}{\delta}\cdot
S^{2}$ uniformly random vectors, one for each input vector. Then we divide the
input sequence into groups of length $S$ and to each input vector we add the
corresponding random vector. Within each group, we apply procedure $\cal A$.
As the sums are random vectors, in each group, procedure $\cal A$ succeeds
with probability at least $\delta$ and, with probability at least
$\frac{1}{2}$, $\cal A$ will succeed in at least $S$ groups. If this is the
case then we choose $S$ ”lucky” groups, in each group take the sum of the
random vectors corresponding to the members of the zero sum subsequences. We
apply algorithm $\cal A$ for these $S$ sums. It finds a nontrivial zero sum
subsequence with probability at least $\delta$. Finally, we take the union of
the corresponding subsequences. This way we obtain a procedure that finds a
nontrivial zero sum subsequence of every sequence of length
$\frac{1}{\delta}\cdot S^{2}$ in time
$\operatorname{\mathrm{poly}}(T+\frac{1}{\delta}\cdot ST)$ with probability at
least $\delta/2$.

## References

  * [AMR07] G. Alagic, C. Moore, and A. Russell.  Quantum algorithms for simon’s problem over general groups.  In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1217–1224, 2007.
  * [AR17] G. Alagic and A. Russell.  Quantum-secure symmetric-key cryptography based on hidden shifts.  In Advances in Cryptology–EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30–May 4, 2017, Proceedings, Part III, pages 65–93. Springer, 2017.
  * [BH97] G. Brassard and P. Høyer.  An exact quantum polynomial-time algorithm for Simon’s problem.  In ISTCS 97, pages 12–23, 1997.
  * [BL21] E. Bae and S. Lee.  Quantum algorithm based on the $\varepsilon$-random linear disequations for the continuous hidden shift problem.  Quantum Inf. Process., 20(10):347, 2021.
  * [BNP18] X. Bonnetain and M. Naya-Plasencia.  Hidden shift quantum cryptanalysis and implications.  In Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I 24, pages 560–592. Springer, 2018.
  * [Bon21] X. Bonnetain.  Tight bounds for Simon’s algorithm.  In LATINCRYPT 2021, pages 2–23, 2021.
  * [BV97] E. Bernstein and U. Vazirani.  Quantum complexity theory.  SIAM J. Comput., 26:1411–1473, 1997.
  * [CM23] W. Castryck and N. Vander Meeren.  Two remarks on the vectorization problem.  In Progress in Cryptology–INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings, pages 658–678. Springer, 2023.
  * [CQ18] G. Cai and D. Qiu.  Optimal separation in exact query complexities for Simon’s problem.  J. Comput. Syst. Sci., 97:83–93, 2018.
  * [DHIS14] T. Decker, P. Høyer, G. Ivanyos, and M. Santha.  Polynomial time quantum algorithms for certain bivariate hidden polynomial problems.  Quantum Inf. Comput., 14(9-10):790–806, 2014.
  * [EHK04] M. Ettinger, P. Høyer, and E. Knill.  The quantum query complexity of the hidden subgroup problem is polynomial.  Inf. Process. Lett., 91:43–48, 2004.
  * [FIM+14] K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen.  Hidden translation and translating coset in quantum computing.  SIAM J. Comput., 43(1):1–24, 2014.  Preliminary version in STOC 2003.
  * [HK18] K. Horan and D. Kahrobaei.  The hidden subgroup problem and post-quantum group-based cryptography.  In Mathematical Software–ICMS 2018: 6th International Conference, South Bend, IN, USA, July 24-27, 2018, Proceedings 6, pages 218–226. Springer, 2018.
  * [II22] M. Imran and G. Ivanyos.  An exact quantum hidden subgroup algorithm and applications to solvable groups.  Quantum Inf. Comput., 22(9&10):770–789, 2022.
  * [IS17] G. Ivanyos and M. Santha.  Solving systems of diagonal polynomial equations over finite fields.  Theor. Comput. Sci., 657:73–85, 2017.
  * [ISS12] G. Ivanyos, L. Sanselme, and M. Santha.  An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups.  Algorithmica, 62(1-2):480–498, 2012.
  * [KL90] W. M. Kantor and E. M. Luks.  Computing in quotient groups.  In STOC 1990, pages 524–534, 1990.
  * [Kup05] G. Kuperberg.  A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.  SIAM J. Comput., 35(1):170–188, 2005.
  * [LK07a] S. Jr. Lomonaco and L. H. Kauffman.  Is grover’s algorithm a quantum hidden subgroup algorithm?  Quantum Inf. Process., 6:461–476, 2007.
  * [LK07b] S. Jr. Lomonaco and L. H. Kauffman.  Quantum hidden subgroup algorithms: An algorithmic toolkit.  In Mathematics of Quantum Computation and Quantum Technology, pages 21–64. Chapman and Hall/CRC, New York, 2007.
  * [Lom04] C. Lomont.  The hidden subgroup problem-review and open problems.  Technical Report quant-ph/0411037, arXiv, 2004.
  * [MZ03] M. Mosca and C. Zalka.  Exact quantum Fourier transforms and discrete logarithm algorithms.  Int. J. Quantum Inf., 02:91–100, 2003.
  * [NC10] M. A. Nielsen and I. K. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, Cambridge, 10th anniversary edition, 2010\.
  * [NO02] H. Nishimura and M. Ozawa.  Computational complexity of uniform quantum circuit families and quantum turing machines.  Theor. Comput. Sci., 276:147–181, 2002.
  * [NO05] H. Nishimura and M. Ozawa.  Uniformity of quantum circuit families for error-free algorithms.  Theor. Comput. Sci., 332:487–496, 2005.
  * [NO09] H. Nishimura and M. Ozawa.  Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families.  Quantum Inf. Process., 8:13–24, 2009.
  * [Ols69] J. E. Olson.  A combinatorial problem on finite abelian groups, i.  J. Number Theory, 1(1):8–10, 1969.
  * [Rob95] D. Robinson.  A Course in the Theory of Groups.  Springer, Urbana, Illionis, 2nd edition, 1995.
  * [Wan10] F. Wang.  The hidden subgroup problem.  Technical Report quant-ph/1008.0010, arXiv, 2010.
  * [Wat01] J. Watrous.  Quantum algorithms for solvable groups.  In STOC 2001, pages 60–67, 2001.
  * [WQT+22] Z. Wu, D. Qiu, J. Tan, H. Li, and G. Cai.  Quantum and classical query complexities for generalized Simon’s problem.  Theor. Comput. Sci., 924:171–186, 2022.