MATH-STATS Quantum Colloquium: Tamas Terlaky (Lehigh Univ.)

Quantum Interior Point Methods (QIPMs) for linear and semi-definite optimization (LO and SDO) problems build on classic polynomial time IPMs. Quantum Computing (QC) inspired to design novel Inexact Feasible IPM variants. These are novel algorithms in both the QC and classic computing environments. Enhancing Quantum Interior Point Methods (QIPMs) with Iterative Refinement (IR) leads to exponential improvements in the worst-case overall running time of QIPMs, compared to previous QIPMs. We also discuss how the proposed IR scheme can be used in classical inexact IPMs with conjugate gradient methods. Further, the proposed IR scheme exhibits quadratic convergence for LO and SDO towards an optimal solution without any assumption on problem characteristics. On the practical side, IR can be useful to find precise solutions while using inexact LO and SDO solvers.