An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
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 com...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-02-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/2/330 |
| _version_ | 1797621071133802496 |
|---|---|
| author | Zeguan Wu Mohammadhossein Mohammadisiahroudi Brandon Augustino Xiu Yang Tamás Terlaky |
| author_facet | Zeguan Wu Mohammadhossein Mohammadisiahroudi Brandon Augustino Xiu Yang Tamás Terlaky |
| author_sort | Zeguan Wu |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mo>ℓ</mo><mn>1</mn></msub></semantics></math></inline-formula>-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. |
| first_indexed | 2024-03-11T08:51:28Z |
| format | Article |
| id | doaj.art-0a96785430f14f65827ce9f9bd9cbce7 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-11T08:51:28Z |
| publishDate | 2023-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-0a96785430f14f65827ce9f9bd9cbce72023-11-16T20:24:00ZengMDPI AGEntropy1099-43002023-02-0125233010.3390/e25020330An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic OptimizationZeguan Wu0Mohammadhossein Mohammadisiahroudi1Brandon Augustino2Xiu Yang3Tamás Terlaky4Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USADepartment of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USADepartment of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USADepartment of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USADepartment of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USAQuantum 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mo>ℓ</mo><mn>1</mn></msub></semantics></math></inline-formula>-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.https://www.mdpi.com/1099-4300/25/2/330quantum computinginterior point methodquadratic optimization |
| spellingShingle | Zeguan Wu Mohammadhossein Mohammadisiahroudi Brandon Augustino Xiu Yang Tamás Terlaky An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization Entropy quantum computing interior point method quadratic optimization |
| title | An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization |
| title_full | An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization |
| title_fullStr | An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization |
| title_full_unstemmed | An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization |
| title_short | An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization |
| title_sort | inexact feasible quantum interior point method for linearly constrained quadratic optimization |
| topic | quantum computing interior point method quadratic optimization |
| url | https://www.mdpi.com/1099-4300/25/2/330 |
| work_keys_str_mv | AT zeguanwu aninexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT mohammadhosseinmohammadisiahroudi aninexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT brandonaugustino aninexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT xiuyang aninexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT tamasterlaky aninexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT zeguanwu inexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT mohammadhosseinmohammadisiahroudi inexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT brandonaugustino inexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT xiuyang inexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization AT tamasterlaky inexactfeasiblequantuminteriorpointmethodforlinearlyconstrainedquadraticoptimization |