Can classical algorithms match decoded quantum interferometry on polynomial intersection? · revision history

Revision 2

Accepted · cosmetic change · record

Changes against revision 1:

Title · changed
Revision 1: Can classical algorithms match decoded quantum interferometry on polynomial intersection
Revision 2: 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

Decisions