# A Quantum Interior Point Method for LPs and SDPs

arXiv: https://arxiv.org/abs/1808.09266 · HTML: https://mlsanity.com/paper/1808.09266/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2018.

## Built on by (most cited first, 17 of 17)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Quantum Langevin Dynamics for Optimization](https://mlsanity.com/paper/2311.15587/) (2023)
- [Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games](https://mlsanity.com/paper/2304.14197/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Noisy intermediate-scale quantum algorithm for semidefinite programming](https://mlsanity.com/paper/2106.03891/) (2021)
- [Quantum thermodynamics and semi-definite optimization](https://mlsanity.com/paper/2505.04514/) (2025)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Quantum algorithms for SVD-based data representation and analysis](https://mlsanity.com/paper/2104.08987/) (2021)
- [Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems](https://mlsanity.com/paper/2502.11173/) (2025)
- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems](https://mlsanity.com/paper/2508.09103/) (2025)
- [Quantum diffusion map for nonlinear dimensionality reduction](https://mlsanity.com/paper/2106.07302/) (2021)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [On Quantum Perceptron Learning via Quantum Search](https://mlsanity.com/paper/2503.17308/) (2025)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit](https://mlsanity.com/paper/2510.06925/) (2025)

## Abstract (arXiv)

We present a quantum interior point method with worst case running time widetildeO(fracn2.5xi2 μ kappa3 log (1/ε)) for SDPs and widetildeO(fracn1.5xi2 μ kappa3 log (1/ε)) for LPs, where the output of our algorithm is a pair of matrices (S,Y) that are ε-optimal xi-approximate SDP solutions. The factor μ is at most √2n for SDPs and √2n for LP's, and kappa is an upper bound on the condition number of the intermediate solution matrices. For the case where the intermediate matrices for the interior point method are well conditioned, our method provides a polynomial speedup over the best known classical SDP solvers and interior point based LP solvers, which have a worst case running time of O(n6) and O(n3.5) respectively. Our results build upon recently developed techniques for quantum linear algebra and pave the way for the development of quantum algorithms for a variety of applications in optimization and machine learning.