Lovász theta and Shearer lower bounds on Quantum Max Cut

기술 요약: 양자 Max Cut에 대한 로바스 테타(Lovász Theta) 및 셰어러(Shearer) 하한

문제 정의
본 논문은 고전적 Max Cut 문제를 양자 다체 물리 영역으로 일반화한 양자 Max Cut(QMC) 문제를 다룬다. 고전적 Max Cut이 그래프의 정점들을 분할하여 교차하는 에지의 수를 최대화하는 것을 목표로 한다면, QMC는 해밀토니안 $H_{qmc} = \frac{1}{4} \sum_{uv \in E} (I - X_u X_v - Y_u Y_v - Z_u Z_v)$의 최대 고윳값을 구하는 문제이다. 이 해밀토니안은 물리적으로 반강자성 하이젠베르크 해밀토니안(anti-ferromagnetic Heisenberg Hamiltonian)의 음의 값에 해당하며, 이는 양자 자성 모델의 근간이 되는 중요한 모델이다. 본 연구의 목적은 임의의 그래프에 대해 (특히 곱 상태(product states)에 의해 달성 가능한) 지표면 에너지(또는 이와 동등한 $H_{qmc}$의 최대 고윳값)에 대한 엄밀한 하한을 설정하는 것이다.

방법론
저자는 고전적 근사 알고리즘을 위해 개발된 Briët-de Oliveira Filho-Vallalez(BOV) 프레임워크를 변형한 확률적 라운딩(probabilistic rounding) 기법을 사용한다. 핵심 방법론은 다음과 같다:

1. 벡터 표현: 그래프의 보그래프(complement graph)에 대한 로바스 테타 함수 $\vartheta(\bar{G})$를 활용하여, 모든 에지 $uv \in E(G)$에 대해 $\langle x_u, x_v \rangle = -1/(\vartheta(\bar{G}) - 1)$을 만족하는 단위 벡터 $\{x_u\}$를 정점들에 할당한다.
2. 무작위 라운딩: 표준 정규 분포를 따르는 무작위 행렬 $Z \in \mathbb{R}^{3 \times n}$을 사용하여 이 고차원 벡터들을 1-큐비트 상태로 매핑한다. 구체적으로, 각 정점 $u$에 대해 $y_u = Zx_u / \|Zx_u\|$인 단위 벡터를 생성하며, 이는 블로흐 구(Bloch sphere) 상의 단일 큐비트 밀도 행렬 $\varrho_u$를 정의하는 곱 상태 $\varrho_\vartheta = \bigotimes_{u} \varrho_u$를 결정한다.
3. 기댓값 분석: 에너지의 기댓값 $\mathbb{E}[\text{tr}(H_{qmc} \varrho_\vartheta)]$를 계산한다. 이를 위해서는 라운딩된 벡터들의 내적의 기댓값 $\mathbb{E}[y_u \cdot y_v]$를 평가해야 하며, 이는 원래 벡터들의 내적과 하이퍼지오메트릭 함수(hypergeometric function) $\hat{F}(r, u \cdot v)$를 통해 연결된다.
4. 부등식 유도: 증명은 고전적 Max Cut 분석에서 사용되는 아크사인(arcsine) 함수의 알려진 성질을 일반화하는 함수 $\hat{F}(r, \alpha)$ (여기서 $r=3$은 전체 QMC 해밀토니안에 해당)에 대한 특정 부등식을 확립하는 데 의존한다.

주요 기여 및 결과

1. 로바스 테타 하한:
   본 연구의 주요 결과는 $m$개의 에지를 가진 그래프의 QMC 값 $qmc(G)$에 대한 새로운 하한이다:
   $$qmc(G) \geq \frac{m}{4} \left( 1 + \frac{8}{3\pi} \frac{1}{\vartheta(\bar{G}) - 1} \right)$$
   이 하한은 곱 상태에 의해 달성된다. 증명 과정은 고전적 Max Cut에 관한 Balla, Janzer, 그리고 Sudakov [BJS24]의 결과를 확장한다. 저자는 계수 $\frac{8}{3\pi} \approx 0.8488$이 고전적 계수인 $\frac{2}{\pi} \approx 0.6366$보다 엄격히 크다는 점을 언급하며, 이는 양자 라운딩 전략이 이 문맥에서 고전적 전략보다 우수함을 나타낸다.

• 벡터 색수(Vector Chromatic Number): $\vartheta(\bar{G})$를 벡터 색수 $\chi_{vec}(G)$로 대체함으로써 하한을 강화할 수 있다 ($\chi_{vec}(G) \leq \vartheta(\bar{G})$ 이므로).
• 차수 기반 완화(Degree-Based Relaxation): 최대 차수가 $\Delta$인 그래프의 경우, $\vartheta(\bar{G}) \leq \Delta + 1$ 관계를 사용하여 하한을 $qmc(G) \geq \frac{m}{4} (1 + \frac{8}{3\pi\Delta})$로 완화할 수 있다. 이는 양자 물리학에서 흔히 나타나는 유계 차수를 가진 그래프(예: 격자 구조)에 특히 유용하다.

2. 삼각형 없는 그래프(Triangle-Free Graphs)를 위한 셰어러 유형 하한:
   본 논문은 Carlson 등의 연구와 셰어러(Shearer)의 결과를 양자 설정으로 확장한다. 고전적 Max Cut의 반정부호 프로그래밍(SDP) 완화에 기반한 특정 벡터 안사츠(ansatz)를 구축함으로써, 저자는 셰어러 하한의 양자 아날로그를 도출한다.

• 삼각형 없는 그래프에 대해 $m$개의 에지가 있을 때, 논문은 다음을 증명한다:
  $$qmc(G) \geq \frac{m}{4} + \frac{2m^{3/4}}{3\pi}$$
• 이 결과는 아크사인 함수를 포함하는 부등식을 하이퍼지오메트릭 함수 $\hat{F}(3, \cdot)$로 일반화함으로써 도출된다. 구체적으로, 비음의 $\alpha, \beta$에 대해 $\hat{F}(3, \alpha - \beta) \leq \frac{3\pi}{8}(\alpha - \beta)$임을 증명한다.

의의 및 주장
본 논문은 고전적 결과와 유사하게 로바스 테타 함수나 셰어러 하한과 같은 그래프 불변량을 통해 표현되는 양자 Max Cut의 첫 번째 명시적 하한을 제공한다고 주장한다. 그 의의는 다음과 같다:

• 이론적 통합: 고전적 근사 알고리즘(Max Cut)과 양자 다체 문제(하이젠베르크 해밀토니안) 사이의 간극을 고전적 라운딩 기법을 양자 연산자 설정에 적응시킴으로써 메꾼다.
• 곱 상태의 최적성: 이러한 비자명한 하한들이 복잡한 얽힌 상태(entangled states)가 아닌, 준비와 분석이 계산적으로 효율적인 단순한 곱 상태에 의해 달성될 수 있음을 보여준다.
• 물리적 관련성: 차수에 의존하는 하한은 결함이 있는 격자와 같이 연결성이 제한된 물리적으로 유의미한 시스템의 바닥 상태 에너지를 추정하기 위한 실질적인 도구를 제공한다.

저자는 증명 기법이 QMC 항의 일부만을 포함하는 해밀토니안(예: $H_{XX}$)에도 적용되어, 라운딩 공간의 차원 $r$에 따라 다른 계수를 생성할 수 있다고 명시적으로 밝힌다. 본 연구는 이론적 하한을 넘어선 새로운 실험적 설정이나 미래의 알고리즘 개발을 제안하지 않는다.