Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
Die Arbeit beweist unter der Annahme , dass das Problem max-LINSAT nicht besser als der Zufallsanteil approximiert werden kann, und zeigt, dass diese untere Schranke exakt mit dem Grenzwert der Decodierbarkeit in der quantenmechanischen Interferometrie übereinstimmt, wodurch die Grenze zwischen worst-case-Härte und potenziellem Quantenvorteil definiert wird.