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.
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).
The Hidden Subgroup Problem (HSP) generalises and is related to important computational problems, such as Integer Factorisation. A major breakthrough in the study of quantum algorithms is Shor’s approach to solving HSP for abelian groups. Recently, one of the authors of this paper has proposed a quantum algorithm for coset multiplication, which seems to be promising for the HSP in some group classes, such as symmetric and alternating groups. We extend the result on symmetric groups to dihedral groups Dp when p is prime.
The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.
The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.