A provable quantum advantage for approximate optimization via decoded quantum interferometry

The 30-second take

• What: The authors prove that decoded quantum interferometry (DQI) achieves a strictly better approximation ratio than any polynomial-time classical algorithm on a folded optimal polynomial intersection task with random acceptance sets and membership oracles.
• Why it matters: Most quantum-optimization talks lack a proof versus all efficient classical algorithms; a clean oracle gap is a scarce theoretical asset, not a near-term product.
• Who should care: Quantum algorithms and complexity theorists, and anyone who needs to tell oracle separations from hardware-ready speedups.

What the paper actually did

Decoded quantum interferometry (DQI) is a framework for approximate optimization on quantum computers, with performance guarantees and a duality between optimization and coding theory. The open question the authors take up is whether DQI can provably beat all polynomial-time classical algorithms. They give an oracle separation on folded optimal polynomial intersection (folded OPI), where acceptance sets are random and accessed by membership oracles. They prove a strict gap between the approximation ratio any polynomial-time classical algorithm can achieve and the ratio DQI achieves. The proof uses Jordan et al.’s DQI framework and extends the classical lower-bound method behind Yamakawa and Zhandry’s exact-search oracle separation to the approximation setting. Building on Sun and Wootters, Horinaga and Yamakawa, and Jo, a modified DQI algorithm widens the gap. As a concrete example, at code rate 0.3, DQI and the modified algorithm get expected scores of about 0.85 and 0.95, while exceeding the classical threshold of 0.65 by any fixed amount with constant probability on sampled instances needs super-polynomially many classical membership queries.

What makes this disruptive

A proven gap versus all polynomial-time classical algorithms is rarer than a heuristic quantum-optimization plot. Extending an exact-search oracle separation to approximation, then widening it with a modified DQI algorithm, is a clean complexity result. The rate-0.3 numbers (0.85 / 0.95 versus 0.65 with super-polynomial classical queries) make the gap quantitative. For abundance, this is long-horizon: it says there exist optimization-shaped problems where a quantum algorithm is provably better in an oracle world. It does not say today’s hardware solves folded OPI or that logistics software should switch.

Why it matters (outside the lab)

Abundance lens: some hard optimization capabilities are elite. A proven quantum approximation advantage is a brick in the wall of making those capabilities less mysterious — but the brick is theoretical. Horizon is long, and the setting is oracles, not a consumer default. Near-term, use it to update what “DQI advantage” means in talks. Medium-term, derandomizing or de-oraclizing the problem is the path toward anything default.

Limitations & open questions

The advantage is in an oracle setting with random acceptance sets and membership queries — not an explicit, unstructured industrial instance. Super-polynomial classical query lower bounds do not automatically imply a practical wall once the oracle is implemented as a circuit. Expected scores ~0.85 and ~0.95 are for a stated code rate 0.3 example, not every rate. “Any polynomial-time classical algorithm” is with respect to this oracle model. No hardware experiment is claimed. Preprint; check the extension of Yamakawa–Zhandry and the modified-DQI citations before quoting the larger gap.