Quantum computing inspired iterative refinement for semidefinite optimization

• 成果类型: Article; Early Access
• 署名作者: Mohammadisiahroudi, Mohammadhossein; Augustino, Brandon; Sampourmahani, Pouya; Terlaky, Tamas
• 署名单位: Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02183-z
• 发表日期: 2025
• 关键词: interior-point algorithm; linear complementarity-problem; local convergence

摘要

Iterative Refinement (IR) is a classical computing technique for obtaining highly precise solutions to linear systems of equations, as well as linear optimization problems. In this paper, motivated by the limited precision of quantum solvers, we develop the first IR scheme for solving semidefinite optimization (SDO) problems and explore two major impacts of the proposed IR scheme. First, we prove that the proposed IR scheme exhibits quadratic convergence of the optimality gap without any assumption on problem characteristics. As an application of our results, we show that using IR with Quantum Interior Point Methods (QIPMs) leads to exponential improvements in the worst-case overall running time of QIPMs, compared to previous best-performing QIPMs. We also discuss how the proposed IR scheme can be used with classical inexact SDO solvers, such as classical inexact IPMs with conjugate gradient methods.