Robustness of Hidden-Variable Theories and Matrix Scaling

기술 요약: 숨은 변수 이론의 강건성과 행렬 스케일링

문제 정의
양자 기초론과 복잡도 이론에 의해 동기 부여된 본 논문은 아런슨(Aaronson)에 의해 형식화된 숨은 변수 이론(HVT)의 특성을 조사한다. 구체적으로, 본 논문은 아런슨이 공식화한 슈뢰딩거의 1931년 제안에서 영감을 받은 HVT인 '슈뢰딩거 이론'의 강건성(robustness)을 다룬다. 이 이론에서는 초기 양자 상태 $\rho$와 유니터리 진화 $U$가 주어졌을 때, $U$의 성분별 절댓값(entrywise modulus)을 리스케일링(Sinkhorn 알고리즘을 통해)하여 $\rho$의 Born 법칙 확률과 일치하는 열 주변부(column marginals) 및 $U\rho U^\dagger$의 Born 법칙 확률과 일치하는 행 주변부(row marginals)를 갖는 결합 확률 분포를 할당한다.

아런슨은 이 매핑이 강건할 것이라고 추측했다. 즉, 입력값($\rho$와 $U$)에 대한 역다항식 수준의 미세한 섭동(perturbation)이 결과적인 결합 분포에 역다항식 수준의 미세한 섭동을 일으킨다는 것이다. 이 성질은 비붕괴 측정(non-collapsing measurements)의 능력(복잡도 클래스 DQP)을 규명하는 데 있어 복잡도 이론적 응용, 특히 매우 중요하다. 본 논문은 이 추측이 성립하는지, 만약 그렇지 않다면 대칭성, 무관심성(indifference), 분해 불변성(decomposition invariance), 교환 법칙(commutativity)과 같은 다른 공리들을 만족하면서 강건성을 충족할 수 있는 수정된 이론이 존재하는지 규명하고자 한다.

방법론
저자들은 행렬 스케일링 이론, 운송 폴리토프(transportation polytopes) 상의 최적화, 그리고 명시적인 반례 구축의 조합을 사용한다.

1. 반례 구축: 원래의 슈뢰딩거 이론의 강건성을 부정하기 위해, 저자들은 특정 입력 계열을 구축한다. 저자들은 특정 제로 패턴(zero-pattern)과 파라미터 $\delta$를 가진 비음수 행렬 $M_\delta$를 정의한다. 이어서 $M_\delta$의 Sinkhorn 스케일링이 $\delta$에 매우 민감함을 입증한다. 이 행렬은 고차원 힐베르트 공간($N = 2n+1$)을 구성하고, 동일한 서포트(support)를 공유하지만 $\|U_\delta - U_{\delta'}\|_{\max} < 2^{-n}$만큼 차이가 나는 유니터리 $U_\delta$와 $U_{\delta'}$를 정의함으로써 양자 환경으로 "리프팅(lifted)"된다. 초기 상태 $\rho$는 슈뢰딩거 이론에 의해 할당된 결합 분포가 입력값이 지수적으로 가까움에도 불구하고 총 변동 거리(total variation distance) 측면에서 상수만큼 크게 차이 나도록 선택된다.

2. 최적화 및 용량 제약: 강건성의 실패를 해결하기 위해, 저자들은 "캡드 슈뢰딩거 이론(Capped Schrödinger Theory)"을 제안한다. 이 변형된 이론은 제약된 최적화 문제에 의해 정의된다. 표준 운송 폴리토프(고정된 주변부를 갖는 행렬들) 상에서 쿨백-라이블러(KL) 발산 $D_{KL}(P \parallel |U|)$를 최소화하는 대신, 새로운 이론은 추가적인 **용량 제약(capacity constraints)**을 갖는 폴리토프 $C(\rho, U)$ 상에서 이 발산을 최소화한다. 구체적으로, 결합 분포 $P$의 성분은 $P_{ji} \leq C_{ji} = 2|U_{ji}|\sqrt{(U\rho U^\dagger)_{jj} \rho_{ii}}$에 의해 제한된다.

3. 강건성 증명: 캡드 이론의 강건성은 KL 발산의 강한 볼록성(strong convexity)과 최대 유량 최소 컷(max-flow min-cut) 정리를 사용하여 증명된다. 용량 제약은 인접한 입력 $(\rho, U)$와 $(\tilde{\rho}, \tilde{U})$에 대해 가용한 집합들이 서로 "가깝게" 유지되도록 하여 해의 투영(projection)을 가능하게 한다. 인접한 폴리토프 상의 KL 발산 최소화 값들 사이의 거리를 제한함으로써, 저자들은 입력 섭동에 대해 결합 분포가 다항식적으로만 변화함을 입증한다.

4. 공리 분석: 저자들은 아런슨의 공리들이 얼마나 호환되는지를 체계적으로 분석한다. 저자들은 특정 공리들의 조합이 동시에 만족될 수 없음을 보여주는 새로운 불가능성 정리들을 증명하여, 가능한 HVT의 지형을 정교화한다.

주요 기여 및 결과

• 강건성 추측의 부정: 본 논문은 원래의 슈뢰딩거 이론이 강건하지 않음을 보여주는 반례(정리 1.3)를 제공한다. 저자들은 순수 상태와 두 유니터리를 구성하여, 이들이 지수적으로 가깝지만 할당된 결합 분포는 적어도 하나의 성분에서 역선형 항(inverse-linear term) 이상으로, 그리고 총 변동 거리 측면에서 상수만큼 차이가 남을 보여준다. 이러한 실패는 유니터리들이 동일한 최소 블록(support)을 공유할 때도 발생하며, 이는 불안정성이 스케일링 절차 자체에 내재되어 있음을 나타낸다.
• 캡드 슈뢰딩거 이론 제안: 저자들은 결합 분포에 용량 제약을 부과하는 수정된 이론(정의 4.1)을 도입한다. 저자들은 이 새로운 이론이 다음을 만족함을 증명한다(정리 1.4):
  • 대칭성(Symmetry): 기저 재라벨링에 대한 불변성.
  • 무관심성(Indifference): $U$의 블록 구조 보존.
  • 강건성(Robustness): 작은 섭동에 대한 안정성.
  • 분포 곱 교환성(Distributional Product Commutativity): 곱 상태에 대한 특정 형태의 교환 법칙.
• 공리에 대한 새로운 한계: 본 논문은 두 가지 새로운 불가능성 결과(정리 1.5 및 1.6)를 확립한다:
  • 어떤 HVT도 무관심성과 곱 교환성(전이 행렬의 강한 의미에서의)을 동시에 만족할 수 없다.
  • 어떤 HV도 무관심성과 분해 불변성을 동시에 만족할 수 없다.
    이러한 결과들은 이전 연구들과 결합되어, 아런슨의 공리 중 어떤 부분 집합이 동시에 만족될 수 있는지에 대한 완전한 분류를 제공한다.

의의
본 논문은 아런슨이 제기한 슈뢰딩거 이론의 안정성에 관한 주요 미해결 문제를 해결한다. 원래의 슈뢰딩거 이론이 강건하지 않음을 입증함으로써, 비붕괴 측정을 포함하는 복잡도 이론적 특성화에서 이 특정 HVT를 사용하는 것의 한계를 명확히 한다.

캡드 슈뢰딩거 이론의 도입은 대칭성, 무관심성, 그리고 일종의 교환 법칙을 유지하면서 강건성 성질을 구제해냈다는 점에서 중요하다. 이는 HVT의 내재적 트레이드오프에 대한 "완전한 그림"을 제공한다. 즉, 강건성과 무관심성을 동시에 달로는 가능하지만, 그 대가로 분해 불변성과 강한 교환 법칙을 포기해야 한다는 것을 보여준다. 이 연구는 HVT의 공리적 틀 내에서 무엇이 가능한지에 대한 정확한 경계를 획정하며, 비붕괴 측정을 사용하는 양자 시스템의 계산 능력을 조사하기 위한 정교한 도구를 제공한다.

또한, 본 논문은 행렬 스케일링, 용량 제약이 있는 엔트로피 최적 운송(entropic optimal transport), 그리고 양자 기초론 사이의 연결 고리를 강조하며, 용량 제약이 있는 상황에서 Sinkhorn 알고리즘의 안정성이 물리적으로 타당한 숨은 변수 모델을 구축하는 데 핵심적인 요소임을 시사한다.