Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
이 논문은 임의의 유한체에 대해 차수가 유계인 max-LINSAT을 의 가산 인자 이상으로 근사하는 것이 NP-난해임을 입증함으로써, 잠재적인 양자 이득을 상수 전계수로 국한시키는 복잡도 이론적 벤치마크를 설정하고, 디코딩된 양자 간섭계가 이러한 최적 스케일링에 도달하기 위해 양자 디코딩이 필수적인 구성 요소임을 식별한다.