← 研踪 PaperTrailarXiv:2510.05588 · v4
A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
首次提交 2025-10-07 13:28
版本更新 2026-11-10 23:37
雷达观测 2026-11-11 13:07
摘要
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 $|\vec{y}\rangle$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms have runtimes that scale linearly with the condition number $κ(A)$, the sparsity of $A$, and logarithmically with inverse precision, but often overlook structural properties of $\vec{b}$, whose alignment with $A$'s eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. The runtime of our algorithm depends polynomially on the sparsity 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$. We also introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike left preconditioning methods, which transform the linear system to $DA\vec{y} = D\vec{b}$, our approach applies a right rescaling matrix, reformulating the linear system as $AD\vec{z} = \vec{b}$. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.
作者备注：34 pages ITCS version
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v4 · 2026-11-10 23:37 · 最新观测版本
A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
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 $|\vec{y}\rangle$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms have runtimes that scale linearly with the condition number $κ(A)$, the sparsity of $A$, and logarithmically with inverse precision, but often overlook structural properties of $\vec{b}$, whose alignment with $A$'s eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. The runtime of our algorithm depends polynomially on the sparsity 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$. We also introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike left preconditioning methods, which transform the linear system to $DA\vec{y} = D\vec{b}$, our approach applies a right rescaling matrix, reformulating the linear system as $AD\vec{z} = \vec{b}$. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.
查看此版本解读 →查看此版本原文 ↗