Revision 1

Superseded · first revision · record

Title: Can classical algorithms match decoded quantum interferometry on polynomial intersection
Plain: Most quantum methods for hard optimization problems give only modest speedups. A quantum method called decoded quantum interferometry finds better approximate solutions to a structured problem than any known classical method, and it is open whether a classical method can catch up.
Precise: Optimal Polynomial Intersection (OPI): given a prime $p$, points $x_{1}..x_{m}$ in $F_{p}$ and subsets $S_{i}$ of $F_{p}$, find a polynomial $Q$ over $F_{p}$ of $\mathrm{degree}<n$ maximizing the number of $i$ with $Q(x_{i})$ in $S_{i}$. For the parameter families of Jordan et al. (Nature 646, 831, 2025, arXiv:2408.08292), decoded quantum interferometry reaches a satisfied fraction (given by a semicircle-law formula) above that of every known polynomial-time classical algorithm. Answer: a classical polynomial-time algorithm achieving the same fraction, or a hardness proof under a standard complexity assumption.
Settled by: A classical algorithm matching the DQI fraction on the stated OPI families, or a reduction showing that doing so would break a standard assumption.
Kind: well-posed
Answer type: yes-no
References: (empty)
Literature status: open
Status note: 2025-2026 work gave faster DQI implementations and inapproximability results for related max-LINSAT problems; no classical match for OPI has been reported.
Posed since: 2024