MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems

Jintai Ding University of Cincinnati, OH, USA; Yau Math. Sci. Center, Tsinghua University; Ding Lab, Beijing Institute of Mathematical Sciences and Applications Vlad Gheorghiu softwareQ Inc.; Institute for Quantum Computing / Dept. of Combinatorics & Optimization, University of Waterloo, ON, Canada András Gilyén Institute for Quantum Information and Matter, Caltech, Pasadena CA, USA; Alfréd Rényi Institute of Mathematics, Budapest, Hungary Sean Hallgren Department of Computer Science and Engineering, Pennsylvania State University, PA, USA Jianqiang Li Department of Computer Science and Engineering, Pennsylvania State University, PA, USA

TBD mathscidoc:2207.43135

arXiv, 2021.10
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 $\CC$, 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 $\CC$ 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 $\FF_q$ improving on subsequent work by Chen, Gao and Yuan \cite{ChenGao2018}. 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}.
No keywords uploaded!
[ Download ] [ 2022-07-23 11:02:55 uploaded by dingjt ] [ 1682 downloads ] [ 0 comments ] 
@inproceedings{jintai2021limitations,
  title={Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems},
  author={Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, and Jianqiang Li},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220723110256270795719},
  booktitle={arXiv},
  year={2021},
}
Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, and Jianqiang Li. Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems. 2021. In arXiv. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220723110256270795719.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved