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

CREATORLennart Binkowski 1
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47345
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.24362

Browse the full library · About the Tower of Babel