A 0.651-approximation to quantum Max Cut via Rydberg atoms

기술 요약: 리드베리 원자를 이용한 양자 Max Cut에 대한 0.651 근사

문제 정의
본 논문은 반강자성 하이젠베르크 해밀토니언의 바닥 상태 에너지를 찾는 것과 동등한 문제인 양자 Max Cut (QMC) 문제를 다룬다. 이 문제는 QMA-완전(QMA-complete)하며, 이는 범용 양자 컴퓨터를 사용하더라도 효율적으로 해결할 수 없음을 의미한다. 목표는 최적의 바닥 상태 에너지에 대해 특정 비율($\alpha$) 내의 해를 보장하는 근사 알고리즘을 찾는 것이다. 준데프리미티브(semidefinite programming, SDP) 완화에만 의존하는 기존의 최첨단 고전적 방법들은 $\alpha = 0.614$의 근사 비율을 달성한다.

방법론: 하이브리드 양자-고전 접근 방식
저자들은 리드베리 원자 시스템의 자연스러운 양자 역학과 고전적 최적화 기법(SDP 및 무작위 반올림)을 통합하는 하이브리드 알고리즘을 제안한다. 방법론은 네 가지 단계로 진행된다:

1. 인코딩 및 어닐링 (Encoding and Annealing):
   그래프 $G=(V, E, \omega)$로 정의된 QMC 인스턴스는 리드베리 원자 배열로 인코딩된다. 리드베리 해밀토니언 $H_r$의 정적 부분은 그래프의 에지에 대응하는 $XX + YY$ 상호작용 항을 포함하도록 구성된다:
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   시스템은 근사 바닥 상태 $\varrho_r$을 준비하기 위해 어닐링 과정을 거친다.

2. 측정 및 제약 조건 공식화 (Measurement and Constraint Formulation):
   어닐링된 상태 $\varrho_r$에서 모든 에지에 대한 기대값 $\langle X_i X_j + Y_i Y_j \rangle$을 측정한다. 이 값들은 후속 고전적 최적화 단계를 위한 경험적 제약 조건 역할을 한다.

3. 준데프리미티브 프로그래밍 및 반올림 (Semidefinite Programming and Rounding):
   의사 모멘트 행렬(pseudo-moment matrix) $\Delta$는 리드베리 측정값과 파울리 연산자의 대수적 관계를 제약 조건으로 하여 SDP를 통해 최적화된다. 이 행렬은 무작위 투영 기법(Cholesley 분해 후 $\mathbb{R}^{4n}$에서 $\mathbb{R}^3$로의 무작위 투영)을 사용하여 곱 상태(product state) $\varrho_p$로 반올림된다.

4. 최종 상태 선택 (Selection of Final State):
   알고리즘은 더 낮은 에너지를 가진 상태, 즉 리드베리 바닥 상태 $\varrho_r$ 또는 고전적으로 반올림된 곱 상태 $\varrho_p$를 반환한다.

주요 이론적 기여
본 논문은 기존의 최선이었던 0.614를 능가하는 0.651의 조건부 근사 비율을 확립한다. 이 도출은 두 가지 주요 이론적 통찰에 기반한다:

• 리드베리 바닥 상태를 통한 하한 (Lower Bound via Rydberg Ground State): 저자들은 전체 QMC 해밀토니언($H_{qmc}$)의 바닥 상태 에너지가 리드베리 해밀토니언($H_r$)의 에너지를 통해 하한을 가질 수 있음을 증명한다. 하이젠베르크 모델의 $SU(2)$불변성을 활용하여, 최적의 바닥 상태에서는$XX, YY, ZZ$의 기대값이 같음을 보여준다. 이를 통해 리드베리 시스템으로부터 얻은 부분적인$XX+YY$ 측정값으로부터 전체 QMC 에너지를 재구성할 수 있다.
• 반올림을 통한 상한 (Upper Bound via Rounding): 논문은 SDP 반올림에 의해 생성된 곱 상태 $\varrho_p$의 에너지를 분석한다. 저자들은 측정된 상관관계를 바탕으로 이 상태의 기대 에너지에 대한 해석적 표현을 도출한다.
• 비율의 최적화 (Optimization of the Ratio): 리드베리 상태로부터 도출된 하한과 (리드베리 상태 및 곱 상태로부터의) 상한을 결합함으로써, 상관 매개변수 $t_{ij}$에 대한 최소화 문제를 공식화한다. 이를 해결함으로써 0.651의 비율을 얻는다.

결과 및 강건성

• 근사 비율: 알고리즘은 $\kappa = 0.651$의 조건부 근사 비율을 달성한다.
• 노이즈에 대한 강건성: 알고리즘의 중요한 발견은 불완전한 바닥 상태 준비에 대한 강건성이다. 저자들은 리드베리 어닐링 과정이 실제 리드베리 바닥 상태 에너지의 89%($\eta = 0.89$)에 해당하는 에너지만을 생성하더라도 0.651의 이점이 유지됨을 입증한다. 이 임계값 아래로 떨어지면 순수 고전적 SDP 방법 대비 이점이 감소한다.
• 계산 복잡도: 이 하이브리드 접근 방식은 고전적 최적화 문제의 차원을 줄인다. 얽힘 상태를 대상으로 하는 고전적 방식은 $O(n^4)$의 실수 변수를 필요로 하지만, 이 하이브리드 방식은 양자 시스템을 활용하여 얽힘 구조의 복잡성을 처리함으로써 $O(n^2)$개의 변수로 작동한다.

의의
본 논문은 하이브리드 양자-고전 알고리즘의 새로운 경로를 열었다고 주장한다. 이는 양자 하드웨어(특히 리드베리 원자 배열)를 고전적 최적화와 결합하는 것이, 양자 하드웨어가 밑바탕이 되는 해밀토니언 문제를 완벽하게 해결하지 못하더라도 순수 고전적 방법보다 더 강력한 근사 보장을 제공할 수 있음을 보여준다. 이 연구는 양자 플랫폼이 고품질의 하한과 고전적 반올림 절차의 시작점을 제공하는 효과적인 "대리물(proxies)" 역할을 할 수 있으며, 이를 통해 순수 고전적 접근 방식의 계산적 스케일링 한계를 우회할 수 있음을 시사한다.