We present a polynomial time exact quantum algorithm for the hidden subgroup problem in
Zmkn. The algorithm uses the quantum Fourier transform modulo
m and does not require factorization of
m. For smooth
m, i.e., when the prime factors of
m are of size
(logm)O(1), the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general
m, the algorithm of Mosca and Zalka is available. Even for
m=3 and
k=1 our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as
m. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Zn p, whenever p is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group G is reducible to instances of Translating Coset in G/N and N, for appropriate normal subgroups N of G. Our self-reducibility framework, combined with Kuperberg’s subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.
Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively.
In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form
G=A⋊φZpk, with
A finite Abelian,
p prime,
k∈N and the action of
Zpk is generated by the scalar automorphism
a↦μa, for some
μ∈ZExp(A)×, where
Exp(A) is the exponent of
A. Our algorithm is efficient when
A has bounded generator rank and
Exp(A)/p=polylog(∣G∣). This includes the case
A=ZN for
N∈N and
k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and
A=Zqr with
q prime and
r∈N studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in
Zpn, whenever
p is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group
G is reducible to instances of Translating Coset in
G/N and
N, for appropriate normal subgroups
N of
G. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.
In this paper we extend the algorithm for extraspecial groups in \cite{iss07}, and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a
p-group of exponent
p and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.
The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group
Zpr⋊Zqs, when $p^r/q= \up{poly}(\log p^r)$, where
p,
q are any odd prime numbers and
r,s are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.