Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Questo articolo stabilisce che approssimare il max-LINSAT a grado limitato su campi finiti arbitrari oltre un fattore additivo di è NP-difficile, stabilendo così un parametro di riferimento della complessità teorica che confina il potenziale vantaggio quantistico a fattori pre-costanti e identifica la decodifica quantistica come la componente essenziale affinché l'interferometria quantistica decodificata raggiunga questa scalabilità ottimale.