Quantum Interior Point Methods (QIPMs) build on classic polynomial time IPMs. With the emergence of quantum computing we apply Quantum Linear System Algorithms (QLSAs) to Newton systems within IPMs to gain quantum speedup in solving Linear Optimization (LO) and Semidefinite Optimization (SDO) problems. Due to their inexact nature, QLSAs mandate the development of inexact variants of IPMs which, due to the inexact nature f their computations, by default are inexact infeasible methods. We propose “quantum inspired‘’ Inexact-Feasible IPMs (IF-IPM) for LO and SDO problems, using novel Newton systems to generate inexact but feasible steps. We show that IF-QIPMs enjoys the to-date best iteration complexity. Further, we explore how QLSAs can be used efficiently in iterative refinement schemes to find optimal solutions without excessive calls to QLSAs. Finally, we experiment with the proposed IF-IPM’s efficiency using IBMs QISKIT environment.

Speaker Bio:

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

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 Society, Egerváry Award of the Hungarian Operations Research Society, H.G. Wagner Prize of INFOMRS, 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 will be a Plenary Speaker at ISMP’2024 in Montreal.