Improvements to Quantum Interior Point Method for Linear Optimization
Quantum linear system algorithms (QLSA) have the potential to speed up
Interior Point Methods (IPM). However, a major challenge is that QLSAs are
inexact and sensitive to the condition number of the coefficient matrices of
linear systems. This sensitivity is exacerbated when the Newton systems arising
in IPMs converge to a singular matrix. Recently, an Inexact Feasible Quantum
IPM (IF-QIPM) has been developed that addresses the inexactness of QLSAs and,
in part, the influence of the condition number using iterative refinement.
However, this method requires a large number of gates and qubits to be
implemented. Here, we propose a new IF-QIPM using the normal equation system,
which is more adaptable to near-term quantum devices. To mitigate the
sensitivity to the condition number, we use preconditioning coupled with
iterative refinement to obtain better gate complexity. Finally, we demonstrate
the effectiveness of our approach on IBM Qiskit simulators
Mohammadhossein Mohammadisiahroudi Zeguan Wu Brandon Augustino Arriele Carr Tamás Terlaky