Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs

기술 요약: 비음수 비얽힘 양자 증명에 대한 근사 최적 갭 증폭

문제 정의
본 논문은 두 명의 비얽힌 양자 증명자가 계산 기저(computational basis)에서 비음수 실수 진폭(nonnegative real amplitudes)을 가진 증명을 제공하여 검증 가능한 복잡도 클래스인 $\text{QMA}^+(2)$의 갭 증폭 문제를 다룬다. Jeronimo와 Wu(STOC 2023)에 의해 도입된 $\text{QMA}^+(2)$는 완결성-건전성 갭($c-s$)에 따라 급격한 상전이를 보인다. 작은 상수 갭은 이 클래스가 $\text{NEXP}$를 포착할 수 있게 하는 반면, 더 큰 상수 갭은 이 클래스를 $\text{QMA}(2)$로 붕괴시킨다. 이는 프로덕트 테스트(product test)를 통해 강력한 갭 증폭이 알려진 표준 $\text{QMA}(2)$와 대조된다. 핵심 과제는 $\text{QMA}^+(2) = \text{NEXP}$ 관계를 유지하면서(즉, $\text{QMAR}(2) = \text{NEXP}$를 함의하지 않으면서) 건전성 $s$가 얼마나 $1/4$에 가깝게 접근할 수 있는지(구체적으로 갭을 얼마나 증폭할 수 있는지)를 결정하는 것이다.

방법론
저자는 대칭 부분 공간 투영(symmetric-subspace projections)과 새로운 차원 독립적 드 피네티 정리(dimension-independent de Finetti theorem)를 결합한 새로운 검증자 프로토콜을 구성한다. 증명 전략은 다음 세 단계로 진행된다:

1. 강건한 단일 증명 테스트(Robust One-Proof Test): 최근의 결과인 Bassirian, Fefferman, 그리고 Marwaha(ITCS 2024)의 $\text{NEXP} = \text{QMA}^+(1)$(고정된 상수 갭에 대해)를 활용하여, 저자는 먼저 하나의 큰 레지스터에 대한 임계값 테스트를 구성한다. 고정된 갭을 가진 단일 증명 검증자 $L$을 반복하고, 실행 중의 비율 $\theta$가 수락하면 수락하는 방식을 통해, 어떤 비음수 상태(심지어 $L$개의 레지스터에 걸쳐 얽혀 있는 상태라도)에 대해서도 수락 확률이 상수 $r < 1$로 제한되는 테스트 연산자 $B$를 생성한다.
2. 이중 증명 프로토콜 구성: 검증자는 각각 $M$개의 레지스터를 가진 두 명의 Merlin에게 요청한다. 검증자는 각 증명을 대칭 부분 공간 $\text{Sym}_M(\mathcal{H})$로 투영하여 순열 대칭성을 강제한다. 그 후, 각 증명에서 $N = \Theta(\log M)$개의 레지스터를 선택하고, $2N$개의 결합 레지스터를 $\text{Sym}_{2N}(\mathcal{H})$로 투영한 뒤, 선택된 모든 레지스터에 연산자 $B$를 적용한다.
3. 텐서 거듭제곱 근사를 통한 건전성 분석: 핵심적인 기술적 과제는 증명자들이 대칭이 되도록 투영된 얽힌 상태를 보낼 때의 건전성을 분석하는 것이다. 저자는 새로운 차원 독립적 드 피네티 정리(정리 12)에 의존한다. 이 정리는 $\text{Sym}_m(\mathcal{H})$ 상의 상태 $\Gamma_m$에 대하여, $\ell \leq (1/2 - \eta)\log_2 m$일 때, $\ell$개 레지스터 상의 축소 상태(reduced state)가 텐서 거듭제곱 $(|\psi\rangle\langle\psi|)^{\otimes \ell}$의 볼록 조합에 힐베르트-슈미트 노름(Hilbert-Schmidt norm) 의미에서 가깝다는 것을 기술한다. 결정적으로, 이 오차 범위는 국소 차원 $\dim \mathcal{H}$에 독립적이며, 이는 여기서의 차원이 입력 크기에 지수적인 만큼 필수적이다.

건전성 분석은 진폭의 비음수성을 활용한다. 축소 상태를 텐서 거듭제곱의 혼합물로 근사하고 "절댓값" 비교(상태를 성분별 절댓값으로 매핑)를 적용함으로써, 저자는 수락 확률을 제한한다. 이들은 관련 연산자의 제곱 힐베르트-슈미트 노름이 $1/4 + o(1)$로 제한됨을 보여줌으로써, 총 건전성이 $1/4 + 1/\text{poly}(n)$임을 입증한다.

주요 기여 및 결과
주요 결과는 높은 완결성과 $1/4$에 접근하는 건전성을 가진 $\text{QMA}^+(2)$를 이용한 $\text{NEXP}$의 근사 최적 특성화이다:

• 정리 1: 임의의 다항식 $p(n) \geq 4$에 대하여,
  $$\text{NEXP} = \text{QMA}^+\left(2, 1 - \frac{1}{p(n)}, \frac{1}{4} + \frac{1}{p(n)}\right).$$
  이는 역 다항식 갭을 가진 임의의 $\text{QMA}^+(k)$ 프로토콜이 이 영역으로 증폭될 수 있음을 의미한다.

• 최적성 및 상전이: 이 결과는 거의 최적이다. 저자는 만약 건전성이 $1/4 - 1/\text{poly}(n)$으로 개선되어 $c=4s$ 선을 넘게 된다면, 그것이 $\text{QMAR}(2) = \text{NEXP}$를 함의한다는 것을 보여준다. 이는 $\text{QMA}(2)$를 $\text{NEXP}$로 붕괴시키거나 실수의 진폭이 복소수 진폭과 근본적으로 다른 힘을 갖는다는 것을 증명하는 등 중요한 복잡도 이론적 결과를 초래할 수 있다.

• 차원 독립적 드 피네티 정리 (정리 12): 본 논문은 전체 레지스터 수 $m$에 대해 로그 단위로 증가하는 레지스터 수 $\ell$ ($\ell \leq (1/2-\eta)\log_2 m$)에 적용되는 힐베르트-슈미트 노름에서의 유한 양자 드 피네티 정리를 증명한다. 선형적으로 국소 차원에 의존하는 이전의 트레이스 노름(trace-norm) 경계와 달리, 이 경계는 차원에 독립적이다. 증명은 단일 레지스터 축소 상태의 스펙트럼을 "무거운" 부분(고윳값 $> 1/m$)과 "가벼운" 부분으로 나누고, 가벼운 부분이 힐베르트-슈미트 노름에 미치는 기여가 무시할 수 있는 수준임을 보여주는 과정을 포함한다.

의의
본 논문은 $\text{QMA}^+(2)$에 대한 명확한 복잡도 상전이를 확립한다. 저자는 비음수 비얽힘 증명에 대한 갭 증폭 문제를 거의 최적으로 해결하여, 건전성을 $1/4$에 임의로 가깝게 밀어붙이면서도 해당 클래스를 $\text{QMA}(2)$로 붕괴시키거나 $\text{QMAR}(2) = \text{NEXP}$를 함의하지 않음을 보여준다.

이 연구는 비얽힘과 결합된 비음수 진폭의 독특한 능력을 강조한다. 표준 $\text{QMA}(2)$는 프로덕트 테스트를 통해 강력한 증폭을 허용하는 반면, $\text{QMA}^+(2)$는 갭 크기에 매우 민감하다. 저자의 결과는 이 민감도의 경계를 명확히 한다: $1/4$ 임계값은 실수 증명으로 비음수 증명을 시뮬레이션하는 능력(부호 제거를 통해)에 의해 부과되는 장벽이며, 이 선을 넘으면 복잡도 클래스가 근본적으로 변하게 된다.

기술적으로, 본 논문은 양자 복잡도 이론에 중요한 도구를 제공한다: 로그 단위의 레지스터에 대한 힐베르트-슈마이트 노름에서의 차원 독립적 드 피네티 정리이다. 이 도구는 국소 차원이 지수적인 상황에서 전통적인 트레이스 노름 드 피네티 정리가 실패하는 프로토콜을 분석하는 데 필수적이다. 저자는 이 근사 정리가 로그 단위의 레지스터 상의 축소 상태의 2차 모멘트에만 의존하는 다른 프로토콜에도 유용할 수 있다고 언급한다.