An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
Open Access
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 -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.
Keywords
All Related Versions
Funding Information
- Defense Advanced Research Projects Agency (W911NF2010022, CAREER DMS-2143915)
- National Science Foundation (W911NF2010022, CAREER DMS-2143915)
This publication has 19 references indexed in Scilit:
- Prediction by linear regression on a quantum computerPhysical Review A, 2016
- Quantum Support Vector Machine for Big Data ClassificationPhysical Review Letters, 2014
- Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic ProgrammingSIAM Journal on Optimization, 2013
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- An Iterative Solver-Based Infeasible Primal-Dual Path-Following Algorithm for Convex Quadratic ProgrammingSIAM Journal on Optimization, 2006
- Support-vector networksMachine Learning, 1995
- An O(n 3 L) primal interior point algorithm for convex quadratic programmingMathematical Programming, 1990
- Interior path following primal-dual algorithms. part II: Convex quadratic programmingMathematical Programming, 1989
- A polynomial-time algorithm for a class of linear complementarity problemsMathematical Programming, 1989
- Direct Methods for Solving Symmetric Indefinite Systems of Linear EquationsSIAM Journal on Numerical Analysis, 1971