{"id":"arxiv/2606.13570","url":"https://arxiv.org/abs/2606.13570","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Approximability limits for bounded-degree 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":"For general max-k-XORSAT with $k \\geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\\mathsf{P} = \\mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-11","reactions":{}}