기술 요약: 노드 속성이 있는 그래프를 위한 양자 진화 커널 (Quantum Evolution Kernel)

문제 정의

그래프 머신러닝은 실제 세계의 문제를 표현하는 데 있어 핵심적인 분야이지만, 고전적 방법론들은 상당한 한계에 직면해 있습니다. 전통적인 그래프 커널(예: Weisfeiler-Lehman)은 종종 연속적인 노드 특징을 무시하며, 그래프 합성곱 신경망(GCN)은 이론적으로 1-WL 동형 검사(isomorphism test)에 의해 제한되고, 오버스무딩(over-smoothing) 문제를 겪으며, 그래프 크기가 증가함에 따라 높은 계산 비용이 발생합니다. 또한, 아날로그 양자 그래프 커널에 다수의 연속적인 노드 속성을 통합하는 것은 여전히 미개척 영역으로 남아 있습니다. 본 논문은 특히 양자 커널이 유망한 성능을 보이는 저데이터(low-data) 환경을 대상으로, 중성 원자 양자 프로세서에서 그래프 구조와 연속적인 노드 수준 특징을 모두 인코딩할 수 있는 양자 패러다임의 필요성을 다룹니다.

방법론

제안된 접근 방식은 Pasqal의 중성 원자 양자 프로세서를 사용하여 노드 속성이 있는 그래프를 처리하도록 양자 진화 커널(QEK) 프레임워크를 확장합니다. 방법론은 세 가지 주요 단계로 구성됩니다.

1. 물리적 인코딩 및 해밀토니안 (Physical Encoding and Hamiltonian)

시스템은 세 가지 관련 상태를 가진 중성 원자를 활용합니다: 두 개의 저에너지 초미세 바닥 상태($|g\rangle$ 및 $|h\rangle$)와 하나의 고에너지 리드베리(Rydberg) 상태($|r\rangle$).

• 그래프 구조: 원자의 공간적 배치(spatial positioning)를 통해 인코딩됩니다. 연결된 노드는 반데르발스 힘($1/R^6$)을 통한 상호작나를 가능하게 하기 위해 리드베리 차단 반경($R_b$) 내에 배치되며, 연결되지 않은 노드는 이 반경 밖에 배치됩니다.
• 노드 특징: 리드베리 레이저만을 사용했던 이전 연구들과 달리, 본 방법은 $|g\rangle$ 상태와 $|h\rangle$ 상태를 결합하기 위해 **로컬 라만 레이저 펄스(local Raman laser pulses)**를 도입합니다. 이는 원자당 3레벨(qutrit) 시스템을 생성합니다. 노드 특징 벡터는 정규화되어 블로흐 구(Bloch sphere) 상의 회전각($\theta_1, \theta_2$)으로 매핑되며, 이는 $|g\rangle$와 $|h\rangle$ 사이의 인구 이동(population transfer)을 효과적으로 조절합니다.
• 진화: 시스템은 로컬 회전($U_{local}$)과 글로벌 리드베리 상호작용($U_{int}$)으로 구성된 해밀토니안 하에서 진화합니다. 최종 상태 $|\Psi(t)\rangle$는 이러한 연속적인 층들의 결과물입니다.

2. 측정 및 분포 추출 (Measurement and Distribution Extraction)

하드웨어가 세 가지 상태를 직접 구별할 수 없으므로, 측정은 바닥-리드베리 기저(ground-Rydberg basis, 비트 0은 $|g\rangle$ 또는 $|h\rangle$, 비트 1은 $|r\rangle$)에서 수행됩니다.

• 점유 분포 (Occupation Distribution): 비트 문자열의 해밍 가중치(Hamming weight, 들뜬 원자의 비율)로부터 도출됩니다.
• 상관 분포 (Correlation Distribution): 2점 상관관계 $\langle Z_i Z_j \rangle - \langle Z_i \rangle \langle Z_j \rangle$로부터 도출됩니다.
• 규모 불변성 (Scale Invariance): 이러한 분포들은 크기에 불변하는(size-invariant) 그래프 표현을 생성하기 위해 집계됩니다.

3. 커널 구축 (Kernel Construction)

본 논문은 측정으로부터 도출된 확률 분포 간의 거리를 기반으로 양자 커널을 정의합니다.

• 거리 메트릭: 저자들은 흔히 사용되는 젠슨-샤논(Jensen-Shannon, JS) 거리 대신 와서스테인 거리($W_1$)(Earth Mover's Distance)를 채택했습니다. $W_1$은 기하학적 정보를 보존하고 빈닝(binning)과 관련된 이산화 손실을 피하지만, 시간 복잡도가 더 높습니다.
• 커널 공식화: 커널은 $K(P, Q) = \exp(-\gamma D(P, Q))$로 정의됩니다. 두 가지 집계 전략, 즉 개별 커널의 가중 합과 합산된 거리의 곱이 테스트되었습니다.
• 분류: 생성된 커널은 다중 클래스 분류를 위해 one-vs-one 전략을 사용하는 서포트 벡터 분류기(SVC)에 입력됩니다.

실험 설정

• 데이터셋: MNIST 필기 숫자 데이터셋의 일부가 그래프로 변환되었습니다. 이미지는 이진화, 스켈레톤화(skeletonization), 그리고 그래프 정제(가까운 노드 병합, 공선 노드 제거) 과정을 거쳤습니다.
• 제약 조건: Pasqal의 Pulser 라이브러리를 이용한 시뮬레이션 제한으로 인해, 그래프는 노드 수 $|V| \le 9$인 것들로 필터링되었습니다.
• 특징 (Features): 네 가지 노드 수준 특징이 인코딩되었습니다: 픽셀 좌표(스케일링됨), 연속된 에지의 편차 각도, 그리고 이등분선 방향.
• 베이스라인: 본 방법은 다양한 특징 구성을 가진 고전적 Weisfeiler-Lehman(WL) 그래프 커널 및 그래프 합성곱 신경망(GCN)과 비교되었습니다.

주요 결과

1. 거리 메트릭의 효능: 와서스테인 거리가 모든 훈련 세트 크기에서 젠슨-샤논, 헬링거(Hellinger), L2 거리보다 가장 높은 평균 정확도를 달립했습니다. JS 거리는 약간 낮은 성능을 보였으며, 빈(bin)의 수를 늘릴 때 성능이 저하되었는데, 이는 연속 분포를 처리하는 데 있어 $W_1$의 능력이 우수함을 시사합니다.
2. 특징의 중요성: 노드 수준의 특징을 포함한 양자 커널이 특징이 없는 버전보다 높은 성능을 보였으며, 이는 로컬 정보가 분류를 강화함을 확인시켜 줍니다.
3. 고전적 베이스라인과의 비교:
   • GCN이 딥러닝 모델의 기대대로 가장 높은 전체 정확도를 달성했습니다.
   • 양자 커널(와서스테인 사용)은 위치 정보만을 사용한 WL 커널과 대등한 성능을 보였으며, 각도 정보만을 사용하거나 특징이 없는 WL 커널보다는 우수한 성능을 보였습니다.
   • 그러나 양자 커널은 위치-각도 결합 WL 커널이나 GCN을 평균 정확도 면에서 능가하지 못했습니다.

의의 및 주장

본 논문은 아날로그 중성 원자 하드웨어에서 다중 속성 연속 특징을 인코딩하는 것이 구조적으로 가능하다는 것을 입증한다고 주장합니다. 주요 기여는 다음과 같습니다:

• 새로운 인코딩: 라만 레이저를 통해 원자당 3레벨 시스템을 도입함으로써, 노드 특징 인코딩을 위상적 인코딩과 분리하여 로컬 힐베르트 공간을 풍부하게 만들었습니다.
• 메트릭 선택: 양자 측정 분포에 기반한 그래프 커널 작업에서 와서스테인 거리가 젠슨-샤논 메트릭보다 더 효과적임을 확립했습니다.
• 프로토타입 검증: 단순한 회로 설계와 짧은 진화 시간에도 불구하고, 이 방법이 분류 작업에 유용한 상관관계 기반 정보를 추출할 수 있음을 보여주었습니다.

저자들은 현재의 성능에 대해 겸허한 태도를 유지하며, 단순한 회로 설계와 짧은 진화 시간이 최첨단 고전적 커널이나 GCN을 능가하는 것을 방지했다고 언급했습니다. 이들은 더 정교한 인코딩과 긴 진화 시간을 갖춘 개선된 설계가 성능을 향상시킬 수 있다고 가정합니다. 본 연구는 향후 대규모 구현을 위한 베이스라인 역할을 하며, 실제 하드웨어에서 인코딩이 그래프 크기에 따라 선형적으로 확장되는 반면, 상관 행렬에 대한 고전적 후처리 비용을 관리하는 것이 확장성에 있어 중요한 과제임을 강조합니다.