Presentation: Speaker:              Tamás Terlaky
Alcoa Endowed Chair Professor.
Quantum Computing Optimization Laboratory,
Department of Industrial and Systems Engineering
Lehigh University, Bethlehem, PA, USA

Title:
Quantum Interior Point Methods (QIPMs) with Iterative Refinement for Linear and Semidefinite Optimization
 
Abstract:

QIPMs build on classic polynomial time IPMs. In QIPMs we apply Quantum Linear System Algorithms (QLSAs) to solve 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 by default are inexact infeasible methods.  We also discuss “quantum inspired‘’ Inexact-Feasible IPMs (IF-IPMs) 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 (IR) schemes to find optimal solutions without excessive calls to QLSAs. Notably, the IR-IPM scheme enjoys quadratic convergence of the optimality gap.

***************************************************************
Tamás Terlaky, Alcoa Endowed Chair Professor.
Fellow of: IFORS, Canadian Academy of Engineering, SIAM, INFORMS, Fields Institute 
Editor in Chief of JOTA
Department of Industrial and Systems Engineering, RCEAS
Lehigh University, Harold S. Mohler Laboratory
200 West Packer Avenue, Bethlehem, PA 18015-1582
Phone: (610) 758-2903    Fax: (610) 758-4886
Email: terlaky@lehigh.edu
http://www.lehigh.edu/~tat208
http://coral.ie.lehigh.edu/~mopta