This Quantum Optimization Advantage Is Proven—and Deliberately Narrow

A new preprint puts a proof behind one carefully defined kind of quantum optimization advantage. The authors show that decoded quantum interferometry, or DQI, can achieve an approximation score that no polynomial-time classical algorithm can match with only polynomially many membership queries on their folded optimal polynomial intersection problem.^[1]

The result is striking because it is not merely a comparison with the best classical heuristic the authors happened to test. It includes a classical lower bound inside the same query model. That turns an observed gap into a theorem—but only for the structured, randomly sampled acceptance sets and membership-oracle access that the theorem defines.^[1]

At code rate 0.3, the paper gives the cleanest numerical picture. A classical information-set strategy reaches a score threshold of 0.65. DQI approaches an expected score of about 0.8571 on every promised instance, while exceeding the classical threshold by any fixed amount with constant probability requires super-polynomially many classical membership queries.^[1]

DQI connects optimization to error-correcting codes. In broad terms, a quantum circuit interferes over candidate codewords and uses a coherent decoder for the dual code to concentrate probability on candidates satisfying more constraints. The original DQI framework established strong approximation guarantees; this new work supplies an oracle setting in which the advantage over arbitrary classical algorithms can be proved.^[1][2]

The paper also describes a stronger modified quantum method. At the same 0.3 rate, its score envelope is about 0.9583, but that statement applies to a large fraction of randomly sampled instances rather than every promised instance. That distinction matters: the 0.8571 DQI guarantee and the stronger typical-instance result do not carry the same quantifiers.^[1]

The oracle is the largest boundary around the claim. A membership oracle answers whether a candidate symbol belongs to a hidden acceptance set without requiring the algorithm to construct or store that set in an ordinary input format. Query separations are valuable evidence about what quantum interference can do, but they do not automatically become speedups for logistics, finance or scheduling data loaded from conventional databases.^[1]

Nothing in this preprint reports a run on a quantum processor. It is also an October 1 preprint rather than a peer-reviewed experimental paper. Its contribution is theoretical clarity: a specific approximation task, a common oracle model, a quantum guarantee and a classical lower bound that meet in one proof.^[1]

The next step is to shrink the distance between the theorem and an executable workload. Useful evidence would include resource estimates for fault-tolerant circuits, input models that resemble real optimization data and classical algorithms allowed to exploit the same structure. Until then, the honest headline is still meaningful: quantum optimization now has another provable advantage, and the proof tells readers exactly where it lives.^[1][2]