This talk briefly reviews the current state of quantum computing (QC) hardware, and the opportunities and challenges quantum computing offers in solving optimization problems. The Quantum Computing (QC) and the Interior Point Methods (IPM) revolutions inspire novel challenges and novel methodologies. Optimization is in the heart of the quest to evidence quantum advantage. However, the inexactness and condition number dependence characteristics of NISQ (Noisy Intermediate-Scale Quantum) devices forced us to think differently about solving optimization problems.

Considering IPMs for linear and semi-definite optimization (LO and SDO) problems, QC inspired to design Inexact Infeasible and Inexact Feasible Primal-Dual, and Inexact Dual 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 best-performing 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.