A computational phase diagram for the transverse field Ising model

기술 요약: 가로 방향 자기장 이징 모델(Transverse Field Ising Model)에 대한 계산적 상평형도

문제 정의
본 연구는 가로 방향 자기장 이징 모델(TFIM)의 분배 함수 $Z(\beta) = \text{Tr}(e^{-\beta H})$와 깁스 상태 관측량(Gibbs state observables)을 근사하는 데 따르는 계산 복잡도를 다룬다. TFIM은 다음과 같은 해밀토니안(Hamiltonian)으로 정의된다:
$$H = \frac{1}{2} \sum_{i,j \in [n]} J_{ij} Z_i Z_j + \sum_{i=1}^n h^z_i Z_i + \eta \sum_{i=1}^n X_i$$
여기서 $J$는 대칭 상호작용 행렬, $h^z$는 종방향 자기장을, $\eta$는 가로 방향 자기장의 세기를 나타낸다. 강자성 시스템이나 고온 영역(구체적으로 $\beta \Delta(J) \leq 1$인 경우)에 대해서는 기존 알고리즘들이 존재했으나, 강한 가로 방향 자기장 하에서의 모델의 추적 가능성(tractability)은 미해결 문제로 남아 있었다. 저자는 모든 가로 방향 자기장 세기에 걸쳐 효율적인 고전적 근사가 가능한 경계와 NP-난해성(NP-hardness) 사이의 정확한 경계를 규명하고자 한다.

방법론
본 논문은 리-트로터 곱 공식(Lie-Trotter product formula) 근사, 고전 통계 역학적 사상(mapping), 그리고 대편차 원리(large deviation principles)를 결합하여 사용한다.

1. 고전적 분포로의 사상: 양자 분배 함수와 관측량들을 고전적 분포에 대한 기댓값으로 재작성한다. $M$ 단계의 리-트로터 근사를 활용함으로써, 양자 트레이스(quantum trace) $\text{Tr}(O e^H)$를 $\text{Tr}(O Q_M)$으로 근사한다. 여기서 $Q_M = (e^{H_z/M} e^{H_x/M})^M$이다. 이는 다시 $E_{\sigma \sim \nu}[e^{W(\sigma)} f(\sigma)]$ 형태의 기댓값으로 표현된다. 여기서 $\sigma$는 폐 경계 조건(closed boundary conditions)을 가진 사이클 그래프 상의 $n$개 독립적인 1D 이징 모델들의 구성(configurations)을 나타내며, $W(\sigma)$는 상호작용 행렬 $J$로부터 유도된 포텐셜 함수이다.
2. Glauber 역학을 통한 샘플링: 추적 가능한 영역에서, 문제는 기울어진 분포(tilted distribution) $\mu_\lambda \propto e^{\lambda W} \nu$로부터 샘플링하는 문제로 귀결된다. 저자는 상호작용 행렬의 스펙트럼 폭이 특정 조건을 만족할 때, 이 분포에 대한 Glauber 역학이 빠르게 혼합(KL-발산이 수축)됨을 증명한다. 이러한 빠른 혼합은 기초가 되는 사이클 상의 1D 이징 모델들의 공분산 행렬의 연산자 노름(operator norm)을 제한하는 것에 의존한다.
3. Gadget을 통한 난해성 입증: 난해성을 확립하기 위해, 저자는 MAXCUT 문제로부터의 환원(reduction)을 구성한다. 추적 불가능한 영역에 있는 가로 방향 커리-바이스(Curie-Weiss) 모델의 "이봉성(bimodality)"을 활용한다. MAXCUT 인스턴스의 정점들을 커리-바이스 가젯(gadget)으로 교체함으로써, 분배 함수 비율이 최대 컷 값을 인코딩하는 TFIM 인스턴스를 생성한다. 난해성은 가젯의 평균 스핀이 두 개의 서로 다른 값($\pm m^*$) 근처로 집중된다는 사실에 기반하며, 이를 통해 가젯이 이진 변수를 효과적으로 인코딩할 수 있게 한다.

주요 기여 및 결과

1. 계산적 상평형도: 본 논문은 다음 조건으로 정의되는 날카로운 상전이를 확립한다:
   $$\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \leq 1$$
   여기서 $\Delta(J) = \lambda_{\max}(J) - \lambda_{\min}(J)$는 상호작용 행렬의 스펙트럼 폭이다.

   • 추적 가능한 영역 ($\leq 1$): 저자는 분배 함수 $Z(\beta)$를 상대 오차 $\epsilon$ 내에서, 그리고 파울리 문자열(Pauli string) 관측량을 가산 오차 $\epsilon$ 내에서 근사하는 무작위 고전 알고리즘을 제공하며, 이때 시간 복잡도는 $n, \beta, \epsilon^{-1}$ 및 모델 파라미터에 대한 다항식이다. 이 조건은 기존 결과(예: $\beta \Delta(J) \leq 1$)보다 엄격히 약하며, 강한 자기장 극한($\Delta(J) \leq |\eta|$)을 포함한 모든 가로 방향 자기장 세기에 적용된다.
   • 추적 불가능한 영역 ($> 1$): 저자는 분배 함수를 $\exp(o(n))$-배수 오차 내에서 근사하는 것이 NP-난해함을 증명한다. 구체적으로, 임의의 $\epsilon > 0$에 대하여, $\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \in (1, 1+\epsilon)$를 만족하는 대칭 행렬 $J$가 존재하여 근사가 NP-난해함을 보인다. 이는 표준 복잡도 가정($NP \not\subseteq BQP$ 및 $NP \neq RP$) 하에서, 이 영역에는 효율적인 고전적 또는 양자 알고리즘이 존재할 수 없음을 의미한다.

2. 깁스 상태 준비: 추적 가능한 영역을 위해 개발된 효율적인 샘플링 기법을 활용하여, 저자는 총 변동 거리(trace distance) 오차 $\epsilon_{TV}$를 갖는 깁스 상태 $\rho_\beta = e^{-\beta H} / Z(\beta)$를 준비하는 효율적인 양자 알고리즘을 제공한다.

3. 바닥 상태 에너지 근사: 가로 방향 자기장이 지배적인 영역($\Delta(J) \leq |\beta \eta|$)에서, 알고리즘은 임의의 역온도 $\beta \geq 0$에 대해 적용 가능하다. 이를 통해 충분히 큰 $\beta$를 선택함으로써 바닥 상태 에너지 $E_0$를 임의의 가산 정밀도로 근사할 수 있다.

4. 관측량 추정: 알고리즘은 임의의 파울리 문자열 $P$에 대해 $\text{Tr}(P \rho_\beta)$를 추정한다. 만약 $P$가 X-기저에서 대각 성분(즉, $P \in \{I, X\}^{\otimes n}$)이라면, 알고리즘은 임의로 작은 상대 오차를 달성한다. 일반적인 파울리 문자열의 경우, 임의로 작은 가산 오차를 달성한다.

의의
본 논문은 양자 어닐링 및 응집 물질 물리학의 중심 영역인 강한 가로 방향 자기장 하에서의 TFIM 추적 가능성 영역을 규명하는 미해결 문제를 해결했다고 주장한다. $\Delta(J) \cdot \frac{\tanh(\beta \eta)}{\eta} \leq 1$을 정확한 경계로 식별함으로써, 본 연구는 강자성 또는 고온의 경우로 제한되었던 기존의 결과들을 통합하고 확장한다. 보완적인 영역에서의 NP-난해성 증명은 이 파라미터 공간에서의 고전적 및 양자 시뮬레이션 방법의 한계에 대한 강력한 이론적 근거를 제공한다. 나아가, 추적 가능한 영역을 위한 효율적인 깁스 상태 준비 및 관측량 추정 알고리즘의 개발은 강한 가로 방향 자기장이 존재하는 양자 시뮬레이션 작업에 실질적인 도구를 제공한다.

저자는 고수준의 전략은 저자가 직접 개발하였으며, AI 도구는 특정 증명(Lemma 13, Theorem 21, Propositions 8 및 9)과 타이포그래핑(typesetting)을 보조하였으나, 내용에 대한 모든 책임은 저자가 지고 있음을 밝힌다.