Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

문제 정의

그래프 신경망(GNN)은 "메시지 전달(message passing)" 프리미티브에 힘입어 화학, 생물학 및 최적화 분야의 관계형 데이터 학습의 중심이 되었습니다. 그러나 기존의 양자 대응 모델들은 다음과 같은 상당한 한계에 직면해 있습니다:

1. 진정한 메시지 전달의 부재: 제안된 대부분의 양자 그래프 모델은 양자 회로 내에서 메시지 전달을 수행하지 않습니다. 대신 그래프 에지를 회로 게이트에 매핑한 후, 이웃 정보를 집계하기 위해 고전적인 후처리 과정에 의존하며, 이는 양자 연산의 결맞는(coherent) 이점을 놓치게 됩니다.
2. 표현력의 천장: 표준 메시지 전달 GNN은 1-Weisfeiler–Leman(1-WL) 테스트에 의해 제한됩니다. 즉, 특정 구조적으로 구별되는 그래프(예: 특정 비동형 분자 또는 하위 구조)를 구별할 수 없습니다.
3. 학습 가능성 및 확장성: 변분 양자 회로(VQC)는 회로 크기가 커짐에 따라 그래디언트가 기하급적으로 소실되는 "바렌 플래토(barren plateau)" 문제로 인해 학습이 불가능해지는 경우가 많습니다. 또한, 대규모 그래프 인스턴스에 대해 순열 등변성(permutation equivariance)이나 확장성을 보장하는 양자 모델은 거의 없습니다.

방법론

저자들은 양자 영역 내에서 완전히 작동하는 **부분 공간 보존 회로(subspace-preserving circuits)**를 기반으로 한 양자 그래프 신경망(QGNN) 프레임워크를 소개합니다. 이 아키텍처는 네 가지 핵심 구성 요소로 이루어져 있습니다:

1. 계층적 데이터 로더 ($V$): 시스템은 두 개의 레지스터를 사용합니다:

   • 노드 레지스터 ($N$ 큐비트): 특정 해밍 가중치 $j$에서의 그래프 노드를 인코딩합니다. 기저 상태(Basis states)는 $j$-부분집합(예: $j=1$일 때 단일 노드, $j=2$일 때 에지, $j=3$일 때 삼각형)을 나타냅니다.
   • 임베딩 레지스터 ($D$ 큐비트): 해밍 가중치 $k$에서의 특징(features)을 인코딩합니다.
   • 제어된 Givens 입자 수 인코더(controlled-Givens particle-number encoder)는 노드 특징을 결합 부분 공간 $H^j_N \otimes H^k_D$로 로드합니다.

2. 등변 인접 계층 ($A(G)$): 이 계층은 에지에 대응하는 노드-큐비트 쌍 사이에 Givens 회전을 적용하여 그래프 연결성을 인코딩합니다. 회전 각도는 정준 순서(canonical ordering)에 따른 에지 가중치로부터 유도되며, 이를 통해 노드 레이블에 의존하지 않고 그래프 구조를 준수하도록 보장합니다.

3. 학습 가능한 진화 ($W(\theta)$): 임베딩 레지스터에만 작용하여 노드 특징을 업데이트하는 이 계층은, 역학이 구조화된 부분 공간 내에 머물도록 하여 바렌 플래토를 피하기 위해 부분 공간 보존 게이트(구체적으로는 컴파운드 표현으로 리프트된 $SO(D)$의 Cayley 매개변수화)를 사용합니다.

4. 결합 레지스터 혼합 ($M(\theta_M)$): 마지막 계층은 Givens 회전을 통해 노드 레지스터와 임베딩 레지스터를 결합하여, 구조적 부분 공간과 특징 부분 공간 사이의 정보 흐름을 허용합니다.

핵심 메커니즘:

• 메시지 전달: 회로는 결맞게 메시지 전달을 수행합니다. 인접 계층은 에지를 따라 진폭을 라우팅하고, 학습 가능한 진화는 특징을 업데이트합니다. 각 레이어에서 로더를 재업로드(re-uploading)하는 것은 비선형성을 도입합니다.
• 순열 등변성: 이 아키텍처는 구조적으로 정확하게 순열 등변성을 갖습니다. 학습 가능한 진화가 공유 임베딩 레지스터에만 작용하고, 인접/혼합 계층이 노드 레이블이 아닌 에지 가중치에 기반한 정준 순서를 따르기 때문에, 노드 레이블을 변경하는 것은 함수를 바꾸지 않고 출력의 레이블만 바꿀 뿐입니다.
• 리드아웃(Readout): 특징은 임베딩 레지스터의 일입자 밀도 행렬(1-RDM, $\gamma_{pq} = \langle \psi | a^\dagger_p a_q | \psi \rangle$)을 통해 읽혀집니다. 이는 matchgate shadow나 결정론적 Hartree–Fock 리드아웃을 사용하여 전체 노드 수 $N$과는 독립적으로 다항식 비용($O(D^3/\epsilon^2)$)으로 추정될 수 있습니다.

주요 기여

1. 이론적 보장: 본 논문은 QGNN이 진정한 메시지 전달을 수행하고, 정확하게 순열 등변성을 가지며, $j$-WL 표현력을 달성함을 증명합니다. 노드 레지스터의 입자 수를 $j \ge 3$으로 설정함으로써, 이 모델은 표준 1-WL 테스트(및 따라서 모든 표준 메시지 전달 GNN)가 구분할 수 없는 그래프 쌍을 구별할 수 있습니다.
2. 부분 공간 보존을 통한 확장성: 역학을 고정된 크기의 부분 공간(그래프 크기 $N$이 아닌 $D$와 $k$에 의해 결정됨)에 국한함으로써, 모델은 일반적인 VQC와 관련된 지수적인 그래디언트 소실을 피합니다.
3. 사전 학습 전략: 이 프레임워크는 "작게 학습하여 크게 배포하는(train-small, deploy-large)" 접근 방식을 채택합니다. 학습 가능한 파라미터가 그래프 크기와 무관한 임베딩 레지스터에만 작용하므로, 작은 그래프에서 학습된 모델을 더 큰 모델의 파라미터로 초기화함으로써 더 큰 인스턴스로 전이할 수 있습니다.

결과

본 프레임워크는 세 가지 데이터셋에 대해 최대 56 큐비트에 이르는 대규모 고전 시뮬레이션을 통해 검증되었습니다:

1. Cai–Fürer–Immerman (CFI) 그래프:

   • 목표: 1-WL이 분리할 수 없는 비동형 그래프 쌍을 구별하는 것.
   • 결과: QGNN은 예측된 입자 수($CFI(K_3)$의 경우 $j=3$, $CFI(K_4)$의 경우 $j=4$)에서 정확히 100% 테스트 정확도를 달성한 반면, 1-WL 베이스라인은 무작위 확률 수준에 머물렀습니다. 이는 모델이 1-WL 천장을 초과할 수 있음을 확인시켜 줍니다.

2. QM9 분자 특성 예측:

   • 목표: 130,831개의 분자에 대한 HOMO–LUMO 갭 예측.
   • 결과: 입자 수 $j$를 1에서 3으로 증가시킴에 따라 파라미터 수를 거의 일정하게 유지하면서도 평균 절대 오차(MAE)를 0.398 eV에서 0.235 eV로 줄였습니다. 이는 더 높은 차원의 구조적 해상도가 실제 화학 작업에서 성능을 향상시킨다는 것을 보여줍니다.

3. 유클리드 외판원 문제 (TSP):

   • 목표: $N$개의 도시($N$은 최대 50)에 대한 근사 최적 경로 찾기.
   • 결과: 모델은 $N=50$일 때 1.201의 비율(최적값은 1.0)을 가진 경로를 생성했습니다. 결정적으로, 모델은 이러한 규모에서도 학습이 가능했습니다.
   • 학습 가능성: 큐비트 수가 56까지 증가해도 그래디언트 분산은 지수적이 아닌 다항식적으로 유지되었습니다. (작은 모델에서 학습된 모델로 큰 모델을 초기화하는) 전이 학습은 그래디언트 신호를 무작위 초기화보다 1~2 자릿수 더 높게 유지했습니다.
   • 리드아웃: Matchgate 기반 리드아웃은 계산 기저(computational-basis) 리드아웃보다 성능이 훨씬 뛰어났으며, 작업 수행에 필수적인 비대각(off-diagonal) 정보를 성공적으로 회복했습니다.

의의 및 주장

본 논문은 이론적 보장과 실질적 확장성을 모두 갖춘 **근미래 양자 알고리즘(near-term quantum algorithms)**의 길을 열었다고 주장합니다.

• 이론과 실제의 가교: 메시지 전달, 등변성, WL 계층 구조와 같은 그래프 학습의 원칙을 휴리스틱한 양자 모델을 넘어 양자 회로 설계에 직접 도입했습니다.
• 학습 가능성 해결: 부분 공간 보존 역학 및 사전 학습을 활용함으로써, 바렌 플래토 병목 현상을 해결하고 양자 그래프 모델이 대규모 인스턴스에서도 학습될 수 있음을 입증했습니다.
• 표현력: 복잡한 그래프 구조를 구별할 수 있는 이론적 근거를 제공함으로써, 1-WL 표현력 한계를 뛰어넘는 최초의 증명된 양자 그래프 모델을 제시했습니다.

저자들은 현재 검증이 고전 시뮬레이션을 통해 이루어졌으나, 아키텍처 자체가 근미래 양자 하드웨어(N=50을 위해 약 56 큐비트 필요)와 호환되도록 설계되었으며, 리드아웃 비용은 그래프 크기가 아닌 특징 차원에 따라 다항식적으로 스케일링된다는 점을 강조합니다.