Publikation
Iterative Quantum-Assisted Least Squares Optimization with Convergence Guarantees
Supreeth Mysore Venkatesh; Antonio Macaluso; Diego Arenas; Matthias Klusch; Andreas Dengel
In: Journal of Computational Science (JOCS), Vol. xx, Pages 1-33, Elsevier, 2026.
Zusammenfassung
This article presents i-QLS, an anytime iterative quantum-assisted least squares optimization method that leverages quantum annealing to mitigate
the scalability and precision limitations of prior quantum least-squares approaches. Unlike prior QUBO-based formulations that struggle on current
quantum annealers’ low qubit counts, i-QLS uses low-precision runs and recovers accuracy through iterative refinement toward the optimum. Our
contribution includes a discretization scheme of the least-squares problem, QUBO construction, refinement dynamics, and provides a formal convergence
analysis showing that, once the true optimum lies inside the initial predefined interval, the width of the search range decreases geometrically at every iteration, yielding exponential convergence of the parameter estimates. We further identify a structural limitation that arises when the true optimum lies outside the initial discretization interval and introduce i-QLS+, which replaces interval shrinking with a deterministic translation step upon boundary selections. This mechanism guarantees finite-time entrance into the correct search region and restores the same fast geometric refinement of the baseline method. Our empirical evaluation includes experiments on multiple generations of D-Wave quantum annealers, two distinct hardware-embedded implementations of the algorithm, robustness tests under misspecified intervals, and scalability to regression problems with up to 175 features. We additionally demonstrate that the framework naturally extends to nonlinear regression through spline-based modeling. Overall, this work establishes i-QLS and i-QLS+ as scalable, theoretically grounded, and practically effective tools for quantum-assisted regression on near-term quantum hardware, without claiming a quantum advantage over state-of-the-art classical solvers. An earlier version of this work appeared in our ICCS conference paper [28].