Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Diese Arbeit stellt fest, dass die Approximation von bounded-degree max-LINSAT über beliebige endliche Körper über einen additiven Faktor von hinaus NP-hart ist, wodurch ein komplexitätstheoretischer Referenzpunkt gesetzt wird, der den potenziellen Quantenvorteil auf konstante Präfaktoren begrenzt und das Quantendekodieren als die essenzielle Komponente identifiziert, damit dekodierte Quanteninterferometrie diese optimale Skalierung erreicht.