Abstract
In the field of quantum computing, the hidden subgroup problem (HSP) for finitely generated Abelian groups has been effectively solved, while research on non-Abelian groups continues to explore quantum computational capabilities. The dihedral hidden subgroup problem (DHSP), critical for cryptographic security, has attracted significant attention. This paper presents a quantum–classical hybrid scheme that replaces the iterative step in DHSP algorithms. The method generalizes the semiclassical quantum Fourier transform (QFT) to the DHSP context, which avoids serial processing limitations and reduces the complexity of modifying sampling circuits. By decoupling sampling from iteration, the proposed scheme enhances overall algorithmic efficiency.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
No datasets were generated or analyzed during the current study.
References
Shor, P W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, (1994)
Jozsa, R.: Quantum algorithms and the fourier transform. Proc. R. Soc. London Ser. Mathe. Phys. Eng. Sci. 454, 323–337 (1997)
Ettinger, M., Høyer, P.: On quantum algorithms for noncommutative hidden subgroups. Adv. Appl. Math. 25(3), 239–251 (2000)
Ettinger, M., Høyer, P.: A quantum observable for the graph isomorphism problem. 1999 arXiv: 9901029 [quant-ph]
Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738–760 (2004)
Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005)
Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. (2004) arXiv: 0406151 [quant-ph]
Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Theory of Quantum Computation, Communication, and Cryptography, pp. 20–34, (2011)
Childs, A., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1–29 (2013)
Roetteler, M.: Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups. In: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), vol. 61, pp. 8:1–8:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, (2016)
Dam, D.-T., Tran, T.-H., Hoang, V.-P., Pham, C.-K., Hoang, T.-T.: A survey of post-quantum cryptography: start of a new race. Cryptography 7, 40 (2023)
Yang, P., Zhang, X., Lin, S.: Distributed quantum algorithm for the dihedral hidden subgroup problem. (2025) arXiv: 2503.06478 [quant-ph]
Brakerski, Z., Kirshanova, E., Stehlé, D., Wen, W.: Learning with errors and extrapolated dihedral cosets. In: International Conference on Theory and Practice of Public Key Cryptography, pp. 702–727, (2017)
Gábor Ivanyos, A., Prakash, and M Santha. On learning linear functions from subset and its applications in quantum computing. In: 26th Annual European Symposium on Algorithms (ESA,: number 112, pages 66:1–66:14, p. 2018. Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl (2018)
Chen, Y., Liu, Q., Zhandry, M.: Quantum algorithms for variants of average-case lattice problems via filtering. In: Advances in Cryptology–EUROCRYPT 2022, pp. 372–401, Springer International Publishing, Cham (2022)
Yan, X., Lize, G., Suo, J., Wang, L.: Leveraging the hardness of dihedral coset problem for quantum cryptography. Quantum Inf. Process. 21, 308 (2022)
Doliskani, J.: Efficient quantum public-key encryption from learning with errors. (2021)arXiv: 2105.12790 [quant-ph]
Griffiths, R.B., Niu, C.-S.: Semiclassical fourier transform for quantum computation. Phys. Rev. Lett. 76(17), 3228–3231 (1996)
Beauregard, S.: Circuit for shor’s algorithm using 2n+3 qubits. Quantum Info. Comput. 3(2), 175–185 (2003)
Gidney, C.: Factoring with n+2 clean qubits and n-1 dirty qubits. (2017) arXiv: 1706.07884 [quant-ph]
Häner, T., Roetteler, M., Svore, K.M.: Factoring using 2n + 2 qubits with toffoli based modular multiplication. Quantum Info. Comput. 17(7–8), 673–684 (2017)
Nam, Y S., Su, Y., Maslov, D L.: Approximate quantum fourier transform with o(n log(n)) t gates. npj Quantum Information, 6:26, (2018)
Acknowledgements
Acknowledgements are not compulsory. Where included they should be brief. Grant or contribution numbers may be acknowledged.
Author information
Authors and Affiliations
Contributions
The first author designed the quantum circuits and completed the theoretical proofs. The second author reviewed and refined these proofs while also revising the manuscript structure. All authors collectively contributed to revising the manuscript.
Corresponding authors
Ethics declarations
Code availability
The quantum circuits for dihedral coset separation and the post-processing code are available at: https://github.com/cuifx/HSP-DHSP
Conflict of interest
The authors declare no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Fuxin, C., Bei, W., Menghan, D. et al. Improvements to the DHSP quantum solving algorithm. Quantum Inf Process 25, 130 (2026). https://doi.org/10.1007/s11128-026-05145-w
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s11128-026-05145-w