기술적 요약: 가분 집합의 준정부호 확장 복잡도 (Semidefinite Extension Complexity of the Separable Set)

1. 문제 정의

본 논문은 두 가지 결과(two-outcome) 측정 연산자 $Q$에 대하여 가분 상태 집합 $\text{Sep}(d:d)$ 상에서의 최대 수용 확률을 근사하는 계산 복잡도를 다룬다. 이 최적화 문제 $h_{\text{Sep}}(Q) = \max_{\sigma \in \text{Sep}(d:d)} \text{Tr}(Q\sigma)$는 $\text{QMA}(2)$ (두 개의 얽히지 않은 증명을 가진 양자 머린-아서) 복잡도 클래스의 핵심이다.

구체적인 초점은 HNW(Harrow, Natarajan, Wu)가 구축한 프레임워크 내에서 가분 집합의 **준정부호 확장 복잡도(semidefinite extension complexity)**에 있다. 저자들은 다음 제약 조건 하에서 $h_{\text{Sep}}$를 근사하기 위해 필요한 최소 SDP 크기 $r$을 조사한다:

• 공통 가용 영역 (Common Feasible Region): 모든 측정 연산자 $Q$는 단일 SDP 가용 영역 $\mathcal{P}$ ($r \times r$ PSD 행렬들의 스펙트라헤드론)를 공유한다.
• 목적 함수 독립적 임베딩 (Objective-Independent Embedding): 순수 곱 상태(pure product states)를 $\mathcal{P}$로 임베딩하는 고정된 사상 $\iota$가 존재하여, 모든 $Q$에 대해 SDP 목적 함수 $\Phi_Q$가 곱 상태 $\tau$에 대한 수용 확률 $\text{Tr}(Q\tau)$를 재현한다.
• 근사 (Approximation): SDP는 지정된 가법 오차(additive error) $a$ 또는 상대적 간격(relative gap) $\varrho$ 내에서 $h_{\text{Sep}}$를 근사해야 한다.

본 논문은 또한 근사 디스엔탱글러(approximate disentanglers), 즉 임의의 입력을 가분 상태에 가까운 상태로 매핑하고 모든 가분 상태를 커버하는 양자 채널 $\Lambda: \mathcal{L}(\mathbb{C}^D) \to \mathcal{L}(\mathbb{C}^d \otimes \mathbb{C}^d)$에 이 하한값들을 적용한다. 목표는 이러한 채널에 필요한 최소 입력 차원 $D$를 결정하는 것이다.

2. 방법론

저자들은 패턴-행렬 하한(pattern-matrix lower bounds), 의사-밀도 기법(pseudo-density techniques), 그리고 **스펙트라헤드럴 기하학(spectrahedral geometry)**을 결합하여 사용한다.

2.1 HNW 프레임워크와 PSD 랭크

핵심 기술은 특정 비음수 행렬(즉, "슬랙 행렬")의 PSD 랭크와 SDP 정식화의 크기를 연결하는 Lee–Raghavendra–Steurer (LRS) 정리의 활용에 기반한다.

• 슬랙 행렬 구성: 저자들은 행은 "증인(witnesses)"(블록-양의 연산자 $W_T$)에 대응하고, 열은 "상태"(곱 상태 $\sigma_S$)에 대응하는 행렬 $M$을 구성한다. 행렬 성분은 $M(T, S) = \text{Tr}(W_T \sigma_S)$이다.
• 인수 분해 (Factorization): 크기 $r$의 SDP는 이 행렬의 크기 $r+1$인 PSD 인수 분해를 함의한다. 따라서 $M$의 PSD 랭크에 대한 하한은 SDP 크기에 대한 하한을 제공한다.

2.2 배낭 패턴 행렬 (The Knapsack Pattern Matrix)

그래프 3-색칠 가능성(graph 3-colorability)에 기반한 QMA(2) 프로토콜을 사용했던 이전 연구(HNW)와 달리, 본 논문은 **중앙 배낭 다항식(central knapsack polynomial)**을 기반으로 행렬을 구성한다:
$$f_m(x) = \frac{1}{m^2} \left[ \left( \sum_{i=1}^m x_i - \frac{m}{2} \right)^2 - \frac{1}{4} \right]$$
여기서 $m$은 홀 정수이다. 불리언 하이퍼큐브 $\{0,1\}^m$ 위에서 $f_m(x) \geq 0$이다. 그러나 Grigoriev의 의사-기댓값 범함수(pseudo-expectation functional) $\mathcal{G}_m$은 존재하지 않는 해밍 무게 층(Hamming weight layer) $m/2$를 유효한 것으로 취급함으로써 $f_m$에 음수 값(구체적으로 $-1/4m^2$)을 할당한다.

2.3 체비쇼프 다항식을 통한 증폭 (Amplification via Chebyshev Polynomials)

HNW의 지수적으로 작은 오차 체제와 비교하여 더 큰 근사 오차(상수 또는 역다항식)를 처리하기 위해, 저자들은 **체비쇼프-하다마르 증폭(Chebyshev-Hadamard amplification)**을 적용한다:

• 행렬 성분에 다항식 변환 $P_\ell(u) = (1 + T_\ell(2u-1))/2$를 적용한다.
• 이 변환은 범위 $[0,1]$ 내에서 성분의 비음수성을 보존하면서, "형식적" 음수 지점에서의 의사-기댓값 음수치를 $\ell^2$ 배만큼 증폭시킨다.
• 결정적으로, 저자들은 $P_\ell(u) = u Q_\ell(u)^2$라는 항등식을 사용하여 PSD 랭크 증가를 제한함으로써, 랭크 비용이 다항식의 차수에 따라 선형적으로만 증가함을 보여, 이 논증이 더 큰 오차 파라미터에서도 확장될 수 있음을 보여준다.

2.4 증인 및 상태의 구성

명제 4.1은 다음을 명시적으로 구성한다:

• 곱 상태 (Product States): 특정 기저 벡터들의 중첩을 사용하여 부분집합 $S \subseteq [N]$을 인코딩하는 $\sigma_S$.
• 블록-양의 증인 (Block-Positive Witnesses): 대각 투영 연산자와 스왑 연산자 $F$를 포함하는 페널티 항으로부터 구성된 $W_T$. 이 증인들은 곱 상태에 대해서는 비음수이지만 얽힌 상태에 대해서는 음수가 될 수 있도록 설계되었으며, 주변 차원에 무관하게 $O(m)$의 노름 상한을 갖는다.

3. 주요 기여 및 결과

3.1 SDP 정식화에 대한 하한

본 논문은 $h_{\text{Sep}}$를 근사하는 SDP 정식화의 크기 $r$에 대한 새로운 하한을 확립한다.

• 정리 5.4: 고정된 $0 < \theta < 2/7$에 대하여, 충분히 큰 $d$와 $a \leq a_\theta$인 근사 오차 $a$에 대해, $h_{\text{Sep}}$를 근사하는 모든 SDP의 크기는 다음과 같다:
  $$r \geq d^{c_\theta \min\{a^{-1/3}, d^\theta\}}$$
• HNW와의 비교: HNW는 오차 $O(1/d^2)$에 대해 $d^{\log d / \text{polylog} \log d}$의 하한을 증명했다. 새로운 하한은 상수 오차에 적용되며, 오차가 충분히 작을 때($a \leq d^{-3\theta}$) HNW의 하한을 $d$의 지수 함수($d^{\Omega(d^\theta)}$)로 개선한다.
• 기하학적 해석: 코롤러리 5.6은 이를 스펙트라헤드럴 섀도우(spectrahedral shadows)로 확장하여, $\text{Sep}(d:d)$를 포함하고 그것과 트레이스 거리 $a$ 내에 있는 모든 볼록 집합은 적어도 $d^{c_\theta \min\{(2a)^{-1/3}, d^\theta\}}$의 크기를 갖는 스펙트라헤드럴 리프트(spectrahedral lift)를 필요로 함을 증명한다. 이는 가분 집합이 정확한 준정부호 표현을 가질 수 없다는 Fawzi의 정리에 대한 정량적 대응물을 제공한다.

3.2 근사 디스엔탱글러에 대한 하한

저자들은 SDP 하한을 근사 디스엔탱글러의 입력 차원 $D$에 적용한다.

• 정리 1.1: 총 오차 $a = \varepsilon + \delta$인 $(\varepsilon, \delta)$-근사 디스엔탱글러에 대하여, 입력 차원 $D$는 다음을 만족한다:
  $$\log D \geq c M_a \log(2 + R_a)$$
  여기서 $M_a$와 $R_a$는 $d$와 $a$로부터 유도된 함수이다.
• 코롤러리 1.2 (정량적 성장):
  • 만약 $a \leq n^{-c}$ (큐비트 수 $n = \log d$에 대한 역다항식)이면, $\log D = \Omega(n^{1+c/3})$이다. 이는 초선형(superlinear) 수의 입력 큐비트를 강제한다.
  • 만약 $a$가 $(\log d)^{18/7} / d^{6/7}$의 차수라면, $\log D = \Omega(d^{2/7} / (\log d)^{6/7})$이다.
• QMA(2)에 대한 함의: 이러한 결과들은 약속 간격(promise gap)이 초다항식적으로 작을 때($n^{-\omega(1)}$), 디스엔글러 전략이 다항식 개수의 입력 큐비트를 가진 채널을 사용하여 $\text{QMA} = \text{QMA}(2)$를 증명하는 것을 불가능하게 만든다.

3.3 보존 가분성 (Bosonic Separability)

코롤러리 5.7은 이 하한을 이입자 보존 가분체(두 입자의 상태 형태 $|\psi\rangle\langle\psi|^{\otimes 2}$)로 확장하여, 동일한 복잡도 하한이 적용됨을 보여준다.

4. 의의 및 주장

본 논문은 다음과 같은 의의를 주장한다:

1. SDP 특화 하한: 본 연구는 상수 또는 역다항식 트레이스 거리 내에서 가분 집합을 근사하는 $h_{\text{Sep}}$의 일반적인 SDP 확장 정식화에 대한 최초의 무조건적인 정보 이론적 하한을 제공한다. 병행 연구인 Bostanci 등 [BGH+26]이 양자 오라클 분리를 통해 근사 디스엔탱글러에 대한 더 강력한 하한을 확립했지만, 그들의 환원은 일반적인 SDP 정식화에는 적용되지 않는다. 따라서 SDP 특화 하한(정리 5.4 및 코롤러리 5.5)이 준정부호 복잡도 맥락에서 본 연구의 주요 기여이다.
2. 정량적 개선: 본 연구의 하한은 HNW의 결과를 유의미하게 개선하여, 상수 또는 역다항식 오차에 대해 $d$에 대한 준다항식(quasipolynomial)에서 지수적(exponential) 하한으로 이동시켰다.
3. 디스엔탱글러 전략의 반박: 본 결과는 약속 간격에 비해 채널 오차가 충분히 작을 때(특히 SDP 하한이 적용되는 영역 내에서), 디스엔탱글러 접근 방식이 다항식 개수의 입력 큐비트를 사용하여 $\text{QMA}(2)$를 시뮬레이션할 수 없음을 보여준다.
4. 방법론적 발전: 본 연구는 배낭 다항식과 체비쇼프 증폭을 사용하는 LRS 정리의 정교한 적용을 도입하여, 이전의 프로토콜 기반 구성과 비교하여 오차 파라미터와 PSD 랭크 비용에 대해 더 정밀한 제어를 가능하게 했다.

저자들은 양자 오라클 분리를 사용하여 디스엔탱글러에 대한 더 강력한 하한($a$가 상수일 때 $\log D = \Omega(\sqrt{d})$)을 증명하는 Bostanci 등의 병행 연구 [BGH+26]를 인정한다. 그러나 저자들은 Bostanci 등의 환원이 일반적인 SDP 정식화에는 적용되지 않음을 지적하며, SDP 특화 하한(정리 5.4 및 코롤러리 5.5)이 본 연구의 핵심 기여임을 밝힌다. 모든 결과는 공식적인 Lean 증명에 의해 뒷받침된다.