Quantum Coset Multiplication and the Hidden Subgroup Problem in Dihedral Groups Dp - Sarmento, João R.; Zatesko, Leandro M.; Costa, Abner F. B. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
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 D p when p is prime.