An Almost-exact Quantum Interior Point Method for Linear Optimization Achieving Optimal Scaling

Recent advances in quantum computing, particularly quantum linear system solvers, offer potentials to improve the complexity of Interior Point Methods to solve linear and conic optimization problems. However, practical challenges such as quantum error, hardware noise, high cost of Tomography and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) have been developed to address these challenges. In this work, we propose a novel almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum, enabling the method to achieve an optimal worst-case scalability (oracle compelxity) w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations.