{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T07:48:56Z","timestamp":1775288936316,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:00:00Z","timestamp":1775260800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:00:00Z","timestamp":1775260800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-026-05145-w","type":"journal-article","created":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:52:27Z","timestamp":1775285547000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improvements to the DHSP quantum solving algorithm"],"prefix":"10.1007","volume":"25","author":[{"given":"Cui","family":"Fuxin","sequence":"first","affiliation":[]},{"given":"Wang","family":"Bei","sequence":"additional","affiliation":[]},{"given":"Dou","family":"Menghan","sequence":"additional","affiliation":[]},{"given":"Li","family":"Ye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,4]]},"reference":[{"key":"5145_CR1","doi-asserted-by":"crossref","unstructured":"Shor, P\u00a0W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134, (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"5145_CR2","first-page":"323","volume":"454","author":"R Jozsa","year":"1997","unstructured":"Jozsa, R.: Quantum algorithms and the fourier transform. Proc. R. Soc. London Ser. Mathe. Phys. Eng. Sci. 454, 323\u2013337 (1997)","journal-title":"Proc. R. Soc. London Ser. Mathe. Phys. Eng. Sci."},{"issue":"3","key":"5145_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/aama.2000.0699","volume":"25","author":"M Ettinger","year":"2000","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for noncommutative hidden subgroups. Adv. Appl. Math. 25(3), 239\u2013251 (2000)","journal-title":"Adv. Appl. Math."},{"key":"5145_CR4","unstructured":"Ettinger, M., H\u00f8yer, P.: A quantum observable for the graph isomorphism problem. 1999 arXiv: 9901029 [quant-ph]"},{"issue":"3","key":"5145_CR5","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539703440678","volume":"33","author":"O Regev","year":"2004","unstructured":"Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738\u2013760 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5145_CR6","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005)","journal-title":"SIAM J. Comput."},{"key":"5145_CR7","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. (2004) arXiv: 0406151 [quant-ph]"},{"key":"5145_CR8","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Theory of Quantum Computation, Communication, and Cryptography, pp. 20\u201334, (2011)"},{"issue":"1","key":"5145_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jmc-2012-0016","volume":"8","author":"A Childs","year":"2013","unstructured":"Childs, A., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1\u201329 (2013)","journal-title":"J. Math. Cryptol."},{"key":"5145_CR10","unstructured":"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\u20138:16. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2016)"},{"key":"5145_CR11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/cryptography7030040","volume":"7","author":"D-T Dam","year":"2023","unstructured":"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)","journal-title":"Cryptography"},{"key":"5145_CR12","unstructured":"Yang, P., Zhang, X., Lin, S.: Distributed quantum algorithm for the dihedral hidden subgroup problem. (2025) arXiv: 2503.06478 [quant-ph]"},{"key":"5145_CR13","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Kirshanova, E., Stehl\u00e9, D., Wen, W.: Learning with errors and extrapolated dihedral cosets. In: International Conference on Theory and Practice of Public Key Cryptography, pp. 702\u2013727, (2017)","DOI":"10.1007\/978-3-319-76581-5_24"},{"key":"5145_CR14","unstructured":"G\u00e1bor 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\u201366:14, p. 2018. Schloss Dagstuhl Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2018)"},{"key":"5145_CR15","doi-asserted-by":"crossref","unstructured":"Chen, Y., Liu, Q., Zhandry, M.: Quantum algorithms for variants of average-case lattice problems via filtering. In: Advances in Cryptology\u2013EUROCRYPT 2022, pp. 372\u2013401, Springer International Publishing, Cham (2022)","DOI":"10.1007\/978-3-031-07082-2_14"},{"key":"5145_CR16","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/s11128-022-03592-9","volume":"21","author":"X Yan","year":"2022","unstructured":"Yan, X., Lize, G., Suo, J., Wang, L.: Leveraging the hardness of dihedral coset problem for quantum cryptography. Quantum Inf. Process. 21, 308 (2022)","journal-title":"Quantum Inf. Process."},{"key":"5145_CR17","unstructured":"Doliskani, J.: Efficient quantum public-key encryption from learning with errors. (2021)arXiv: 2105.12790 [quant-ph]"},{"issue":"17","key":"5145_CR18","doi-asserted-by":"publisher","first-page":"3228","DOI":"10.1103\/PhysRevLett.76.3228","volume":"76","author":"RB Griffiths","year":"1996","unstructured":"Griffiths, R.B., Niu, C.-S.: Semiclassical fourier transform for quantum computation. Phys. Rev. Lett. 76(17), 3228\u20133231 (1996)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"5145_CR19","first-page":"175","volume":"3","author":"S Beauregard","year":"2003","unstructured":"Beauregard, S.: Circuit for shor\u2019s algorithm using 2n+3 qubits. Quantum Info. Comput. 3(2), 175\u2013185 (2003)","journal-title":"Quantum Info. Comput."},{"key":"5145_CR20","unstructured":"Gidney, C.: Factoring with n+2 clean qubits and n-1 dirty qubits. (2017) arXiv: 1706.07884 [quant-ph]"},{"issue":"7\u20138","key":"5145_CR21","first-page":"673","volume":"17","author":"T H\u00e4ner","year":"2017","unstructured":"H\u00e4ner, T., Roetteler, M., Svore, K.M.: Factoring using 2n + 2 qubits with toffoli based modular multiplication. Quantum Info. Comput. 17(7\u20138), 673\u2013684 (2017)","journal-title":"Quantum Info. Comput."},{"key":"5145_CR22","doi-asserted-by":"crossref","unstructured":"Nam, Y\u00a0S., Su, Y., Maslov, D\u00a0L.: Approximate quantum fourier transform with o(n log(n)) t gates. npj Quantum Information, 6:26, (2018)","DOI":"10.1038\/s41534-020-0257-5"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05145-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-026-05145-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05145-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:52:32Z","timestamp":1775285552000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-026-05145-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,4]]},"references-count":22,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,4]]}},"alternative-id":["5145"],"URL":"https:\/\/doi.org\/10.1007\/s11128-026-05145-w","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,4]]},"assertion":[{"value":"17 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The quantum circuits for dihedral coset separation and the post-processing code are available at:","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"The authors declare no conflict of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"130"}}