{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:47:25Z","timestamp":1776127645553,"version":"3.50.1"},"reference-count":39,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF grant","award":["SaTC-1814221"],"award-info":[{"award-number":["SaTC-1814221"]}]},{"name":"the Institute for Quantum Information and Matter","award":["Samsung Electronics Co., Ltd."],"award-info":[{"award-number":["Samsung Electronics Co., Ltd."]}]},{"name":"NSF Physics Frontiers Center","award":["NSF Grant PHY-1733907"],"award-info":[{"award-number":["NSF Grant PHY-1733907"]}]},{"name":"EU&apos;s Horizon 2020 Marie Sk\u0142odowska-Curie program","award":["891889-QuantOrder"],"award-info":[{"award-number":["891889-QuantOrder"]}]},{"name":"National Science Foundation","award":["CCF-1618287, CCF-1617710, CNS-1617802"],"award-info":[{"award-number":["CCF-1618287, CCF-1617710, CNS-1617802"]}]},{"DOI":"10.13039\/100000005","name":"the US Department of Defense","doi-asserted-by":"crossref","award":["a Vannevar Bush Faculty Fellowship"],"award-info":[{"award-number":["a Vannevar Bush Faculty Fellowship"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Recently Chen and Gao \\cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a Quantum Linear System (QLS) algorithm to a Macaulay linear system over <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">C<\/mml:mi><\/mml:mrow><\/mml:math>, which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao's algorithm by introducing the Boolean Macaulay linear system over <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">C<\/mml:mi><\/mml:mrow><\/mml:math> by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables.Furthermore, we provide a simple and more elementary proof of correctness for our improved algorithm using a reduction employing the Valiant-Vazirani affine hashing method, and also extend the result to polynomial systems over <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">F<\/mml:mi><\/mml:mrow><mml:mi>q<\/mml:mi><\/mml:msub><\/mml:math> improving on subsequent work by Chen, Gao and Yuan \\citeChenGao2018. We also suggest a new approach for extracting the solution of the Boolean polynomial system via a generalization of the quantum coupon collector problem \\cite{arunachalam2020QuantumCouponCollector}.<\/jats:p>","DOI":"10.22331\/q-2023-07-26-1069","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T11:11:28Z","timestamp":1690369888000},"page":"1069","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":7,"title":["Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems"],"prefix":"10.22331","volume":"7","author":[{"given":"Jintai","family":"Ding","sequence":"first","affiliation":[{"name":"University of Cincinnati, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vlad","family":"Gheorghiu","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing \/ Dept. of Combinatorics & Optimization, University of Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Gily\u00e9n","sequence":"additional","affiliation":[{"name":"Institute for Quantum Information and Matter, Caltech, Pasadena CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Hallgren","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianqiang","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. Read the fine print. Nature Physics Nat. Phys. , 11(4):291\u2013293, 2015.","DOI":"10.1038\/nphys3272"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum coupon collector. In Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC) TQC , pages 10:1\u201310:17, 2020. arXiv: 2002.07688.","DOI":"10.4230\/LIPIcs.TQC.2020.10"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Gw\u00e9nol\u00e9 Ars, Jean-Charles Faugere, Hideki Imai, Mitsuru Kawazoe, and Makoto Sugita. Comparison between XL and Gr\u00f6bner basis algorithms. In International Conference on the Theory and Application of Cryptology and Information Security, pages 338\u2013353. Springer, 2004.","DOI":"10.1007\/978-3-540-30539-2_24"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS) STACS , pages 636\u2013647, 2012. arXiv: 1010.4458.","DOI":"10.4230\/LIPIcs.STACS.2012.636"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Eric R Anschuetz, Jonathan P Olson, Al\u00e1n Aspuru-Guzik, and Yudong Cao. Variational quantum factoring. arXiv: 1808.08927, 2018.","DOI":"10.1007\/978-3-030-14082-3_7"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Bruno Buchberger et al. Gr\u00f6bner bases computation by triangularizing Macaulay matrices. In The 50th Anniversary of Gr\u00f6bner Bases, pages 25\u201333. Mathematical Society of Japan, 2018.","DOI":"10.2969\/aspm\/07710025"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Kim Batselier. A numerical linear algebra framework for solving problems with multivariate polynomials. PhD thesis, KU Leuven (Leuven, Belgium), 2013.","DOI":"10.13140\/RG.2.1.3137.9608"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Michel Boyer, Gilles Brassard, Peter H\u00f8yer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4\u20135):493\u2013505, 1998. arXiv: quant-ph\/9605034.","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Magali Bardet, Jean-Charles Faug\u00e8re, Bruno Salvy, and Pierre-Jean Spaenlehauer. On the complexity of solving quadratic boolean systems. Journal of Complexity, 29(1):53\u201375, 2013.","DOI":"10.1016\/j.jco.2012.07.001"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Andreas Bj\u00f6rklund, Petteri Kaski, and Ryan Williams. Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) ICALP, 2019.","DOI":"10.4230\/LIPIcs.ICALP.2019.26"},{"key":"10","unstructured":"Christopher JC Burges. Factoring as optimization. Microsoft Research MSR-TR-200, 2002."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on computing, 26(5):1411\u20131473, 1997.","DOI":"10.1137\/S0097539796300921"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Daniel J Bernstein and Bo-Yin Yang. Asymptotically faster quantum algorithms to solve multivariate quadratic equations. In International Conference on Post-Quantum Cryptography, pages 487\u2013506. Springer, 2018.","DOI":"10.1007\/978-3-319-79063-3_23"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Alessio Caminata and Elisa Gorla. Solving multivariate polynomial systems and an invariant from commutative algebra. arXiv: 1706.06319, 2017.","DOI":"10.1007\/978-3-030-68869-1_1"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Yu-Ao Chen and Xiao-Shan Gao. Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems. Journal of Systems Science and Complexity, 2021. arXiv: 1712.06239.","DOI":"10.1007\/s11424-020-0028-6"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) ICALP, pages 33:1\u201333:14, 2019. arXiv: 1804.01973.","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Proceedings of the 52nd ACM Symposium on the Theory of Computing (STOC) STOC , page 387\u2013400, 2020. arXiv: 1910.06151.","DOI":"10.1145\/3357713.3384314"},{"key":"17","unstructured":"Yu-Ao Chen, Xiao-Shan Gao, and Chun-Ming Yuan. Quantum algorithm for optimization and polynomial system solving over finite field and application to cryptanalysis, 2018. arXiv: 1802.03856."},{"key":"18","doi-asserted-by":"publisher","unstructured":"B David Clader, Bryan C Jacobs, and Chad R Sprouse. Preconditioned quantum linear system algorithm. Physical review letters, 110(25):250504, 2013.","DOI":"10.1103\/PhysRevLett.110.250504"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 392\u2013407. Springer, 2000 (Extended version as of 24 Aug, 2004. http:\/\/www.minrank.org\/xlfull.pdf).","DOI":"10.1007\/3-540-45539-6_27"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing SIAM J. Comp., 46(6):1920\u20131950, 2017. arXiv: 1511.02306.","DOI":"10.1137\/16M1087072"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Claus Diem. The XL-algorithm and a conjecture from commutative algebra. In International Conference on the Theory and Application of Cryptology and Information Security, pages 323\u2013337. Springer, 2004.","DOI":"10.1007\/978-3-540-30539-2_23"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Jintai Ding and Dieter Schmidt. Solving degree and degree of regularity for polynomial systems over a finite fields. In Number Theory and Cryptography, pages 34\u201349. Springer, 2013.","DOI":"10.1007\/978-3-642-42001-6_4"},{"key":"23","unstructured":"Jean-Charles Faugere, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, and Ludovic Perret. Fast quantum algorithm for solving multivariate quadratic equations. arXiv: 1712.07211, 2017."},{"key":"24","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics [full version], 2018. arXiv: 1806.01838.","DOI":"10.1145\/3313276.3316366"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC) STOC, pages 193\u2013204, 2019. arXiv: 1806.01838.","DOI":"10.1145\/3313276.3316366"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters Phys. Rev. Lett., 103(15):150502, 2009. arXiv: 0811.3171.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science (2nd ed.). Texts in Theoretical Computer Science. Springer, 2011.","DOI":"10.1007\/978-3-642-17364-6"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) ITCS, pages 49:1\u201349:21, 2017. arXiv: 1603.08675.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum Quant., 4:361, 2020. arXiv: 1910.14596.","DOI":"10.22331\/q-2020-11-11-361"},{"key":"30","unstructured":"Ludovic Perret. Bases de Gr\u00f6bner en Cryptographie Post-Quantique. PhD thesis, UPMC-Paris 6 Sorbonne Universit\u00e9s, 2016."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Herbert Robbins. A remark on Stirling&apos;s formula. The American Mathematical Monthly, 62(1):26\u201329, 1955.","DOI":"10.2307\/2308012"},{"key":"32","unstructured":"The Mathematica source code is also available at the Woflram Notebook Archive: https:\/\/notebookarchive.org\/2022-02-1ec5yyv, 2022."},{"key":"33","doi-asserted-by":"publisher","unstructured":"Yi\u011fit Suba\u015f\u0131, Rolando D. Somma, and Davide Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Physical Review Letters Phys. Rev. Lett., 122(6):060504, 2019. arXiv: 1805.10549.","DOI":"10.1103\/PhysRevLett.122.060504"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Changpeng Shao and Hua Xiang. Quantum circulant preconditioner for a linear system of equations. Physical Review A, 98(6):062321, 2018.","DOI":"10.1103\/PhysRevA.98.062321"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions. arXiv: 2008.13295, 2020.","DOI":"10.1103\/PhysRevA.104.032422"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science Theor. Comput. Sci., 47:85\u201393, 1986. Earlier version in STOC&apos;85.","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"37","unstructured":"Ronald de Wolf. Quantum computing: Lecture notes, 2019. arXiv: 1907.09415."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Manuela Wiesinger-Widi. Gr\u00f6bner bases and generalized sylvester matrices. PhD thesis, Johannes Kepler University Linz, Austria, 2015.","DOI":"10.1145\/2016567.2016594"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-26-1069\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T11:12:12Z","timestamp":1690369932000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-26-1069\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":39,"URL":"https:\/\/doi.org\/10.22331\/q-2023-07-26-1069","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"article-number":"1069"}}