No. 03 · The observatory
Proven ceilings for optimisation claims
Six results turn old guesses about optimisation limits into theorems. Use them to test vendor claims.
- Status
- Open
- Families
- 102, 117, 125, 281; also 096 and 229, with no product found
- Verification
- Lean checks on most headline proofs. The 117 hardness proof is unchecked.
- Time to market
- None. They confirm limits practice already assumed.
- Best use
- Vendor diligence
What did the Unique Games proof change?
Leave your solver stack alone. Keep the theorem handy for vendor pitches.
The release’s biggest claim is a proof of the Unique Games Conjecture.
For twenty years, experts called it almost certainly true. Now it is proven, unless P=NP. It fixes worst-case limits for optimisation software. It changes no product and no cost line.
Practitioners already behaved as if these limits held. They buy solvers on results for their own instances. Worst-case guarantees rarely drive the purchase.
Scott Aaronson says “we’re pretty sure that it’s a proof.” A Lean certificate backs that confidence. Few humans have read the proof, though. Mark Braverman warns: “Math by press release is not that healthy for math.”
What is a worst-case ceiling, in plain terms?
Judge optimisation tools on your own data. Worst-case ceilings say little about typical inputs.
Many business problems are NP-hard.
Routing, scheduling, network splitting and clustering all fall in this class. Theorists expect no fast method to find the exact best answer every time. So software settles for an answer that is approximately best.
Theory asks how close a fast method can guarantee to get. It measures that on the worst possible input. These papers pin that number down for several classic problems.
Typical inputs behave very differently. Heuristics and solvers often get within a fraction of a percent. A ceiling on the worst case says nothing about them.
Which vendor claims now contradict a theorem?
Flag any “provably better worst-case” pitch on Max-Cut, Vertex Cover or sparsest cut.
A few worst-case promises now contradict a proven theorem.
The release proves these limits:
- Max-Cut (102): no fast method can beat the 0.878 ratio on every instance.
- Vertex Cover (102): no fast method can guarantee better than factor 2.
- Sparsest cut (117): no constant-factor guarantee is possible. Its main hardness proof lacks a Lean check.
- k-median (125): a new algorithm reaches about 1.74, matching known hardness. Facility planning still uses solvers.
- Kernel clustering (096): a geometry result makes one guarantee NP-hard to improve. No product sells that guarantee.
- Community detection (229): it fixes when three-community structure becomes detectable. Real networks do not follow this model.
Quantum vendors fall under the same limits. Theorists widely believe quantum computers cannot solve NP-hard problems efficiently either. No theorem proves that belief yet.
The honest pitch was always the same. A vendor should be better on your instances. It should beat a strong classical baseline.
Across the whole release, 12 families are proven limits like these.
Proven limits lead the 40 results that touch business
Result families with any business pathway, by primary mechanism. 40 families.
- Families
How to readEach bar counts families whose main effect runs through that mechanism.
NoteA close read moved 11 of 25 pathway families to none. So 40 is a ceiling.
SourceOur labels, data/cards.json
Does the QAOA result prove quantum advantage?
Reject family 281 as evidence of quantum advantage. It shows eventual parity on one benchmark.
Marketers are most likely to misuse this result.
It proves a quantum algorithm, QAOA, eventually reaches the optimum on a random benchmark. The proof makes the quantum circuit imitate a classical algorithm. Montanari’s classical method already gets within (1-ε) of the optimum in polynomial time.
The paper admits “no quantitative bound on the required depth.” So QAOA can eventually match a classical method here. It never beats one. It does settle an open question that JPMorganChase’s research group studied numerically.
What should each buyer do now?
Name your instances, a classical baseline and a wall-clock limit in every optimisation RFP.
Most readers need no action on these theorems.
- Buyers of optimisation services: write RFPs around your own instances and a named classical baseline. Measure wall-clock time.
- Quantum vendors and investors: do not cite 281 as advantage evidence. It has no depth bound.
- Optimisation software builders: keep your roadmap. The limits you assumed are now theorems.
- Everyone else: nothing to do on these theorems. They tighten the record without moving a cost line.
Will any buyer change behaviour? Probably not. A sophisticated buyer already ignored worst-case pitches. A naive buyer now has a citable theorem to push back with.
These limits matter more as AI vendors pitch optimisation. Google has sold AlphaEvolve on Google Cloud since 2026-07-09. Check any such pitch against the 12 proven limits, and ask for machine-check status.