Membership in the cone of quantum states over time is NP-hard

기술 요약: 시간 경과에 따른 양자 상태의 원뿔(Cone of Quantum States over Time)에 대한 멤버십 문제의 NP-난해성(NP-hardness)

문제 정의
본 논문은 "시간에 따른 상태(stotes)"의 볼록 원뿔 $\mathcal{Q}$를 특징짓는 계산 복잡도를 다룬다. stote는 초기 상태 $\rho$와 양자 채널 $E$로부터 조르단 곱(Jordan product) 규정에 따라 구성된, 이분법적 시스템 $H_A \otimes H_B$ 상의 일반적으로 비양의(non-positive) 헤르미트 연산자로 정의된다:
$$Q = (\rho \otimes \mathbb{1}) \star J_E = \frac{1}{2}((\rho \otimes \mathbb{1})J_E + J_E(\rho \otimes \mathbb{1}))$$
여기서 $J_E$는 채널 $E$의 자미올코프스키(Jamiołkowski) 연산자이다. $\mathcal{Q}$는 이러한 모든 연산자들에 의해 생성되는 볼록 원뿔이다. [HCW26]에서 제기된 핵심적인 미해결 문제는 이 원뿔의 멤버십 특성과 그 쌍대 원뿔(dual cone) $\mathcal{Q}^*$를 특징짓는 것이다. 구체적으로, 본 논문은 주어진 연산자가 $\mathcal{Q}$에 속하는지 여부(정확한 멤버십) 또는 $\mathcal{Q}$에 근접한지 여부(약한 멤버십)를 다항 시간 내에 해결할 수 있는지 조사한다.

방법론
저자는 NP-난해로 알려진 **양자 분리 가능성 문제(quantum separability problem)**로부터 환원을 수행한다. 핵심적인 기술적 전략은 분리 가능한 상태의 원뿔을 "시간에 따른 상태"의 원뿔 안으로 **안면 임베딩(facial embedding)**하는 것이다.

1. 안면 임베딩 구축:
   저자는 특정 출력 시스템 $H_B = H_{A'} \otimes H_R$을 정의한다. 여기서 $H_{A'}$는 입력 공간 $H_A$의 복사본이고, $H_R$은 보조 레지스터이다. 저자는 증인 연산자(witness operator) $W_0 = (d\mathbb{1}_{AA'} - S_{AA'}) \otimes \mathbb{1}_R$를 구성한다 ($S_{AA'}$는 스왑 연산자).
   이어서 $W_0$가 쌍대 원뿔 $\mathcal{Q}^*$에 속하며, $W_0$에 직교하는 하이퍼플레인에 의해 정의되는 $\mathcal{Q}$의 노출된 면(exposed face), 즉 $\{Q \in \mathcal{Q} : \text{Tr}[W_0 Q] = 0\}$가 분리 가능한 상태의 원뿔 $\text{SEP}^+(A:R)$와 동형임을 증명한다.

2. 임베딩 사상:
   $A \otimes R$ 상의 임든 헤르미트 연산자 $\sigma$에 대해, 다음을 만족하는 명시적이고 단사적이며 유리 선형인 사상 $L$이 정의된다:
   $$\sigma \in \text{SEP}^+(A:R) \iff L(\sigma) \in \mathcal{Q}(A:A'R)$$
   사상 $L$은 대칭화 사상 $\Gamma(X) = \frac{1}{2}\{X \otimes \mathbb{1}, S\}$를 $R$에 대한 항등 연산자와 텐서 곱하여 구성된다.

3. 안정성 및 강건성:
   정확한 멤버십으로부터 약한 멤버십(볼록 집합에 대한 표준 복잡도 개념)으로 난해성을 확장하기 위해, 저자는 정량적 안정성 경계(Proposition 3.6)를 도출한다. 이 경계는 노출된 면으로부터 연산자 $Y \in \mathcal{Q}$까지의 트레이스 노름 거리를 $\text{Tr}[W_0 Y]$ 값과 연결한다. 이는 어떤 연산자가 분리 가능 원뿔에서 멀리 떨어져 있다면, 약속 문제(promise problem)의 "NO" 인스턴스를 고려하더라도 그 이미지가 stote 원뿔에서 멀리 떨어져 있음을 보장한다.

4. 혼합 단계:
   약한 멤버십 환원에 필요한 경계 사례를 처리하기 위해, 저자는 $T_\theta(X) = (1-\theta)X + \theta \mathbb{1}/N$라는 혼합 단계를 도입한다. 이는 분리 가능한 원뿔의 이미지를 $\mathcal{Q}$의 트레이스-1 베이스의 상대적 내부로 이동시키면서도, 비분리 입력에 대한 분리성을 유지한다.

주요 기여 및 결과

• 정확한 멤버십의 NP-난해성:
  정리 4.1은 유리 헤르미트 연산자가 $\mathcal{Q}$에 속하는지 결정하는 문제가 NP-hard임을 확립한다. 이는 분리 가능성과 $\mathcal{Q}$의 노출된 면 사이의 정확한 동치성에 의해 증명된다.

• 약한 멤버십 및 최적화의 NP-난해성:
  정리 4.2는 약한 멤버십(연산자가 $\mathcal{Q}$로부터 다항식 크기의 거리 내에 있는지, 혹은 멀리 떨어져 있는지 결정하는 문제)이 **강하게 NP-hard(strongly NP-hard)**임을 증명한다. 결과적으로, $\mathcal{Q}$ 및 그 쌍대 원뿔에 대한 약한 최적화(weak optimization) 또한 NP-hard이다. 이는 P = NP가 아닌 한, $\mathcal{Q}$에 대한 다항 시간 멤버십 테스트가 존재할 수 없음을 의미한다.

• 유한 SDP 표현 불가능성:
  정리 4.5는 차원 $d, r \ge 2$ 및 $d+r > 5$인 경우, 원뿔 $\mathcal{Q}(A:A'R)$이 유한 준정부호(semidefinite) 표현(SDR)을 가질 수 없음을 보여준다. 이 증명은 노출된 면과 스펙트럼 그림자(spectrahedral shadow)의 선형 이미지는 모두 스펙트럼 그림자라는 사실에 기반한다. 분리 가능한 원뿔이 유한 SDR을 갖지 않는 것으로 알려져 있으므로(Fawzi의 정리 [Faw21]), $\mathcal{Q}$가 이를 선형적 복사본으로서 면(face)으로 포함하고 있다면 $\mathcal{Q}$ 역시 유한하게 SDR-표현될 수 없다.

• 기하학적 성질:
  본 논문은 $\mathcal{Q}$가 닫혀 있고(closed), 점진적이며(pointed), 생성적(spanning)인 원뿔임을 확립한다. 또한, 노출된 면까지의 거리가 증인 페어링 값의 제곱근($\sqrt{\eta}$)에 비례한다는 정량적 안정성 경계를 제공하며, 이는 최적임이 밝혀졌다.

의의 및 주장

본 논문은 양자 베이지안 추론, 역추론(retrodiction), 그리고 양자 최적 운송(quantum optimal transport)의 중심 구조인 "시간에 따른 상태"의 멤버십 문제에 대한 복잡도 상태를 해결했다고 주장한다.

• 복잡도 장벽: 주요 의의는 일반적인 경우에 대해 시간에 따른 상태의 원뿔을 특징짓는 것이 계산적으로 불가능함을 입증한 데 있다. 이는 P $\neq$ NP라고 가정할 때, 이 원뿔에 대한 멤버십 테스트나 최적화를 위한 효율적인(다항 시간) 알고리즘의 존재를 배제한다.
• SDP 계층 구조에 대한 제한: 비표현성 결과는 이 원뿔이 유한한 수의 준정부호 제약 조건으로 정확하게 묘사될 수 없음을 시사한다. 이는 분리 가능성을 위한 Doherty-Parrilo-Spedalieri 계층 구조와 같은 SDP 계층들이 수렴할 수는 있지만, 원뿔을 정확하게 나타내는 유한 수준의 캐릭터리제이션을 제공할 수는 없음을 의미한다.
• 기존 연구와의 차별점: 저자는 자신의 난해성 결과가 다중 시간 상태 호환성(multi-time state compatibility)에 대한 기존의 준정부호 테스트(예: [GBB26])와 모순되지 않음을 명확히 한다. 해당 테스트들은 여기서 정의된 특정 볼록 원뿔(초기 시스템-환경 상관관계 및 메모리를 허용하는 세트)과는 다른 집합을 다루기 때문이다.

논문은 특정 출력 차원($B = A' \otimes R$)에 대해 난해성이 확립되었으나, 임의의 고정된 차원이나 상수 간격(constant gaps)에 대한 복잡도는 여전히 미해결 과제로 남아 있다고 언급하며 마무리한다. 또한 도출된 안정성 지수(stability exponent)가 최적임을 강조하며, 잠재적인 근사 알고리즘의 정밀도에 한계를 설정한다.