QIP2021 | Limitations of the Macaulay matrix approach for using the HHL algorithm... (Jianqiang Li)

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

Authors: Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren and Jianqiang Li
Affiliations: University of Cincinnati, OH, USA | softwareQ Inc. / Institute for Quantum Computing / Dept.\ of Combinatorics \& Optimization, University of Waterloo | California Institute of Technology | Department of Computer Science and Engineering, Pennsylvania

Abstract
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 solution. We describe a Grover-based exhaustive search algorithm that always 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 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{arunachalam2020quantum}.

Get entangled with us!