Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry

Abstract

We establish tight inapproximability bounds for max-LINSAT, the problem of maximizing the number of satisfied linear constraints over the finite field ${\mathbb{F}}_q$, where each constraint accepts $r$ values. Specifically, we prove by a direct reduction from HÃ¥stad's theorem that no polynomial-time algorithm can exceed the random-assignment ratio $r/q$ by any constant, assuming $\mathsf{P}\ne \mathsf{NP}$. This threshold coincides with the $\ell /m\to 0$ limit of the semicircle law governing decoded quantum interferometry (DQI), where $\ell$ is the decoding radius of the underlying code. Together, these observations delineate the boundary between worst-case hardness and potential quantum advantage, showing that any algorithm surpassing $r/q$ must exploit instance structure beyond what is present in the hard instances produced by PCP reductions.

11 pages, 1 figure, minor changes