Quantum Coset Multiplication and the Hidden Subgroup Problem in Dihedral Groups Dp

• João R. Sarmento UTFPR
• Leandro M. Zatesko UTFPR
• Abner F. B. Costa UFPR

DOI: https://doi.org/10.5753/etc.2025.9189

Resumo

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.

Referências

Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Princeton.

Conrad, K. (2013). Dihedral groups II. course handout.

Costa, A. F., Hepp, H., da Silva, M. V., and Zatesko, L. M. (2023). The hidden subgroup problem and non-interactive perfect zero-knowledge proofs. In Encontro de Teoria da Computação (ETC), pages 99–103. SBC.

Costa, A. F. B. (2024). Um algoritmo quântico para casos não abelianos de hsp. Dissertação de mestrado, Universidade Federal do Paraná.

Ettinger, M., Høyer, P., and Knill, E. (2004). The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43–48.

Gavinsky, D. (2004). Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Information & Computation, 4(3):229–235.

Gonçalves, D. N., Fernandes, T. D., and Cosme, C. (2017). An efficient quantum algorithm for the hidden subgroup problem over some non-abelian groups. TEMA (São Carlos), 18(2):215–223.

Grigni, M., Schulman, L., Vazirani, M., and Vazirani, U. (2001). Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 68–74.

Hallgren, S., Russell, A., and Ta-Shma, A. (2000). Normal subgroup reconstruction and quantum computation using group representations. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 627–635.

Hoffstein, J., Pipher, J., and Silverman, J. H. (1998). Ntru: A ring-based public key cryptosystem. In International algorithmic number theory symposium, pages 267–288. Springer.

Jozsa, R. (2001). Quantum factoring, discrete logarithms, and the hidden subgroup problem. Computing in Science & Engineering, 3(2):34–43.

Kitaev, A. Y. (1995). Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026.

Kuperberg, G. (2003). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arXiv preprint quant-ph/0302112.

Moore, C., Russell, A., and Schulman, L. J. (2008). The symmetric group defies strong fourier sampling. SIAM Journal on Computing, 37(6):1842–1864.

Nielsen, M. A. and Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press, 1 edition.

Regev, O. (2002). Quantum computation and lattice problems. In Proc. 43rd Annual IEEE Symposium on Foundations of Comput. Sci., pages 520–529. IEEE.

Regev, O. (2004). A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv preprint quant-ph/0406151.

Rotman, J. J. (2005). A First Course in Abstract Algebra. Pearson, 3 edition.

Sdroievski, N. M., da Silva, M. V., and Vignatti, A. L. (2019). The hidden subgroup problem and MKTP. Theoretical Computer Science, 795:204–212.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE.