The Complexity of Local Stoquastic Hamiltonians on 2D Lattices

1. 연구 배경 및 문제 제기 (Problem)

• 국소 해밀토니안 문제 (Local Hamiltonian Problem): 양자 컴퓨팅의 근본적인 난제 중 하나로, 국소 해밀토니안의 바닥 상태 에너지 (ground-state energy) 를 결정하는 문제입니다. 일반적인 경우 이 문제는 QMA (Quantum Merlin-Arthur) 완비 문제로 알려져 있어 고전 및 양자 컴퓨터 모두에서 다루기 어렵습니다.
• 스토쿠아스틱 해밀토니안 (Stoquastic Hamiltonian): 계산 기저 (computational basis) 에서 비대각 성분이 모두 0 이하인 해밀토니안입니다. 이는 몬테카를로 시뮬레이션에서의 '부호 문제 (sign problem)'를 우회하여 고전적인 확률적 방법으로 효율적으로 시뮬레이션할 수 있게 합니다.
• 복잡도 클래스 StoqMA: 스토쿠아스틱 해밀토니안의 바닥 상태 에너지를 찾는 문제는 StoqMA 클래스에 속하며, 이는 MA 와 QMA 사이에 위치합니다.
• 연구 목표: 기존 연구에서 $k$-국소 ($k \ge 2$) 스토쿠아스틱 해밀토니안 문제가 StoqMA-완비임이 증명되었으나, 물리적으로 가장 중요한 2 차원 (2D) 격자 구조로 제한되었을 때의 복잡도는 명확하지 않았습니다. 특히, 2 차원 정사각형 격자 (square lattice) 에서 2-국소 (2-local) 스토쿠아스틱 해밀토니안 문제가 StoqMA-완비인지 여부가 미해결 과제였습니다.

2. 방법론 (Methodology)

저자들은 Oliveira 와 Terhal 의 공간적으로 희소 (spatially sparse) 회로 구성 기법과 Bravyi 등 (Bravyi, DiVincenzo, Oliveira, Terhal) 의 섭동적 가젯 (perturbative gadgets) 기법을 확장하여 문제를 해결했습니다. 주요 접근 방식은 다음과 같습니다.

A. 회로에서 해밀토니안으로의 매핑 (Circuit-to-Hamiltonian Mapping)

1. 근접 이웃 회로 변환: 장거리 게이트를 가진 일반적인 StoqMA 회로를 근접 이웃 (nearest-neighbour) 게이트만으로 구성된 회로로 변환합니다. 이를 위해 Swap 네트워크를 사용하여 게이트 수를 다항식적으로 증가시키지만, 회로의 통계적 성질 (완전성 및 신뢰성 파라미터) 은 유지합니다.
2. 공간적으로 희소 (Spatially Sparse) 회로 구성: 근접 이웃 회로를 공간적으로 희소한 그래프 구조로 매핑합니다. 각 큐비트가 상수 개수의 이웃과만 상호작용하도록 하여, Feynman-Kitaev 시계 (clock) 구성을 적용할 수 있게 합니다. 이 단계에서도 회로 통계는 보존됩니다.
3. 6-국소 StoqMA-완비성 증명: 위 과정을 통해 생성된 공간적으로 희소한 그래프에서의 6-국소 스토쿠아스틱 해밀토니안 문제가 StoqMA-완비임을 증명합니다.

B. 섭동적 가젯을 통한 국소성 축소 (Locality Reduction via Perturbative Gadgets)

6-국소 문제를 2-국소 문제로 축소하기 위해 새로운 스토쿠아스틱 보존 (stoquasticity-preserving) 가젯들을 설계했습니다. 기존 가젯들은 스토쿠아스틱 성질을 유지하지 못했기 때문에 새로운 접근이 필요했습니다.

1. 기저 분해: 2-국소 스토쿠아스틱 해밀토니안을 특정 1-큐비트 행렬 기저 ($\rho_\mu$) 로 분해하여, 대각 항과 음의 비대각 항을 명확히 구분합니다.
2. 새로운 가젯 설계:
   • Subdivision Gadget: 상호작용을 분할합니다.
   • Cross Gadget: 비평면적 (non-planar) 상호작용을 제거하여 평면 그래프로 만듭니다.
   • Fork Gadget: 정점의 차수 (degree) 를 줄입니다.
   • Triangle Gadget: 삼각형 구조의 정점 차수를 줄입니다.
   • 이 모든 가젯은 Schrieffer-Wolff 변환을 사용하여 분석되었으며, 2 차원 섭동 이론에서 원하지 않는 교차 항 (cross-terms) 이 발생하지 않도록 설계되었습니다.
3. 기하학적 축소: 공간적으로 희소한 그래프를 차수가 4 인 평면 그래프로 변환한 후, 이를 2 차원 정사각형 격자에 효율적으로 임베딩합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

1. 2D 격자에서의 StoqMA-완비성 증명 (Theorem 6):

   • 2 차원 정사각형 격자 (2D square lattice) 에 정의된 2-국소 스토쿠아스틱 해밀토니안 문제가 StoqMA-완비임을 증명했습니다.
   • 이는 물리적으로 매우 관련 깊은 시스템 (예: 2D 양자 스핀 시스템) 에서도 이 문제가 계산적으로 어렵다는 것을 의미합니다.

2. 스토쿠아스틱 보존 가젯의 개발:

   • 기존 일반 해밀토니안용 가젯 기법을 스토쿠아스틱 조건을 만족하도록 수정 및 확장했습니다.
   • 입자의 차원 (particle dimension) 을 증가시키지 않고 (qubit 시스템 유지), 기하학적 제약 하에서 국소성을 줄이는 데 성공했습니다.

3. 부모 해밀토니안 (Parent Hamiltonian) 의 분석:

   • 특정 스토쿠아스틱 Pauli 해밀토니안 (예: $(x^- - z/x^- - z)$-Hamiltonian) 이 StoqMA-완비임을 보였습니다. 이는 횡방향 자기장 Ising 모델 (Transverse-field Ising model) 을 포함하는 더 넓은 클래스입니다.

4. 차수 축소 및 평면화:

   • 임의의 스토쿠아스틱 해밀토니안을 2 차원 격자에 매핑하기 위해 정점의 차수를 4 이하로 줄이고 평면 그래프로 변환하는 효율적인 절차를 제시했습니다.

4. 의의 및 중요성 (Significance)

• 물리적 시스템의 복잡성 규명: 2 차원 격자 구조는 실제 양자 물질 (예: 고체 물리 시스템) 을 모델링하는 데 가장 일반적인 형태입니다. 이 연구는 이러한 물리적으로 현실적인 제약 조건 하에서도 스토쿠아스틱 해밀토니안 문제가 여전히 계산적으로 난해 (StoqMA-hard) 함을 보여줍니다.
• 스토쿠아스틱 시뮬레이션의 한계: 스토쿠아스틱 해밀토니안이 몬테카를로 시뮬레이션으로 효율적으로 풀 수 있다는 사실은 알려져 있었으나, 이 연구는 "바닥 상태 에너지를 찾는 문제" 자체가 복잡도 클래스 StoqMA 에 속하여 고전 컴퓨터로 다항식 시간에 해결하기 어렵다는 것을 엄밀하게 증명했습니다.
• 이론적 도구 확장: 스토쿠아스틱 조건을 유지하면서 국소성을 줄이는 새로운 가젯 기법을 개발함으로써, 향후 다른 스토쿠아스틱 시스템의 복잡도 분석에 중요한 도구를 제공했습니다.
• 향후 연구 방향 제시:
  • 2 차원 격자에서의 반강자성 Heisenberg 모델 (antiferromagnetic Heisenberg model) 의 복잡도 (StoqMA-완비인지 여부) 를 규명하는 것이 중요한 열린 과제로 남았습니다.
  • 그래프 구조를 활용한 '가이드 상태 (guiding state)' 구성 가능성 및 복잡도 클래스의 정교화 (예: SStoqMA) 에 대한 연구를 촉발했습니다.

요약

이 논문은 2 차원 정사각형 격자에 제한된 2-국소 스토쿠아스틱 해밀토니안의 바닥 상태 에너지 결정 문제가 StoqMA-완비임을 증명했습니다. 이를 위해 기존 회로 구성 기법을 공간적으로 희소한 구조로 변환하고, 스토쿠아스틱 성질을 보존하는 새로운 섭동적 가젯 (perturbative gadgets) 을 설계하여 고차원 상호작용을 2-국소 격자 상호작용으로 축소하는 데 성공했습니다. 이 결과는 양자 복잡도 이론과 물리적으로 관련된 많은-body 시스템 연구 간의 간극을 메우는 중요한 업적입니다.