Blog

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.

SHORT BIO: Tamás Terlaky

Dr. Terlaky has published four books, edited over ten books and journal special issues and published over 220 research papers. Topics include theoretical and algorithmic foundations of mathematical optimization; quantum computing optimization; nuclear reactor core reloading, oil refinery, VLSI design, radiation therapy treatment, and inmate assignment optimization.

Dr. Terlaky is Editor-in-Chief of the Journal of Optimization Theory and Applications. He has served as associate editor of ten journals and has served as conference chair, conference organizer, and distinguished invited speaker at conferences all over the world. He was general Chair of the INFORMS 2015 Annual Meeting, a former Chair of INFORMS’ Optimization Society, Chair of the ICCOPT Steering Committee of the Mathematical Optimization Society, Chair of the SIAM AG Optimization, and Vice President of INFORMS. He received the MITACS Mentorship Award; Award of Merit of the Canadian Operational Research Society, Egerváry Award of the Hungarian Operations Research Society, H.G. Wagner Prize of INFORMS, Outstanding Innovation in Service Science Engineering Award of IISE. He is Fellow of INFORMS, SIAM, IFORS, The Fields Institute, and elected Fellow of the Canadian Academy of Engineering. He was a Plenary Speaker at ISMP’2024 in Montreal.