Practical lower bounds for hybrid quantum interior point methods in linear programming
A rigorous benchmark finds quantum interior point methods offer no practical speedup over classical LP solvers for any realistic problem today.
The Thesis
Quantum interior point methods (QIPMs) have been a leading candidate for near-term quantum advantage in optimization — the idea being that a quantum computer could solve the linear algebra steps inside classical optimization routines faster than any classical machine. This paper puts that idea to a concrete test, comparing quantum runtime lower bounds against the open-source classical solver HiGHS across eight diverse families of linear programming problems. The result is uniformly negative: even under highly generous assumptions about quantum hardware, the quantum approach is slower than HiGHS on every single instance tested. The catch is not a flaw in quantum theory — it is the overhead reality of quantum linear solvers, which require many more operations per step than their asymptotic complexity suggests.
Catalyst
HiGHS has matured into a genuinely fast, open-source classical solver, raising the bar that any quantum method must clear. Simultaneously, the field has developed 'hybrid benchmarking' frameworks — pioneered by Cade et al. — that allow rigorous, fair lower-bound comparisons between quantum and classical runtimes without requiring a physical quantum computer. These two developments together make it possible, for the first time, to definitively exclude practical quantum advantage rather than merely speculate about it.
What's New
Earlier work on QIPMs (notably by Mohammadisiahroudi et al.) proposed specific Newton system formulations and claimed polynomial asymptotic speedups. The prior hybrid benchmarking approach by Cade et al. established the methodology for rigorous runtime comparison, but applied it to a narrower set of problems. This paper extends that methodology to a much broader and more diverse benchmark suite — including MIPlib instances and combinatorial optimization relaxations — and equips the quantum pipeline with the best-known functional quantum linear solver (a Chebyshev-based method identified by Lefterovici et al.), making the exclusion result more general and harder to argue around.
The Counter
This paper tests a specific pipeline: hybrid QIPMs using quantum linear solvers on current-era LP problem structures. It does not address future fault-tolerant quantum computers running fundamentally different algorithms — the exclusion is bound to today's best-known hybrid approach, not all possible quantum optimization methods. The benchmark instances, while broad, are drawn from classical OR libraries and may not represent the problem structures where quantum methods could eventually shine. The Chebyshev-based quantum linear solver used is the best currently available, but quantum linear solver research is active — a substantially better QLSA could shift the comparison. Finally, the paper's lower bounds are derived under 'highly benevolent assumptions,' meaning they favor the quantum side; in practice, quantum hardware overhead is even worse, which actually strengthens the paper's conclusion rather than weakening it, but a proponent could argue the analysis still doesn't account for radically different hardware paradigms not yet invented.
Longs
- IONQ — longer timeline to LP-relevant quantum advantage clarifies near-term revenue expectations
- RGTI (Rigetti Computing) — same reality check applies across gate-based quantum hardware plays
- QTUM (quantum computing ETF) — sector-wide timeline recalibration
- IBM — classical HPC and optimization software business faces no near-term quantum disruption
Shorts
- Quantum hardware startups pitching near-term optimization advantage — this paper provides a concrete, citable rebuttal to those claims
- Enterprise software vendors marketing 'quantum-ready' optimization products — customer skepticism will increase as results like this circulate
Enablers (Picks & Shovels)
- HiGHS open-source LP solver (https://highs.dev) — the classical baseline that set the bar in this study
- MIPlib benchmark library — the standard public LP/MIP test suite used for evaluation
- Chebyshev-based quantum linear solver (Lefterovici et al.) — the best-performing QLSA identified in the paper
- Hybrid benchmarking methodology (Cade et al.) — the rigorous framework enabling this kind of exclusion analysis
Private Watchlist
- Quantinuum — active in quantum algorithms research; this result affects their optimization roadmap
- Q-NEXT (DOE quantum center) — national lab research into fault-tolerant thresholds needed to close this gap
- Gurobi Optimization — private classical solver vendor; near-term competitive moat reinforced
Resources
The Paper
Quantum interior point methods (QIPMs) promise polynomial speed-ups over classical solvers for linear programming by outsourcing the solution of Newton linear systems to quantum linear solvers (QLSAs). However, asymptotic speed-ups do not necessarily translate to practical advantages on realistic problem instances. In this work, I evaluate whether practical advantage of a standard hybrid QIPM pipeline can already be excluded relative to the classical open-source solver HiGHS on a broad and diverse collection of LP instances spanning eight problem families, including public benchmark libraries, such as MIPlib, and relaxations of combinatorial optimisation problems. Following the hybrid benchmarking paradigm initiated by Cade et al., I derive rigorous lower bounds on the quantum runtime under a series of highly benevolent assumptions and compare them against classical runtimes. I equip the QIPMs with the best-performing functional QLSA, the Chebyshev-based method, as identified by Lefterovici et al., and evaluate two Newton system formulations proposed by Mohammadisiahroudi et al.: the modified normal equation system and the orthogonal subspace system. The exclusion analysis yields a consistent negative picture: across all instances and for any realistic quantum cycle duration, the quantum runtime lower bounds already exceed the classical runtimes, establishing that these hybrid QIPMs will offer no practical advantage over good classical solvers for realistic linear programming instances.