Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
本論文は、任意の有限体における有界次数max-LINSATをの加法的因子を超えて近似することがNP困難であることを確立しており、それによって量子的な優位性が定数倍の係数内に限定されることを制約する計算量理論的なベンチマークを設定し、デコードされた量子干渉法がこの最適なスケーリングに一致するためには量子復号が不可欠な要素であることを特定している。