On The Complexity of Redundancy-Free Quantum Hamiltonians

기술 요약: 중복성이 없는 양자 해밀토니안의 복잡성에 대하여

문제 정의
본 논문은 "중복성이 없는(redundancy-free)"이라 불리는 특정 클래스의 양자 해밀토니안의 계산 복잡도를 조사한다. 해밀토니안 $H = \sum_i J_i O_i$는 적어도 하나의 항이 홀수 번 나타나는 임의의 곱에 대해 트레이스(trace)가 0이 될 때 중복성이 없는 것으로 정의된다. 이 클래스는 항들의 곱 중 어떤 비자명한 곱도 항등원(identity)과 같지 않은 파울리 연산자의 합으로 구성된 해밀토니안을 포함한다(파울리 중복성 없음).

이러한 해밀토니안을 연구하는 주요 동기는 **해밀토니안 디코딩 양자 간섭계(Hamiltonian Decoded Quantum Interferometry, HDQI)**에서 기인한다. HDQI에서 일반적인 해밀토니안의 깁스 상태(Gibbs state)를 준비하는 과정은 두 단계로 축소된다: (1) 중복성이 없는 해밀토니안의 열적 쌍쌍 상태(thermofield double, TFD)와 동등한 "파일럿 상태(pilot state)"를 준비하고, (2) 중복성을 제거하기 위해 고전적인 디코딩 문제를 해결하는 것이다. 디코딩 단계는 잘 이해되어 있으나, 파일럿 상태(중복성이 없는 해밀토니안의 TFD)를 준비하는 복잡도는 미해결 과제로 남아 있었다. 본 연구는 이러한 상태 준비와 그에 따른 분배 함수 근사의 난이도를 규명한다.

방법론 및 프레임워크
저자들은 역온도 $\beta$와 반교환 그래프(anticommutation graph) $G$의 차수 $d$의 함수로서 복잡도를 분석한다. 이 그래프에서 정점은 해밀토니안 항 $O_i$를 나타내며, $\{O_i, O_j\} = 0$인 경우 즉, 두 항이 반교환할 때 정점 $i$와 $j$ 사이에 에지가 존재한다. 복잡성을 결정하는 핵심 파라미터는 $\kappa = \beta^2 d$이다.

본 논문은 다음과 같은 몇 가지 구별된 방법론을 사용한다:

1. 폴리머 전개(Polymer Expansion): 작은 $\kappa$에 대해, 저자들은 자유 에너지의 폴리머 전개를 활용한다. 저자들은 폴리머를 반교환 그래프의 연결된 부분 그래프로 정의하고, 분배 함수의 급수 전개에 대한 수렴 조건을 유도한다.
2. 반교환 유리(Anticommutation Glass) 구축: 큰 $\kappa$에서의 난이도를 확립하기 위해, 저자들은 "반교환 유리"라고 불리는 시스템을 구축한다. 이 시스템은 X-타입과 Z-타입의 두 연산자 집합으로 구성되며, 고전적 중복성 없이 순수하게 반교환 관계로부터 발생하는 좌절(frustration)을 생성하는 가역적인 반교환 행렬을 가진다.
3. Feiguin-Klich 해밀토니안: 상태 준비를 위해, 저자들은 원하는 TFD를 바닥 상태로 갖는 비가역적 연산자인 Feiguin-Klich 해밀토니안($H_{FK}$)을 탐구한다. 저자들은 이의 스펙트럼 갭(spectral gap)과 멱급수 전개의 수렴성을 분석한다.
4. QMA-난해도 감소(QMA-Hardness Reduction): 바닥 상태 에너지의 난해도를 증명하기 위해, 저자들은 삼각 격자 상의 반강자성 XY 모델에 대한 국소 해밀토니안 문제를 중복성이 없는 해밀토니안으로 환원시킨다. 저자들은 관계를 제거하면서 바닥 상태 에너지 구조를 보존하는 3-큐비트 인코딩 기법을 사용한다.

주요 결과

1. 분배 함수 근사의 복잡도

• 작은 $\kappa$ (쉬운 영역): 저자들은 $\kappa$가 충분히 작을 때(구체적으로 $\beta \lesssim 1/\sqrt{d}$일 때), 자유 에너지의 폴리머 전개가 수렴함을 증명한다. 이는 시스템 크기 $n$과 오차 $\epsilon$에 대해 다항 시간 복잡도를 갖는 효율적인 고전 알고리즘을 제공한다. 이는 일반적인 해밀토니안($\beta \lesssim 1/d$에서만 트랙터블함)에 비해 이차적인 개선을 의미한다.
• 큰 $\kappa$ (어려운 영역): 반대로, $\kappa$가 충분히 클 때, 분배 함수를 근사하는 것은 **NP-난해(NP-hard)**임이 밝혀졌다. 저자들은 중복성이 없는 해밀토니안이 임의의 고전적 이징 모델(강자성 및 반강자성 상호작용 모두 포함)을 그들의 분배 함수 내에 효과적으로 인코딩할 수 있음을 보여준다. 이는 반교환 유리의 "분지(basins)"를 사용하여 유효 이징 모델을 구축함으로써 달성된다.
• 바닥 상태 에너지: 중복성이 없는 해밀토니안의 바닥 상태 에너지를 추정하는 것은 제한된 국소성(최대 5)과 제한된 반교환 차수(최대 26) 하에서도 **QMA-완전(QMA-complete)**임이 증명되었다.

2. 양자 상태 준비

• 아지수근(Subexponential) 알고리즘: 작은 $\kappa$에 대해, 저자들은 TFD 상태를 준비하기 위한 아지수근 시간 양자 알고리즘을 제시한다. 이는 상관관계의 감쇠가 $\beta d$가 아닌 $\kappa = \beta^2 d$에 의해 지배된다는 점에 기초한다.
• 일반 해밀토니안에 대한 다항 시간: $\beta \lesssim 1/\sqrt{d}$인 중복성이 없는 해밀토니안에 대한 다항 시간 알고리즘의 증명은 여전히 미완이지만, 저자들은 상호작용 그래프의 차수가 $d$인 일반적인 해밀토니안의 TFD를 $\beta \lesssim 1/d$에서 준비하기 위한 다항 시간 알고리즘을 제공한다. 이 알고리즘은 Feiguin-Klich 해밀토니안을 활용하며, 충분히 작은 $\beta d$에 대한 스펙트럼 갭을 증명하는 데 의존한다.

3. 물리적 특성: 상관관계 및 얽힘

• 상관관계 감쇠: 본 논문은 중복성이 없는 해밀토니안에서 상관관계가 거리의 함수로서 $\kappa = \beta^2 d$에 의해 제어되며 지수적으로 감쇠함을 입증한다. 이 감쇠는 일반적인 해밀토니안에 비해 $\beta$에 대한 의존성이 이차적으로 더 강하다.
• 얽힘: $\beta \lesssim 1/\sqrt{d}$에서 알고리즘적으로 트랙터블함에도 불구하고, 이 해밀토니안들은 훨씬 낮은 온도, 즉 $\beta = O(1/d)$에서 진정한 양자 얽힘을 나타낸다. 저자들은 열 상태가 $\beta \sim 1/d$에서 얽혀 있음(NPT)을 보여주는 명시적인 예시(완전 이분 반교환 그래프의 정형적 구현 포함)를 구축하여, 트랙터블함이 분리 가능성(separability)을 의미하지 않음을 입증한다.
• 상호 정보량: 강화된 열 상호 정보량 경계가 도출되었으며, 이는 일반적인 해밀토니안의 선형 $\beta$ 스케일링과 비교하여 중복성이 없는 해밀토니안의 $\beta^2$ 스케일링을 보여준다.

의의 및 주장
본 논문은 중복성이 없는 해밀토니안이 양자 상태 준비의 어려움의 근원을 이해하기 위한 중요한 테스트베드 역할을 한다고 주장한다. 연구 결과는 **해밀토니안 디코딩 양자 간섭계(HDQI)**가 디코딩 단계가 효율적인 온도 범위에서 특정 해밀토니안의 열 상태 준비를 단순화할 수 있음을 시사한다.

구체적으로, 본 연구는 다음을 입증한다:

• TFD 준비의 어려움은 단순히 고전적 중복성 때문만이 아니라, 순수하게 반교환 관계(좌절)로부터 발생할 수 있다.
• 중복성이 없는 해밀토니안에는 일반적인 해밀토니안의 쉬운 영역($\beta \lesssim 1/d$)보다 이차적으로 더 넓은 "쉬운" 영역($\beta \lesssim 1/\sqrt{d}$)이 존재한다.
• "반교환 유리" 모델은 일반적인 양자 해밀토니안의 본질적인 어려움을 포착하며, 그들의 바닥 상태 에너지 추정은 여전히 QMA-완전하다.

저자들은 $\beta \lesssim 1/\sqrt{d}$에서 중복성이 없는 해밀토니안의 TFD를 다항 시간 내에 준비하는 문제에 대해, 아지수근 알고리즘과 Feiguin-Klich 해밀토니안을 통한 경로를 제시했음에도 불구하고, 해당 영역에서의 스펙트럼 갭에 대한 엄밀한 증명은 향후 과제로 남겨두며 신중한 태도를 유지한다. 또한, 자신들의 일반 해밀토니안에 대한 다항 시간 결과가 격자 차원에 대한 가정을 제거함으로써 기존 연구를 개선했음을 명시한다.