A preconditioned inexact infeasible quantum interior point method for linear optimization
Open Access
- 28 November 2025
- journal article
- research article
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 93 (3) , 1225-1257
Abstract
Quantum Interior Point Methods (QIPMs) have been attracting significant interests recently due to their potential of solving optimization problems substantially faster than state-of-the-art conventional algorithms. In general, QIPMs use Quantum Linear System Algorithms (QLSAs) to substitute classical linear system solvers. However, the performance of QLSAs depends on the condition numbers of the linear systems, which are typically proportional to the square of the reciprocal of the duality gap in QIPMs. To improve conditioning, a preconditioned inexact infeasible QIPM (II-QIPM) based on optimal partition estimation is developed in this work. We improve the condition number of the linear systems in II-QIPMs from quadratic dependence on the reciprocal of the duality gap to linear, and obtain better dependence with respect to the accuracy when compared to other II-QIPMs. Our method also attains better dependence with respect to the dimension when compared to other inexact infeasible Interior Point Methods.Keywords
All Related Versions
Funding Information
- Defense Advanced Research Projects Agency (W911NF2010022)
- National Science Foundation (CAREER DMS-2143915)
- U.S. Department of Energy (DE-AC05-00OR22725)
This publication has 25 references indexed in Scilit:
- Efficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear OptimizationJournal of Optimization Theory and Applications, 2024
- Matrix Analysis2012
- Interior Point Methods for Nonlinear Optimization2010
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear OptimizationJournal of Optimization Theory and Applications, 2008
- Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programmingComputational Optimization and Applications, 2007
- Degeneracy in interior point methods for linear programming: a surveyAnnals of Operations Research, 1993
- Some interlacing properties of the Schur complement of a Hermitian matrixLinear Algebra and its Applications, 1992
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- An identity for the Schur complement of a matrixProceedings of the American Mathematical Society, 1969