Optimal Scaling Quantum Interior Point Method for Linear Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911303525728256 |
|---|---|
| author | Mohammadisiahroudi, Mohammadhossein Wu, Zeguan Sampourmahani, Pouya You, Jun-Kai Terlaky, Tamás |
| author_facet | Mohammadisiahroudi, Mohammadhossein Wu, Zeguan Sampourmahani, Pouya You, Jun-Kai Terlaky, Tamás |
| contents | The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of $\mathcal{O}(n^2)$ for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of $\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$ queries to QRAM and $\mathcal{O}(n^2 \log(\frac{1}ε))$ classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04510 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Scaling Quantum Interior Point Method for Linear Optimization Mohammadisiahroudi, Mohammadhossein Wu, Zeguan Sampourmahani, Pouya You, Jun-Kai Terlaky, Tamás Quantum Physics 90C51, 90C05, 81P68 The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of $\mathcal{O}(n^2)$ for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of $\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$ queries to QRAM and $\mathcal{O}(n^2 \log(\frac{1}ε))$ classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency. |
| title | Optimal Scaling Quantum Interior Point Method for Linear Optimization |
| topic | Quantum Physics 90C51, 90C05, 81P68 |
| url | https://arxiv.org/abs/2512.04510 |