{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:35:43Z","timestamp":1775810143629,"version":"3.50.1"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"DOI":"10.13039\/501100005089","name":"Beijing Natural Science Foundation","doi-asserted-by":"publisher","award":["4234084"],"award-info":[{"award-number":["4234084"]}],"id":[{"id":"10.13039\/501100005089","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Key Research Program of the Chinese Academy of Sciences","award":["ZDRW- XX-2022-1"],"award-info":[{"award-number":["ZDRW- XX-2022-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon\u2019s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.<\/jats:p>","DOI":"10.1093\/comjnl\/bxae129","type":"journal-article","created":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T07:38:07Z","timestamp":1733989087000},"page":"520-538","source":"Crossref","is-referenced-by-count":1,"title":["Algorithm for solving quantum linear systems of equations with coherent superposition and extended applications"],"prefix":"10.1093","volume":"68","author":[{"given":"Qiqing","family":"Xia","sequence":"first","affiliation":[{"name":"Institute of Information Engineering , Chinese Academy of Sciences, No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]},{"name":"Key Laboratory of Cyberspace Security Defense , No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No. 19 Yuquan Road, Shijingshan District, Beijing, 100049,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qianru","family":"Zhu","sequence":"additional","affiliation":[{"name":"Institute of Information Engineering , Chinese Academy of Sciences, No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]},{"name":"Key Laboratory of Cyberspace Security Defense , No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]},{"name":"School of Cyber Security , University of Chinese Academy of Sciences, No. 19 Yuquan Road, Shijingshan District, Beijing, 100049,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huiqin","family":"Xie","sequence":"additional","affiliation":[{"name":"Beijing Electronic Science and Technology Institute , No. 7, Fufeng Road, Fengtai District, Beijing, 100070,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Yang","sequence":"additional","affiliation":[{"name":"Institute of Information Engineering , Chinese Academy of Sciences, No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]},{"name":"Key Laboratory of Cyberspace Security Defense , No. 19, Shucun Road, Haidian District, Beijing, 100085,","place":["China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"2025052712505177800_ref1","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for quantum computation: discrete logarithms and factoring","volume-title":"Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November","author":"Shor","year":"1994"},{"key":"2025052712505177800_ref2","first-page":"212","article-title":"A fast quantum mechanical algorithm for database search","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, USA, 22-24 May","author":"Grover","year":"1996"},{"key":"2025052712505177800_ref3","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","article-title":"Quantum mechanics helps in searching for a needle in a haystack","volume":"79","author":"Grover","year":"1997","journal-title":"Phys Rev Lett"},{"key":"2025052712505177800_ref4","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","article-title":"On the power of quantum computation","volume":"26","author":"Simon","year":"1997","journal-title":"SIAM J Comput"},{"key":"2025052712505177800_ref5","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","article-title":"Quantum lower bounds by polynomials","volume":"48","author":"Beals","year":"2001","journal-title":"J ACM"},{"key":"2025052712505177800_ref6","first-page":"2682","article-title":"Quantum distinguisher between the 3-round feistel cipher and the random permutation","volume-title":"IEEE International Symposium on Information Theory, Austin, Texas, USA, 13-18 June","author":"Kuwakado","year":"2010"},{"key":"2025052712505177800_ref7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-662-53008-5_8","article-title":"Breaking symmetric cryptosystems using quantum period finding","volume-title":"Advances in Cryptology\u2013CRYPTO: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, Proceedings, Part II 36","author":"Kaplan","year":"2016"},{"key":"2025052712505177800_ref8","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-319-72565-9_20","article-title":"Quantum key-recovery on full AEZ","volume-title":"Selected Areas in Cryptography\u2013SAC: 24th International Conference, Ottawa, ON, Canada, August 16-18, Revised Selected Papers 24","author":"Bonnetain","year":"2017"},{"key":"2025052712505177800_ref9","first-page":"552","article-title":"Quantum attacks without superposition queries: the offline Simon\u2019s algorithm","volume-title":"Advances in Cryptology\u2013ASIACRYPT: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8\u201312 December, Proceedings, Part I","author":"Bonnetain","year":"2019"},{"key":"2025052712505177800_ref10","first-page":"312","article-title":"Security on the quantum-type Even-Mansour cipher","volume-title":"International Symposium on Information Theory and Its Applications, Honolulu, HI, USA, 28-31 October","author":"Kuwakado","year":"2012"},{"key":"2025052712505177800_ref11","doi-asserted-by":"publisher","first-page":"0065","DOI":"10.26421\/QIC17.1-2-4","article-title":"Using Simon\u2019s algorithm to attack symmetric-key cryptographic primitives","volume":"17","author":"Santoli","year":"2017","journal-title":"Quantum Inf Comput"},{"key":"2025052712505177800_ref12","first-page":"492","article-title":"On quantum slide attacks","volume-title":"Selected Areas in Cryptography\u2013SAC: 26th International Conference, Waterloo, ON, Canada, 12\u201316 August, Revised Selected Papers","author":"Bonnetain","year":"2019"},{"key":"2025052712505177800_ref13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-319-70697-9_6","article-title":"Grover meets Simon\u2013quantumly attacking the FX-construction","volume-title":"Advances in Cryptology\u2013ASIACRYPT: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 3-7 December, Proceedings, Part 10625","author":"Leander","year":"2017"},{"key":"2025052712505177800_ref14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum algorithm for linear systems of equations","volume":"103","author":"Harrow","year":"2009","journal-title":"Phys Rev Lett"},{"key":"2025052712505177800_ref15","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/2591796.2591854","article-title":"Exponential improvement in precision for simulating sparse Hamiltonians","volume-title":"Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA, 31 May - 03 June","author":"Berry","year":"2014"},{"key":"2025052712505177800_ref16","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1137\/16M1087072","article-title":"Quantum algorithm for systems of linear equations with exponentially improved dependence on precision","volume":"46","author":"Childs","year":"2017","journal-title":"SIAM J Comput"},{"key":"2025052712505177800_ref17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502","article-title":"Quantum linear system algorithm for dense matrices","volume":"120","author":"Wossnig","year":"2018","journal-title":"Phys Rev Lett"},{"key":"2025052712505177800_ref18","first-page":"49:1","article-title":"Quantum recommendation systems","volume-title":"8th Innovations in Theoretical Computer Science Conference, Berkeley, CA, USA, 9-11, January","author":"Kerenidis","year":"2017"},{"key":"2025052712505177800_ref19","doi-asserted-by":"publisher","first-page":"060504","DOI":"10.1103\/PhysRevLett.122.060504","article-title":"Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing","volume":"122","author":"Suba\u015fi","year":"2019","journal-title":"Phys Rev Lett"},{"key":"2025052712505177800_ref20","first-page":"366","article-title":"A complete quantum circuit to solve the information set decoding problem","volume-title":"IEEE International Conference on Quantum Computing and Engineering (QCE), Broomfield, CO, USA, 17-22 October","author":"Perriello","year":"2021"},{"key":"2025052712505177800_ref21","article-title":"An optimized quantum implementation of ISD on scalable quantum resources","author":"Esser","year":"2021"},{"key":"2025052712505177800_ref22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.46586\/tches.v2022.i1.1-27","article-title":"Quantum period finding against symmetric primitives in practice","volume":"2022","author":"Bonnetain","year":"2021","journal-title":"IACR Trans Cryptogr Hardw Embed Syst"},{"key":"2025052712505177800_ref23","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.tcs.2014.05.025","article-title":"Quantum cryptography: public key distribution and coin tossing","volume":"560","author":"Bennett","year":"2014","journal-title":"Theor Comput Sci"},{"key":"2025052712505177800_ref24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.64.062309","article-title":"Quantum authentication of classical messages","volume":"64","author":"Curty","year":"2001","journal-title":"Phys Rev A"},{"key":"2025052712505177800_ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.044305","article-title":"Quantum secure direct communication with high-dimension quantum superdense coding","volume":"71","author":"Wang","year":"2005","journal-title":"Phys Rev A"},{"key":"2025052712505177800_ref26","volume-title":"Introduction to Linear Algebra","author":"Strang","year":"2022"},{"key":"2025052712505177800_ref27","article-title":"On the post-quantum security of encrypted key exchange protocols","author":"Yang","year":"2013"},{"key":"2025052712505177800_ref28","doi-asserted-by":"publisher","first-page":"461","DOI":"10.26421\/QIC8.5-6-8","article-title":"On the CNOT-cost of Toffoli gates","volume":"9","author":"Shende","year":"2009","journal-title":"Quantum Inf Comput"},{"key":"2025052712505177800_ref29","article-title":"Intermediate-qudit assisted improved quantum algorithm for string matching with an advanced decomposition of Fredkin gate","author":"Saha","year":"2023"},{"key":"2025052712505177800_ref30","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen","year":"2010"},{"key":"2025052712505177800_ref31","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","article-title":"Quantum amplitude amplification and estimation","volume":"305","author":"Brassard","year":"2002","journal-title":"Contemp Math"},{"key":"2025052712505177800_ref32","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1038\/s41566-017-0007-1","article-title":"Single-qubit quantum memory exceeding ten-minute coherence time","volume":"11","author":"Wang","year":"2017","journal-title":"Nat Photonics"},{"key":"2025052712505177800_ref33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-019-2689-4","article-title":"Effect on ion-trap quantum computers from the quantum nature of the driving field","volume":"63","author":"Yang","year":"2020","journal-title":"Sci China Inf Sci"},{"key":"2025052712505177800_ref34","first-page":"252","article-title":"How to protect DES against exhaustive key search","volume-title":"Advances in Cryptology\u2013CRYPTO\u201996: 16th Annual International Cryptology Conference Santa Barbara, California, USA, Proceedings 16, 18-22 August","author":"Kilian","year":"1996"},{"key":"2025052712505177800_ref35","first-page":"208","article-title":"PRINCE\u2013a low-latency block cipher for pervasive computing applications","volume-title":"Advances in Cryptology\u2013ASIACRYPT: 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, Proceedings 18, 2-6 December","author":"Borghoff","year":"2012"},{"key":"2025052712505177800_ref36","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-662-44371-2_4","article-title":"Block ciphers\u2013focus on the linear layer (feat. PRIDE)","volume-title":"Advances in Cryptology\u2013CRYPTO: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part I 34, 17-21 August","author":"Albrecht","year":"2014"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/5\/520\/61051758\/bxae129.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/68\/5\/520\/61051758\/bxae129.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T16:51:55Z","timestamp":1748364715000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/68\/5\/520\/7921455"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":36,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,12,11]]},"published-print":{"date-parts":[[2025,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxae129","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,5]]},"published":{"date-parts":[[2024,12,11]]}}}