Practical lower bounds for hybrid quantum interior point methods in linear programming
Lennart Binkowski 1 · 2026
Read Practical lower bounds for hybrid quantum interior point methods in linear programming by Lennart Binkowski 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24362.txt.
Description
Binkowski tests whether hybrid quantum interior point methods can beat the HiGHS solver on realistic linear programming problems. Quantum methods promise polynomial speedups by handing Newton systems to quantum solvers, but speedups need not mean practical gains. Using a hybrid benchmarking approach with the best Chebyshev solver, he derives lower bounds on quantum runtime under generous assumptions. Across eight problem families, including MIPlib, quantum lower bounds exceed classical runtimes for any realistic cycle duration. The verdict is negative: these hybrid methods offer no practical advantage over classical solvers.
Catalog record
| CREATOR | Lennart Binkowski 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47345 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24362