{"id":"arxiv/2603.04540","url":"https://arxiv.org/abs/2603.04540","tags":["quant-ph","math-ph"],"score":0,"title":"Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry","domain":"quant-ph","source":"arxiv","authors":["Maximilian J. Kramer","Carsten Schubert","Jens Eisert"],"reviews":0,"subject":"quant-ph","summary":"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} \\neq \\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.…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-04","reactions":{}}