An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
Abstract
Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to ℓ1-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 10, 2023
- Source ID
- 10.3390/e25020330
Entities
People
- Brandon Augustino
- Mohammadhossein Mohammadisiahroudi
- Tamás Terlaky
- Xiu Yang
- Zeguan Wu
Organizations
- Defense Advanced Research Projects Agency
- Lehigh University
- National Science Foundation