We apply Quantum Linear System Algorithms (QLSAs) to Newton systems within IPMs to gain quantum speedup in solving LO problems. Due to their inexact nature, QLSAs can be applied only to inexact variants of IPMs, which are inexact infeasible methods due to the inexact nature f their computations. We propose Inexact-Feasible IPMs (IF-IPM) for LO and SDO problems, using novel Newton systems to generate inexact but feasible steps. We show that this method enjoys the to-date best iteration complexity. Further, we explore how QLSAs can be used efficiently in iterative refinement schemes to find an exact optimal solution without excessive calls to QLSAs. Finally, we experiment with the proposed IF-IPM’s efficiency using IBMs QISKIT environment.

Bio of the Speaker:

Dr. Terlaky is a George N. and Soteria Kledaras ’87 Endowed Chair Professor Department of Industrial and Systems Engineering, Lehigh University, and Director of the Quantum Computing Optimization Laboratory.

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 operations research, computational optimization, nuclear reactor core reloading optimization, oil refinery and VLSI design optimization, robust radiation therapy treatment optimization, inmate assignment optimization, quantum computing.

His research interest includes high performance optimization methods, optimization modeling, optimization problems in engineering sciences and service systems, and quantum computing 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. 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. Currently he is serving as Vice President of INFORMS.