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).
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups
ZN⋊Zqs where
N is an integer with a special prime factorization,
q prime number and
s any positive integer.
We provide a survey on the Hidden Subgroup Problem (HSP), which plays an important role in studying the security of public-key cryptosystems. We first review the abelian case, where Kitaev's algorithm yields an efficient quantum solution to the HSP, recalling how classical problems (such as order finding, integer factorization, and discrete logarithm) can be formulated as abelian HSP instances. We then examine the current state of the art for non-abelian HSP, where no general efficient quantum solution is known, focusing on some relevant groups including dihedral group (connected to the shortest vector problem), symmetric groups (connected to the graph isomorphism problem), and semidirect product constructions (connected, in a special case, to the code equivalence problem). We also describe the main techniques for addressing the HSP in non-abelian cases, namely Fourier sampling and the black-box approach. Throughout the paper, we highlight the mathematical notions required and exploited in this context, providing a cryptography-oriented perspective.
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.