Improvements to Quantum Interior Point Method for Linear Optimization

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino, Arielle Carr, Tamás TerlakyACM Trans. Quantum Comput 2025 · DOI

TL;DR

This paper proposes an improved quantum algorithm for solving linear optimization problems by modifying the standard "normal equation system" (NES) to be more suitable for near-term quantum computers. By combining this modified NES with iterative refinement and preconditioning techniques, the authors demonstrate a significant reduction in the algorithm's sensitivity to the condition number of the problem, leading to better performance and adaptability for quantum hardware.

What Problem Does This Paper Address?

Linear optimization (LO) problems are fundamental in many scientific and engineering fields, but solving large-scale LO problems can be computationally challenging. Interior Point Methods (IPMs) are a powerful class of algorithms for LO, but their efficiency relies on solving large linear systems at each iteration. Quantum algorithms, specifically Quantum Linear System Algorithms (QLSAs), offer the potential for speedups in solving these systems. However, existing quantum IPMs (QIPMs) face challenges due to the inexactness of QLSAs and their sensitivity to the "condition number" of the linear systems, which can lead to infeasibility or slow convergence. This paper aims to address these limitations by developing a more robust and efficient QIPM that is better suited for current and near-future quantum hardware.

Methods

The core of this work lies in modifying the Newton system used within IPMs. Instead of the standard "Full Newton System" (FNS) or "Augmented System" (AS), the authors focus on the "Normal Equation System" (NES). They propose a modified NES (MNES) that is symmetric and positive definite, making it more amenable to quantum solvers and classical preconditioning techniques.

Key methodological contributions include:

  • Modified Normal Equation System (MNES): This system is designed to be smaller and have better structural properties than other Newton systems, making it more efficient for quantum computation.
  • Iterative Refinement (IR): This classical technique is incorporated to exponentially improve the precision of the solution and reduce the dependence on the condition number bound.
  • Preconditioning: This classical technique is applied to the MNES to mitigate the impact of ill-conditioned matrices, further enhancing robustness.
  • QLSA+QTA Integration: The paper leverages existing Quantum Linear System Algorithms (QLSAs) and Quantum Tomography Algorithms (QTAs) to solve the modified Newton systems on a quantum computer.

Datasets

Not discussed in the paper. The authors mention using "randomly generated Linear Optimization Problems (LOPs)" for their experiments, controlled by parameters like the condition number.

Key Insights and Ideas

  • NES is Quantum-Friendly: The Normal Equation System (NES), particularly when modified, offers a better structure for quantum linear system solvers compared to other Newton system formulations. This is because it's symmetric and positive definite, which is a requirement for many quantum algorithms.
  • Classical Techniques Enhance Quantum Algorithms: Iterative refinement and preconditioning, classical methods for improving numerical stability and convergence, are shown to be highly effective in boosting the performance of quantum IPMs. They don't just improve classical IPMs; they directly address the weaknesses of quantum solvers.
  • Near-Term Adaptability: The proposed MNES is smaller than other systems, requiring fewer qubits and gates, making it more practical for current quantum hardware limitations.
  • Condition Number is the Bottleneck: The paper consistently highlights the condition number as a major challenge for both classical and quantum optimization algorithms. Their work directly targets this issue.

Key Results

  • The proposed Inexact-Feasible Quantum Interior Point Method (IF-QIPM) using the modified NES (MNES) is more adaptable to near-term quantum devices due to its smaller size.
  • Iterative refinement and preconditioning significantly mitigate the impact of the condition number, allowing the algorithm to solve problems with larger condition numbers.
  • The paper demonstrates that their approach can achieve a better complexity with respect to the dimension of the problem compared to classical inexact approaches.
  • Numerical experiments on the IBM Qiskit simulator showed that their method could solve problems with more variables than other OSS-based QIPMs, and iterative refinement coupled with preconditioning enabled solving problems with larger condition numbers.
  • The iterative refinement process, when applied both internally and externally, improved precision from $10^{-1}$ to $10^{-4}$ on average.

Limitations and Future Work

  • QRAM Dependency: The theoretical analysis relies on the availability of Quantum Random Access Memory (QRAM), which is not yet physically realized.
  • QLSA Capabilities: The QLSAs used are still beyond the capabilities of current quantum hardware for large-scale problems.
  • Simulation vs. Real Hardware: The numerical experiments were conducted on a simulator, and extrapolation to actual quantum hardware performance is cautioned against due to the exponential time-consuming nature of quantum simulations.
  • Future Work: The authors suggest exploring regularization techniques in the quantum setting to further address the impact of condition numbers. They also propose generalizing their method to other conic problems, such as semidefinite optimization, where Newton systems can grow quadratically.

Summary updated

BibTeX
@article{mohammadisiahroudi2025improvements,
  author = {Mohammadhossein Mohammadisiahroudi and Zeguan Wu and Brandon Augustino and Arielle Carr and Tamás Terlaky},
  title = {{Improvements to Quantum Interior Point Method for Linear Optimization}},
  journal = {ACM Trans. Quantum Comput.},
  year = {2025},
  doi = {10.1145/3702244},
}
Figure