The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound

기술 요약: 대각선 검사(Diagonal-Lines Test)가 없는 저개별 차수 검사(Low-Individual-Degree Test)는 양자적 건전성(Quantum-Soundness)을 갖지 못한다

문제 정의
본 논문은 $\text{MIP}^* = \text{RE}$ [JNV+21]의 복잡도 클래스 동일성 증명의 핵심 구성 요소인 고전적 저개별 차수 검사의 양자적 건전성에 관한 구체적인 질문을 다룬다. JNV+20[JNV+20]의 수정된 분석에 따르면, 저개별 차수 검사는 축 평행선 검사(axis-parallel lines test), 자기 일관성 검사(self-consistency test), 그리고 대각선 검사(diagonal-lines test)의 세 가지 하위 검사로 분해된다. 대각선 검사는 양자 설정에서 특정한 역할을 수행한다. 즉, 임의의 두 점과 관련된 점 측정(point measurements) 사이의 호환성 보증을 제공하는데, 이는 고전적 전역 함수(global functions)에서는 자동적으로 성립하지만 양자 측정에서는 비자명한 성질이다.

본 연구가 조사하는 핵심 질문은 대각선 검사가 엄격하게 필요한가 하는 점이다. 구체적으로, 모든 축 평행선에 대한 완벽한(또는 근사적인) 일관성과 자기 일관성 검사만으로 점 측정이 전역적으로 근사하게 교환(commute)하도록 강제하여, 전역적인 저차수 다항식 측정을 보장할 수 있는가? [JNV+20]는 매개변수 $(m, d, q) = (2, 2, 4)$에 대한 반례를 제시했지만, 이 예시는 저차수 검사의 건전성과 관련이 있는 "대형 필드 영역(large-field regime)" 즉, $d/q \to 0$인 경우를 다루지 않았다. 본 논문은 이러한 장애물이 이 점근적 영역에서도 지속되는지 조사한다.

방법론
저자는 유한체 $\mathbb{F}_q$ 위에서 (축 평행선 및 자기 일관성 검사만을 포함하는) 축소된 저개별 차수 검사에 대한 2-프로버 투영 전략(two-prover projective strategy)을 구축한다. 매개변수는 $(m, d) = (2, 2)$이며, $q$는 임의의 홀수 소수이다.

1. 힐베르트 공간 및 상태: 전략은 힐베르트 공간 $H = \mathbb{C}^{\mathbb{F}_q^3}$와 최대 얽힘 상태 $|\Phi\rangle = \frac{1}{\sqrt{q^3}} \sum_{z \in \mathbb{F}_q^3} |z\rangle \otimes |z\rangle$를 사용한다.
2. 점 측정: 각 점 $u = (x, y) \in \mathbb{F}_q^2$에 대해, 저자는 Weyl 연산자를 사용하여 점 측정 $A^u_a$를 정의한다. 이 구성은 다음과 같이 정의된 특정 라벨 함수 $w: \mathbb{F}_q^2 \to \mathbb{F}_q^3 \oplus \mathbb{F}_q^3$에 의존한다:
   $$w(x, y) = (1, y, y^2; xy^2, -2xy, x)$$
   측정 연산자는 푸리에 투영(Fourier projections)을 통해 다음과 같이 구성된다:
   $$A^u_a = \frac{1}{q} \sum_{t \in \mathbb{F}_q} \omega^{-ta} W(tw(u))$$
   여기서 $W$는 일반화된 Weyl 연산자를 나타낸다. 밥(Bob)의 측정은 앨리스(Alice)의 측정의 전치(transpose)로 정의된다.
3. 선 측정: 축 평행선 $\ell$에 대해, 전략은 $\{w(u) : u \in \ell\}$에 의해 생성되는 부분 공간 $S_\ell$을 기반으로 선 측정을 정의한다. 저자는 $S_\ell$이 심플렉틱 형식(symplectic form)에 대해 등방 부분 공간(isotropic subspace)임을 증명하며, 이는 Weyl 연산자가 해당 부분 공간 내에서 교환함을 보장한다. 이를 통해 해당 선 위의 점 측정과 일관되는 유효한 투영 측정을 구성할 수 있다.
4. 심플렉틱 성질: 라벨 $w$의 결정적인 성질은 그 심플렉틱 쌍생성(symplectic pairing)이 $\langle w(u), w(v) \rangle = (x' - x)(y' - y)^2$를 만족한다는 것이다. 이 양은 $u$와 $v$가 동일한 축 평행선(즉, $x=x'$ 또는 $y=y'$) 위에 있을 때만 0이 되며, 그렇지 않으면 0이 아니다.

주요 결과
구성된 전략은 다음 결과를 도출한다:

1. 완벽한 수용: 이 전략은 자기 일관성 검사와 축 평행선 검사를 확률 1로 통과한다. 점 측정과 선 측정은 완벽하게 정교화(refined)된다. 구체적으로, 선 측정 연산자는 해당 선 위의 점 측정 연산자를 정교하게 반영한다.
2. 전역 건전성 실패: 이러한 축 평행선 일관성에도 불구하고, 이 전략은 전역 저개별 차수 다항식 측정을 허용하지 못한다.
   • 교환자 오차(Commutator Error): 독립적인 균등 분포 점 $u, v$에 대해, 평균 상태 의존 교환자 오차는 다음과 같이 정확히 계산된다:
     $$\mathbb{E}_{u,v} \sum_{a,b} \| ([A^u_a, A^v_b] \otimes I) |\Phi\rangle \|^2 = 2 \left(1 - \frac{1}{q}\right)^3$$
     $q \to \infty$ (즉, $d/q \to 0$인 대형 필드 영역)일 때, 이 오차는 0이 아닌 2로 수렴한다.
   • 전역 측정과의 거리: 저자는 밥의 공간 상에서 결과가 함수 $g: \mathbb{F}_q^2 \to \mathbb{F}_q$인 모든 투영 측정 $G = \{G_g\}$에 대해, 구성된 전략과의 일관성이 1에서 멀리 떨어져 있음을 증명한다:
     $$\mathbb{E}_{u} \sum_{a} \sum_{g: g(u)=a} \langle \Phi | A^u_a \otimes G_g | \Phi \rangle \leq 1 - \frac{1}{16}\left(1 - \frac{1}{q}\right)^3 \leq 1 - \frac{1}{54}$$
     이 경계는 모든 홀수 소수 $q \geq 3$에 대해 균등하게 적용된다.

의의 및 주장
본 논문은 축 평행선 일관성만으로는 저개별 차수 검사에서 요구되는 전역적 호환성을 강제하기에 불충분하다고 결론짓는다. 따라서 대각선 검사(또는 그와 동등한 명시적 호환성 메커즘)는 건전성 보장을 해치지 않고는 테스트 세트에서 제거될 수 없다.

저자는 자신의 결과가 대각선 검사를 다른 명시적 호환성 검사로 대체하는 것을 배제하는 것은 아니라고 명시적으로 밝힌다. 단지 축 평행선 및 자기 일관성으로의 특정 축소가 부적절하다는 것을 보여줄 뿐이다. 이 작업은 국소적 호환성(행과 열)이 전역적 교환성을 의미하지 않는 머민-페레스 매직 스퀘어(Mermin–Peres magic square)와 유사한 구조적 장애물을 강조한다.

본 논문은 이 결과가 $\text{MIP}^* = \text{RE}$의 기초적 이해에 있어 중요하다고 주장한다. 즉, [JNV+20]에서 언급된 것처럼 "조건부 선형 함수(conditional linear functions)"를 "좌표 삭제 함수(coordinate deletion functions)"로 대체하는 것이 요구되는 건전성을 보존하지 못함을 명확히 한다. 이 구성은 유한 아벨 군에 대한 조화 해석과 유한 차원 양자 역학의 표준 도구, 특히 Weyl-Heisenberg 시스템의 심플렉틱 위상 공간 정식화를 활용한다.