A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

기술 요약: 고차 이싱 유사 모델을 위한 일반적 해밀토니안 축소 (General Hamiltonian Reduction)

문제 정의
이싱 모델(Ising model)은 조합 최적화 문제를 인코딩하는 표준 프레임워크로, 바닥 상태(ground state)를 찾는 것은 최적의 해를 찾는 것과 같습니다. 양자 어닐링(quantum annealing)이나 시뮬레이션된 바이퍼케이션(simulated bifurcation)과 같은 휴리스틱 솔버들이 발전해 왔으나, 대규모 인스턴스에 내재된 조합 폭발(combinatorial explosion) 문제로 인해 어려움을 겪는 경우가 많습니다. 일반적인 전처리 전략은 해밀토니안 축소(Hamiltonian reduction)이며, 이는 모든 바닥 상태에서 고정된 상대적 구성을 유지하는 스핀들의 부분 집합을 식별함으로써 논리 변수의 수를 줄이는 것을 목표로 합니다.

FastHare 및 루프 이중성(roof duality)과 같은 기존 축소 기술은 주로 2차(quadratic) 이싱 모델을 위해 설계되었습니다. 그러나 만족도 문제(satisfiability) 및 고차 네트워크 모델을 포함한 많은 실질적인 최적화 문제들은 다체 상호작용(multi-body interactions)을 포함하는 고차 이싱 유사 해밀토니안으로 자연스럽게 정식화됩니다. 현재의 방법들은 이러한 고차 항들을 직접 처리할 수 없으며, 고차 문제를 이차 문제로 변환하기 위한 차수 감소(order-reduction) 기술들은 종종 보조 변수를 도입하여 문제의 크기를 키우는 경향이 있습니다. 일반적인 차수의 상호작용을 위한 특화된 해밀토니안 축소 체계가 부족한 실정입니다.

방법론
저자들은 비분리 그룹(non-separable groups, NGs) 이론을 임의 차수의 이싱 유사 모델로 일반화한 프레임워크인 **GeneralHare (GH)**를 제안합니다. 핵심 방법론은 세 가지 주요 구성 요소로 이루어집니다:

1. 일반화된 비분리 그룹 (gNGs):
   본 논문은 모든 바닥 상태에서 모든 스핀이 동일한 부호를 공유하는 NG의 정의를 gNG로 확장합니다. gNG는 특정 상대적 구성(예: $\sigma_a = -\sigma_b = \sigma_c$) 또는 그 전역적 역(global inverse)을 모든 바닥 상태에서 유지하는 스핀들의 부분 집합입니다. 이를 통해 단순한 동일성이 아닌 복잡한 내부 상관관계를 가진 스핀들을 병합할 수 있습니다.

2. 식별을 위한 계산 가능한 기준:
   정확한 비분리 지수(분리되는 구성과 분리되지 않는 구성 사이의 에너지 갭)를 계산하는 것은 NP-hard 문제입니다. 알고리즘을 실행 가능하게 만들기 위해, 저자들은 비분리 지수의 쉽게 계산 가능한 하한값($\hat{\nu}_H(X)$)을 도출했습니다.

   • 이 방법은 상호작용 차수($m$)에 따라 해밀토니안을 분해합니다.
   • 모든 가능한 스핀 구성을 최소화하는 대신, 후보 그룹 $X$의 특정 이분(bisection)을 고려하는 하한 추정치를 활용합니다.
   • 만약 하한값 $\hat{\nu}_H(X) > 0$이면, 해당 그룹은 비분리 그룹으로 식별됩니다. 만약 $\hat{\nu}_H(X) = 0$이면, "약한(weakly)" 비분리 그룹으로 취급됩니다.

3. GeneralHare 알고리즘:
   이 체계는 더 이상의 축소가 불가능할 때까지 반복적인 라운드(round)로 작동합니다:

   • 노드 고정 (Node Fixation): 그룹을 식별하기 전에, 로컬 상호작용을 지배하는 선형 항(편향, bias)을 가진 노드들을 특정 값($\pm 1$)으로 고정하여, 이들을 제거하고 인접한 하이퍼엣지(hyperedge)의 차수를 낮춥니다.
   • 식별 (Identification): 알고리즘은 하한 기준을 사용하여 gNG 및 약한 gNG를 탐지하기 위해 하이퍼엣지(크기 제한 $\xi$까지)를 스캔합니다.
   • 확장 (Enlargement): "합집합에 대한 폐쇄성(closure under union)" 성질을 사용하여, 중첩되는 gNG들을 병합하여 더 큰 그룹을 형성합니다.
   • 압축 (Compression): 식별된 그룹들은 단일 노드로 병합됩니다. 이 과정에는 상대적 구성을 일치시키기 위한 스핀 반전, 노드 병합, 그리고 평행한 하이퍼엣지의 가중치 합산이 포함됩니다. 바닥 상태 대응성을 보존하기 위해 이 과정에서 발생하는 가산 상수(additive constants)를 추적합니다.
   • 최적화 (Optimization): 속도를 높이기 위해, 알고리즘은 업데이트된 이웃으로 후보 탐색을 제한하고 독립적인 약한 gNG들의 동시 병합을 채택합니다.

주요 결과
저자들은 합성 하이퍼그래프(Erdős-Rény스 및 Scale-Free)와 공개된 고차 네트워크 데이터셋(예: 접촉 네트워크, 이메일 네트워크)에 대해 GeneralHare를 벤치마킹했습니다.

• 축소 성능:
  • 합성 데이터에 대해, GeneralHare는 상당한 축소 비율(희소한 scale-free 하이퍼그래프에서 최대 ~50%)을 달성했습니다.
  • 그래프 밀도(평균 차수)가 증가하거나 상호작용 차수가 높아짐에 따라 축소 효율이 감소합니다 (4차 그래프는 3차 그래프의 약 절반 수준의 축소 비율을 보였습니다).
  • 실제 데이터셋의 경우, 축소 비율은 2.1%에서 67.4% 사이였으며, 7개 사례 중 5개가 20%를 초과했습니다.
• FastHare (2차 케이스)와의 비교:
  • 2차 이싱 모델에 적용했을 때, GeneralHare는 일반화된 기준 덕분에 더 많은 비분리 그룹을 식별함으로써 표준 FastHare 알고리즘보다 높은 축소 비율을 기록했습니다.
  • GeneralHare는 매우 작은 그래프에서는 더 높은 계산 실행 시간(runtime)이 소요되지만, 약 5,000개의 노드 지점에서 교차점(crossover point)을 지나며 효율적으로 확장되어, 이후에는 더 빠르거나 대등한 성능을 보입니다.
• 차수 감소와의 통합:
  • 본 논문은 GeneralHare를 차수 감소(quadratization) 및 다운스트림 솔버와 결합한 파이프라인을 평가합니다.
  • 결과에 따르면, 차수 감소 전(특히 보수적인 데몬스트레이터인 GH_minimal 사용 시)에 GeneralHare를 적용하는 것이 차수 감소 후 FastHare를 적용하는 것보다 최종 변수 오버헤드를 낮추는 데 효과적입니다.
  • 가장 효과적인 전략으로 확인된 결합 파이프라인은 GeneralHare $\to$ Quadratization $\to$ FastHare입니다.

의의 및 주장
본 논문은 GeneralHare가 고차 이싱 유사 최적화 문제를 위한 해밀토니안 축소의 토대를 마련한다고 주장합니다. 주요 기여는 다음과 같습니다:

1. 이론적 확장: 비분리 이론을 2차에서 임의 차수 모델로 성공적으로 일반화하여, 고차 상호작용에 대한 기술적 공백을 해결했습니다.
2. 실용적 효율성: 문제의 논리적 크기를 줄이는 전처리 도구를 제공함으로써, 탐색 공간을 줄여 다운스트림 휴리스틱 솔버(고전 및 양자 영감 솔버 모두)의 성능을 잠재적으로 향상시킵니다.
3. 바닥 상태 보존: 이 방법은 명시적인 재구성 맵(reconstruction map)을 통해 축소된 해밀토니안의 바닥 상태가 원래 문제의 바닥 상태와 대응됨을 보장합니다.

저자들은 이 방법이 일반적으로 적용 가능하지만, 문제 구조(예: 3-SAT 문제의 균질한 차수 분포)에 따라 효과가 달라질 수 있음을 언급했습니다. 또한 향후 연구로서 특정 문제 클래스를 위한 SAT 솔버와 같은 특화된 솔버와 결합하는 방안을 제시했습니다.