Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914412780060672 |
|---|---|
| author | Kramer, Maximilian J. Schubert, Carsten Eisert, Jens |
| author_facet | Kramer, Maximilian J. Schubert, Carsten Eisert, Jens |
| contents | 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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04540 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry Kramer, Maximilian J. Schubert, Carsten Eisert, Jens Quantum Physics Mathematical Physics 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. 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. |
| title | Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry |
| topic | Quantum Physics Mathematical Physics |
| url | https://arxiv.org/abs/2603.04540 |