https://m2.mtmt.hu/ hun 2026-10-23 19:34 JournalArticle 34479740 VALIDATED true 0 false 2026-07-07T07:29:37.674+0000 2025-06-03T11:39:44.666+0000 2024-01-05T12:37:54.163+0000 true 10000741 Ivanyos Gábor /api/author/10000741 Author Ivanyos Gábor (Algebra, számítástudomány) true 10000741 2024-12-12T11:59:43.564+0000 2024-12-12T11:59:43.564+0000 2024-12-12T11:59:57.095+0000 true 10015181 Nagy Eszter /api/admin/10015181 Admin Nagy Eszter (SZTA admi, admin) true 10015181 Admin 10014568 /api/admin/10014568 Vándor Andrea (VA, admin) Vándor Andrea true 10014568 true 2025-05-27T08:28:08.397+0000 true false true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle true 10000059 Article true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle /api/subtype/10000059 Szakcikk SubType Szakcikk (Folyóiratcikk) 101 true 10000059 true 1 /api/category/1 Category Tudományos true 1 Imran, M true true /api/journal/10007248 REVIEWED QUANTUM INFORMATION PROCESSING 1570-0755 1573-1332 true false 10007248 false 10007248 true 1570-0755 1573-1332 Journal FOREIGN 23 1 14 14 23 2024 We propose a method for solving the hidden subgroup problem in nilpotent groups. The main idea is iteratively transforming the hidden subgroup to its images in the quotient groups by the members of a central series, eventually to its image in the commutative quotient of the original group, and then using an abelian hidden subgroup algorithm to determine this image. Knowing this image allows one to descend to a proper subgroup unless the hidden subgroup is the full group. The transformation relies on finding zero sum subsequences of sufficiently large sequences of vectors over finite prime fields. We present a new deterministic polynomial time algorithm for the latter problem in the case when the size of the field is constant. The consequence is a polynomial time exact quantum algorithm for the hidden subgroup problem in nilpotent groups having constant nilpotency class and whose order only have prime factors also bounded by a constant. Funding 2036811 /api/funding/2036811 MILAB(RRF-2.3.1-21-2022-00004) Támogató: NKFIH false true true 2024 true true true false true false GOLD 2026-07-07 true https://doi.org/10.1007/s11128-023-04228-2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 Q2 false 10000741 false false false 2024-02-29T07:56:19.212+0000 Budapesti Műszaki és Gazdaságtudományi Egyetem; Számítástudományi Kutatócsoport (HRN SZTAKI / IL) 2 14 2 2 0 true 10014568 Language 10002 /api/language/10002 Angol Angol English true 2 true PersonAuthorship 113653317 /api/authorship/113653317 Imran, M ✉ [Imran, Muhammad (Computational alg...), szerző] Budapesti Műszaki és Gazdaságtudományi Egyetem 1 0.5 true false true Author 10087993 /api/author/10087993 Imran Muhammad (Computational algebra) Imran Muhammad DUPLUM true true Imran M true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 113653367 /api/authorship/113653367 Ivanyos, G [Ivanyos, Gábor (Algebra, számítás...), szerző] Számítástudományi Kutatócsoport (HRN SZTAKI / IL) 2 0.0 false true Author 10000741 /api/author/10000741 Ivanyos Gábor (Algebra, számítástudomány) Ivanyos Gábor true 10000741 true Ivanyos G true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PublicationIdentifier 25233048 /api/publicationidentifier/25233048 DOI: 10.1007/s11128-023-04228-2 PlainSource 6 /api/publicationsource/6 DOI PublicationSourceType 10001 /api/publicationsourcetype/10001 DOI true true true DOI DOI https://doi.org/@@@ true true 6 true GOLD true IDENTICAL 10.1007/s11128-023-04228-2 https://doi.org/10.1007/s11128-023-04228-2 false true PublicationIdentifier 25423033 /api/publicationidentifier/25423033 WoS: 001136776400003 PlainSource 1 /api/publicationsource/1 WoS PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true WoS WoS https://www.webofscience.com/wos/woscc/full-record/@@@ true true 1 true IDENTICAL 001136776400003 https://www.webofscience.com/wos/woscc/full-record/001136776400003 false true PublicationIdentifier 25723110 /api/publicationidentifier/25723110 SZTAKI: 10704 SwordSource 86 /api/publicationsource/86 SZTAKI PublicationSourceType 10007 /api/publicationsourcetype/10007 Repozitórium true true true SZTAKI SZTAKI https://eprints.sztaki.hu/@@@ true true 86 true GOLD true IDENTICAL 10704 https://eprints.sztaki.hu/10704 false true PublicationIdentifier 25279824 /api/publicationidentifier/25279824 Scopus: 85181403431 PlainSource 3 /api/publicationsource/3 Scopus PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true Scopus Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true IDENTICAL 85181403431 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85181403431 false true Classification 10006 /api/classification/10006 Algebra true true Classification 10074 /api/classification/10074 Algoritmusok, elosztott, párhuzamos és hálózati algoritmusok, algoritmikus játékelmélet true true Classification 10008 /api/classification/10008 Algoritmusok és komplexitás true true Classification 10057 /api/classification/10057 Elméleti számítástudomány, formális módszerek, kvantumszámítástechnika true true Classification 10159 /api/classification/10159 Kvantumoptika és kvantuminformáció true true Classification 10039 /api/classification/10039 Számítógépes geometria, tételbizonyítás, szimbolikus, algebrai számítások true true Keyword 3693 /api/keyword/3693 artificial intelligence true 3693 true SjrRating 11461167 /api/sjrrating/11461167 sjr:Q2 (2024) Scopus - Electrical and Electronic Engineering QUANTUM INFORMATION PROCESSING 1570-0755 1573-1332 337 0.49 journal RatingType 10002 /api/ratingtype/10002 sjr sjr true true ClassificationExternal 2208 /api/classificationexternal/2208 Scopus - Electrical and Electronic Engineering true 2208 true Q2 DIRECT true true Reference 48451553 /api/reference/48451553 1. Ettinger, M., Høyer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett. 91, 43–48 (2004). arXiv:quant-ph/0401083, DOI: 10.1016/j.ipl.2004.01.024 1 10.1016/j.ipl.2004.01.024 false true Reference 48451554 /api/reference/48451554 2. Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005). arXiv:quant-ph/0302112, DOI: 10.1137/S0097539703436345 2 10.1137/S0097539703436345 false true Reference 48451555 /api/reference/48451555 3. Alagic, G., Moore, C., Russell, A.: Quantum algorithms for Simon’s problem over general groups. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1217–1224 (2007). arXiv:quant-ph/0603251 3 false true Reference 48451556 /api/reference/48451556 4. Lomont, C.: The hidden subgroup problem-review and open problems. Technical report (2004). arXiv:quant-ph/0603251 4 false true Reference 48451557 /api/reference/48451557 5. Wang, F.: The hidden subgroup problem. Technical report (2010). arXiv:1101.1053 5 false true Reference 48451558 /api/reference/48451558 6. Lomonaco, S.J., Kauffman, L.H.: Quantum hidden subgroup algorithms: an algorithmic toolkit. In: Mathematics of Quantum Computation and Quantum Technology, pp. 21–64. Chapman and Hall/CRC, New York (2007). arXiv:quant-ph/0607046, DOI: 10.1201/9781584889007-7 6 10.1201/9781584889007-7 false true Reference 48451559 /api/reference/48451559 7. Horan, K., Kahrobaei, D.: The hidden subgroup problem and post-quantum group-based cryptography. In: Mathematical Software—ICMS 2018, pp. 218–226 (2018). Springer. arXiv:1805.04179, DOI: 10.1007/978-3-319-96418-8_26 7 10.1007/978-3-319-96418-8_26 false true Reference 48451560 /api/reference/48451560 8. Castryck, W., Meeren, N.V.: Two remarks on the vectorization problem. In: Progress in Cryptology—INDOCRYPT 2022, pp. 658–678 (2023). Springer, DOI: 10.1007/978-3-031-22912-1_29 8 10.1007/978-3-031-22912-1_29 false true Reference 48451561 /api/reference/48451561 9. Alagic, G., Russell, A.: Quantum-secure symmetric-key cryptography based on hidden shifts. In: Advances in Cryptology—EUROCRYPT 2017, pp. 65–93 (2017). Springer. arXiv:1610.01187, DOI: 10.1007/978-3-319-56617-7_3 9 10.1007/978-3-319-56617-7_3 false true Reference 48451562 /api/reference/48451562 10. Bae, E., Lee, S.: Quantum algorithm based on the \varepsilon -random linear disequations for the continuous hidden shift problem. Quantum Inf. Process. 20(10), 347 (2021). arXiv:1904.06225, DOI: 10.1007/s11128-021-03290-y 10 10.1007/s11128-021-03290-y false true Reference 48451563 /api/reference/48451563 11. Brassard, G., Høyer, P.: An exact quantum polynomial-time algorithm for Simon’s problem. In: ISTCS 97, pp. 12–23 (1997). arXiv:quant-ph/9704027 11 false true Reference 48451564 /api/reference/48451564 12. Cai, G., Qiu, D.: Optimal separation in exact query complexities for Simon’s problem. J. Comput. Syst. Sci. 97, 83–93 (2018). arXiv:1610.01920, DOI: 10.1016/j.jcss.2018.05.001 12 10.1016/j.jcss.2018.05.001 false true Reference 48451565 /api/reference/48451565 13. Bonnetain, X.: Tight bounds for Simon’s algorithm. In: LATINCRYPT 2021, pp. 2–23 (2021), DOI: 10.1007/978-3-030-88238-9_1 13 10.1007/978-3-030-88238-9_1 false true Reference 48451566 /api/reference/48451566 14. Wu, Z., Qiu, D., Tan, J., Li, H., Cai, G.: Quantum and classical query complexities for generalized Simon’s problem. Theor. Comput. Sci. 924, 171–186 (2022). arXiv:1905.08549, DOI: 10.1016/j.tcs.2022.05.025 14 10.1016/j.tcs.2022.05.025 false true Reference 48451567 /api/reference/48451567 15. Mosca, M., Zalka, C.: Exact quantum Fourier transforms and discrete logarithm algorithms. Int. J. Quantum Inf. 02, 91–100 (2003). arXiv:quant-ph/0301093, DOI: 10.1142/S0219749904000109 15 10.1142/S0219749904000109 false true Reference 48451568 /api/reference/48451568 16. Imran, M., Ivanyos, G.: An exact quantum hidden subgroup algorithm and applications to solvable groups. Quantum Inf. Comput. 22(9 &10), 770–789 (2022). arXiv:2202.04047 16 false true Reference 48451569 /api/reference/48451569 17. Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and translating coset in quantum computing. SIAM J. Comput. 43(1), 1–24 (2014) arXiv:quant-ph/0211091. Preliminary version in STOC 2003, DOI: 10.1137/130907203 17 10.1137/130907203 false true Reference 48451570 /api/reference/48451570 18. Bonnetain, X., Naya-Plasencia, M.: Hidden shift quantum cryptanalysis and implications. In: Advances in Cryptology—ASIACRYPT 2018, pp. 560–592 (2018). Springer, DOI: 10.1007/978-3-030-03326-2_19 18 10.1007/978-3-030-03326-2_19 false true Reference 48451571 /api/reference/48451571 19. Ivanyos, G., Sanselme, L., Santha, M.: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algorithmica 62(1–2), 480–498 (2012). arXiv:0707.1260, DOI: 10.1007/s00453-010-9467-0 19 10.1007/s00453-010-9467-0 false true Reference 48451572 /api/reference/48451572 20. Decker, T., Høyer, P., Ivanyos, G., Santha, M.: Polynomial time quantum algorithms for certain bivariate hidden polynomial problems. Quantum Inf. Comput. 14(9–10), 790–806 (2014). arXiv:1305.1543 20 false true Reference 48451573 /api/reference/48451573 21. Ivanyos, G., Santha, M.: Solving systems of diagonal polynomial equations over finite fields. Theor. Comput. Sci. 657, 73–85 (2017). arXiv:1503.09016, DOI: 10.1016/j.tcs.2016.04.045 21 10.1016/j.tcs.2016.04.045 false true Reference 48451574 /api/reference/48451574 22. Olson, J.E.: A combinatorial problem on finite abelian groups, I. J. Number Theory 1(1), 8–10 (1969). https://doi.org/10.1016/0022-314X(69)90021-3, DOI: 10.1016/0022-314X(69)90021-3 22 10.1016/0022-314X(69)90021-3 false true Reference 48451575 /api/reference/48451575 23. Nishimura, H., Ozawa, M.: Uniformity of quantum circuit families for error-free algorithms. Theor. Comput. Sci. 332, 487–496 (2005). https://doi.org/10.1016/j.tcs.2004.12.020, DOI: 10.1016/j.tcs.2004.12.020 23 10.1016/j.tcs.2004.12.020 false true Reference 48451576 /api/reference/48451576 24. Nishimura, H., Ozawa, M.: Computational complexity of uniform quantum circuit families and quantum Turing machines. Theor. Comput. Sci. 276, 147–181 (2002). arXiv:quant-ph/9906095, DOI: 10.1016/S0304-3975(01)00111-6 24 10.1016/S0304-3975(01)00111-6 false true Reference 48451577 /api/reference/48451577 25. Nishimura, H., Ozawa, M.: Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families. Quantum Inf. Process. 8, 13–24 (2009). arXiv:quant-ph/0511117, DOI: 10.1007/s11128-008-0091-8 25 10.1007/s11128-008-0091-8 false true Reference 48451578 /api/reference/48451578 26. Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26, 1411–1473 (1997). https://doi.org/10.1137/S0097539796300921, DOI: 10.1137/S0097539796300921 26 10.1137/S0097539796300921 false true Reference 48451579 /api/reference/48451579 27. Robinson, D.: A Course in the Theory of Groups, 2nd edn. Springer, Urbana (1995) 27 false true Reference 48451580 /api/reference/48451580 28. Kantor, W.M., Luks, E.M.: Computing in quotient groups. In: STOC 1990, pp. 524–534 (1990). https://doi.org/10.1145/100216.100290, DOI: 10.1145/100216.100290 28 10.1145/100216.100290 false true Reference 48451581 /api/reference/48451581 29. Watrous, J.: Quantum algorithms for solvable groups. In: STOC 2001, pp. 60–67 (2001). arXiv:quant-ph/0011023, DOI: 10.1145/380752.380759 29 10.1145/380752.380759 false true Reference 48451582 /api/reference/48451582 30. Nielsen, M.A., Chuang, I.K.: Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press, Cambridge (2010) 30 false true Reference 48451583 /api/reference/48451583 31. Lomonaco, S.J., Kauffman, L.H.: Is Grover’s algorithm a quantum hidden subgroup algorithm? Quantum Inf. Process. 6, 461–476 (2007). arXiv:quant-ph/0603140, DOI: 10.1007/s11128-007-0066-1 31 10.1007/s11128-007-0066-1 false true /api/publication/34479740 Imran M et al. Zero sum subsequences and hidden subgroups. (2024) QUANTUM INFORMATION PROCESSING 1570-0755 1573-1332 23 1<div class="JournalArticle Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <img title="Idézőközlemény" style="float: left" src="/frontend/resources/grid/publication-citation-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10087993"><a href="/gui2/?type=authors&mode=browse&sel=10087993" target="_blank">Imran M ✉ (<span class="authorship-author-name">Imran Muhammad</span> <span class="authorAux-mtmt"> Computational algebra</span>) </a> </span> <span class="author-affil">Budapesti Műszaki és Gazdaságtudományi Egyetem</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10000741"><a href="/gui2/?type=authors&mode=browse&sel=10000741" target="_blank">Ivanyos G (<span class="authorship-author-name">Ivanyos Gábor</span> <span class="authorAux-mtmt"> Algebra, számítástudomány</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Számítástechnikai és Automatizálási Kutatóintézet">HRN SZTAKI</span>/<span title="Mesterséges Intelligencia Kutatólaboratórium">IL</span>/Számítástudományi Kutatócsoport</span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;34479740" target="_blank">Zero sum subsequences and hidden subgroups</a></div> <div> <span class="journal-title">QUANTUM INFORMATION PROCESSING</span> <span class="journal-issn">(<a target="_blank" href="https://portal.issn.org/resource/ISSN/1570-0755">1570-0755</a> <a target="_blank" href="https://portal.issn.org/resource/ISSN/1573-1332">1573-1332</a>)</span>: <span class="journal-volume">23</span> <span class="journal-issue">1</span> <span class="page"> Paper 14. 23 p. </span> <span class="year">(2024)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:blue" title="10.1007/s11128-023-04228-2" target="_blank" href="https://doi.org/10.1007/s11128-023-04228-2"> DOI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="001136776400003" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/001136776400003"> WoS </a> </span> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:blue" title="10704" target="_blank" href="https://eprints.sztaki.hu/10704"> SZTAKI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="85181403431" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85181403431"> Scopus </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <div class="journal-subject">Folyóirat szakterülete: Scopus - Electrical and Electronic Engineering&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Electronic, Optical and Magnetic Materials&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Modeling and Simulation&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q2</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Signal Processing&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q3</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Statistical and Nonlinear Physics&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q3</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Theoretical Computer Science&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;Q3</div> </div></OnlyViewableByAuthor> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;34479740&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 2 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 34479740</span> | <span class="status-data status-VALIDATED"> Egyeztetett </span> Forrás Idéző | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">kézi felvitel</span> </div> <div class="funder"> MILAB(RRF-2.3.1-21-2022-00004) Támogató: NKFIH </div> <div class="lastModified">Utolsó módosítás: 2025.06.03. 13:39 Vasvari Lilian (MTMT Központ, admin) </div> <div class="lockedBy">Központi kezelésű 2025.05.27. 10:28 Vándor Andrea (VA, admin) </div> </div></div>