2025/10/07 by Jianqiang Li, Li, Jianqiang
Business, Management and Accounting · Computer Science · #Data Structures and Algorithms (cs.DS) #Decision Support System Applications #FOS: Computer and information sciences #FOS: Physical sciences #Multimedia Learning Systems #Polynomial and algebraic computation #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2510.05588
openalex publication_date 2025/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a matrix A of dimension M × N and a vector b, the quantum linear system (QLS) problem asks for the preparation of a quantum state |y⟩ proportional to the solution of Ay = 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 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 b. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix H = [A, -b], the inverse precision, the ℓ2 norm of the solution y = A+ b, and a new instance-dependent parameter ET= ∑i=1M pi2 ⋅ di, where p = (AA\top)+ b, and di denotes the squared ℓ2 norm of the i-th row of H. We also introduce a structure-aware rescaling technique tailored to the solution y = A+ b. Unlike left preconditioning methods, which transform the linear system to DAy = Db, our approach applies a right rescaling matrix, reformulating the linear system as ADz = 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.