1University of Cincinnati, OH, USA
2Institute for Quantum Computing / Dept. of Combinatorics & Optimization, University of Waterloo, ON, Canada
3Institute for Quantum Information and Matter, Caltech, Pasadena CA, USA
4Department of Computer Science and Engineering, Pennsylvania State University, PA, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Recently Chen and Gao [15] 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 $mathbb{C}$, 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 $mathbb{C}$ 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 $mathbb{F}_q$ 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 [2].
[embedded content]
► BibTeX data
► References
[1] Scott Aaronson. Read the fine print. Nature Physics Nat. Phys. , 11(4):291–293, 2015.
https://doi.org/10.1038/nphys3272
[2] 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–10:17, 2020. arXiv: 2002.07688.
https://doi.org/10.4230/LIPIcs.TQC.2020.10
arXiv:2002.07688
[3] Gwénolé Ars, Jean-Charles Faugere, Hideki Imai, Mitsuru Kawazoe, and Makoto Sugita. Comparison between XL and Gröbner basis algorithms. In International Conference on the Theory and Application of Cryptology and Information Security, pages 338–353. Springer, 2004.
https://doi.org/10.1007/978-3-540-30539-2_24
[4] 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–647, 2012. arXiv: 1010.4458.
https://doi.org/10.4230/LIPIcs.STACS.2012.636
arXiv:1010.4458
[5] Eric R Anschuetz, Jonathan P Olson, Alán Aspuru-Guzik, and Yudong Cao. Variational quantum factoring. arXiv: 1808.08927, 2018.
https://doi.org/10.1007/978-3-030-14082-3_7
arXiv:1808.08927
[6] Bruno Buchberger et al. Gröbner bases computation by triangularizing Macaulay matrices. In The 50th Anniversary of Gröbner Bases, pages 25–33. Mathematical Society of Japan, 2018.
https://doi.org/10.2969/aspm/07710025
[7] Kim Batselier. A numerical linear algebra framework for solving problems with multivariate polynomials. PhD thesis, KU Leuven (Leuven, Belgium), 2013.
https://doi.org/10.13140/RG.2.1.3137.9608
[8] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/9605034.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
arXiv:quant-ph/9605034
[9] Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Pierre-Jean Spaenlehauer. On the complexity of solving quadratic boolean systems. Journal of Complexity, 29(1):53–75, 2013.
https://doi.org/10.1016/j.jco.2012.07.001
[10] Andreas Björklund, 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.
https://doi.org/10.4230/LIPIcs.ICALP.2019.26
[11] Christopher JC Burges. Factoring as optimization. Microsoft Research MSR-TR-200, 2002.
[12] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on computing, 26(5):1411–1473, 1997.
https://doi.org/10.1137/S0097539796300921
[13] 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–506. Springer, 2018.
https://doi.org/10.1007/978-3-319-79063-3_23
[14] Alessio Caminata and Elisa Gorla. Solving multivariate polynomial systems and an invariant from commutative algebra. arXiv: 1706.06319, 2017.
https://doi.org/10.1007/978-3-030-68869-1_1
arXiv:1706.06319
[15] 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.
https://doi.org/10.1007/s11424-020-0028-6
arXiv:1712.06239
[16] Shantanav Chakraborty, András Gilyén, 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–33:14, 2019. arXiv: 1804.01973.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv:1804.01973
[17] Nai-Hui Chia, András Gilyén, 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–400, 2020. arXiv: 1910.06151.
https://doi.org/10.1145/3357713.3384314
arXiv:1910.06151
[18] 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.
arXiv:1802.03856
[19] B David Clader, Bryan C Jacobs, and Chad R Sprouse. Preconditioned quantum linear system algorithm. Physical review letters, 110(25):250504, 2013.
https://doi.org/10.1103/PhysRevLett.110.250504
[20] 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–407. Springer, 2000 (Extended version as of 24 Aug, 2004. http://www.minrank.org/xlfull.pdf).
https://doi.org/10.1007/3-540-45539-6_27
http://www.minrank.org/xlfull.pdf)
[21] 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–1950, 2017. arXiv: 1511.02306.
https://doi.org/10.1137/16M1087072
arXiv:1511.02306
[22] 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–337. Springer, 2004.
https://doi.org/10.1007/978-3-540-30539-2_23
[23] 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–49. Springer, 2013.
https://doi.org/10.1007/978-3-642-42001-6_4
[24] 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.
arXiv:1712.07211
[25] András Gilyén, 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.
arXiv:1806.01838
[26] András Gilyén, 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–204, 2019. arXiv: 1806.01838.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838
[27] 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.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171
[28] Stasys Jukna. Extremal Combinatorics – With Applications in Computer Science (2nd ed.). Texts in Theoretical Computer Science. Springer, 2011.
https://doi.org/10.1007/978-3-642-17364-6
[29] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS) ITCS, pages 49:1–49:21, 2017. arXiv: 1603.08675.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
arXiv:1603.08675
[30] 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.
https://doi.org/10.22331/q-2020-11-11-361
arXiv:1910.14596
[31] Ludovic Perret. Bases de Gröbner en Cryptographie Post-Quantique. PhD thesis, UPMC-Paris 6 Sorbonne Universités, 2016.
[32] Herbert Robbins. A remark on Stirling’s formula. The American Mathematical Monthly, 62(1):26–29, 1955.
https://doi.org/10.2307/2308012
[33] The Mathematica source code is also available at the Woflram Notebook Archive: https://notebookarchive.org/2022-02-1ec5yyv, 2022.
https://notebookarchive.org/2022-02-1ec5yyv
[34] Yiğit Subaşı, 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.
https://doi.org/10.1103/PhysRevLett.122.060504
arXiv:1805.10549
[35] Changpeng Shao and Hua Xiang. Quantum circulant preconditioner for a linear system of equations. Physical Review A, 98(6):062321, 2018.
https://doi.org/10.1103/PhysRevA.98.062321
[36] 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.
https://doi.org/10.1103/PhysRevA.104.032422
arXiv:2008.13295
[37] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science Theor. Comput. Sci., 47:85–93, 1986. Earlier version in STOC’85.
https://doi.org/10.1016/0304-3975(86)90135-0
[38] Ronald de Wolf. Quantum computing: Lecture notes, 2019. arXiv: 1907.09415.
arXiv:1907.09415
[39] Manuela Wiesinger-Widi. Gröbner bases and generalized sylvester matrices. PhD thesis, Johannes Kepler University Linz, Austria, 2015.
https://doi.org/10.1145/2016567.2016594
Cited by
Could not fetch Crossref cited-by data during last attempt 2023-07-26 10:46:19: Could not fetch cited-by data for 10.22331/q-2023-07-26-1069 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2023-07-26 10:46:19).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Automotive / EVs, Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- BlockOffsets. Modernizing Environmental Offset Ownership. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-07-26-1069/
