Jianqiang Li

Given a matrix $A$ of dimension $M\times N$ and a vector $\vec{b}$, the quantum linear system (QLS) problem asks for the preparation of a quantum state $\ket{\vec{y}}$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms typically have runtimes that scale linearly with the condition number $\kappa(A)$, the sparsity of $A$, and logarithmically with the inverse precision. However, these algorithms often overlook structural properties of the input vector $\vec{b}$, despite the fact that its alignment with the eigenspaces of $A$ can significantly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. Let the sparsity of a matrix be defined as the maximum number of nonzero entries in any row or column. The runtime of our algorithm depends polynomially on the sparsity $\s$ of the augmented matrix $H = [A , -\vec{b}]$, the inverse precision, the $\ell_2$ norm of the solution $\vec{y} = A^+ \vec{b}$, and a new instance-dependent parameter $$ ET = \sum_{i=1}^M p_i^2 \cdot d_i, $$ where $\vec{p} = (AA^{\top})^+ \vec{b}$, and $d_i$ denotes the squared $\ell_2$-norm of the $i$-th row of $H$. To further reduce the runtime for certain applications we introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike \emph{left} preconditioning methods, which transform the system to $DA\vec{z} = D\vec{b}$, our approach applies a \emph{right} rescaling matrix, reformulating the linear system as $A D \vec{z} = \vec{b}$. This combination of an instance-aware QLS algorithm and a rescaling strategy reopens the possibilities for achieving superpolynomial quantum speedups in various domains, such as nonlinear differential equations and polynomial systems. As a application, we develop a new quantum algorithm for solving multivariate polynomial systems in regimes where previous QLS-based methods fail. Our results yield a new end-to-end algorithmic framework, grounded in our new QLS algorithm, that applies to a broad class of problems. In particular, we apply our approach to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system. Given a graph, the MIS problem asks for finding the largest subset of vertices such that no two vertices in the subset share an edge. We provide a detailed runtime analysis and show that, under certain conditions, our quantum algorithm for the MIS problem runs in polynomial time. While no classical algorithms have been developed under these conditions, a promising feature of our quantum algorithm is that its runtime explicitly depends on the structure of the independent sets in the input graph.

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}.