Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Dit artikel stelt vast dat het benaderen van bounded-degree max-LINSAT over willekeurige eindige velden voorbij een additieve factor NP-hard is, waarmee het een complexiteitstheoretische benchmark vastlegt die de potentiële kwantumvoorsprong beperkt tot constante prefactoren en kwantumdecodering identificeert als het essentiële onderdeel om gedecodeerde kwantuminterferometrie met deze optimale schaling te laten evenaren.