Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization

기술 요약: 변분 최적화 하의 소규모 그래프 동형성 에너지 지형 구조

문제 정의

본 논문은 두 유한 그래프가 구조적으로 동일한지 결정하는 계산 작업인 그래프 동형성(Graph Isomorphism, GI) 문제를 다룹다. 이 문제는 복잡도 이론에서 독특한 위치를 차지하고 있다(NP-완전으로 증명되지도 않았지만, 다항 시간 내에 해결되지도 않음). 이는 화학, 생물학, 사회 네트워크 분야에서 중요한 실질적 응용 가치를 지닌다.

저자들은 GI를 해결하기 위해 변분 양자 알고리즘(Variational Quantum Algorithms, VQAs), 구체적으로는 **양자 근사 최적화 알고리즘(QAOA)**과 **변분 양자 고유치 계산기(VQE)**의 적용을 조사한다. 핵심 과제는 GI 문제를 이차 비제약 이진 최적화(QUBA) 형식(또는 Ising 해밀토니안)으로 인코딩하는 데 있으며, 여기서 유효한 그래프 동형 쌍은 기저 상태(에너지 0)에 해당한다. 본 연구는 특히 작은 규모의 그래프 인스턴스와 제한된 큐비트 수라는 제약 조건이 있는 노이즈가 있는 중간 규모 양자(NISQ) 환경에서, 변분 최적화가 동형 및 비동형 그래프 쌍을 효과적으로 구별할 수 있는지에 초점을 맞춘다.

연구 방법론

본 연구는 NISQ 조건을 시뮬레이션하기 위해 소규모 그래프 인스턴스(노드 4개 및 5개)를 사용하는 하이브리드 양자-고전 접근 방식을 채택한다.

1. 문제 정식화:

   • 저자들은 선행 연구(Lucas, Zick et al., Calude et al.)에서 유도된 QUBO 정식화를 활용한다.
   • 해밀토니안은 전단사 제약(vertex 간의 일대일 매핑 보장)과 에지 보존(인접성 유지 보장)을 강제하기 위한 페널티 항을 포함한다.
   • 필요한 논리 큐비트 수는 그래프 차수 $n$에 대해 $O(n^2)$로 스케일링되며, 이는 현재의 하드웨어 및 시뮬레이션 제약으로 인해 연구 범위를 작은 $n$으로 제한한다.

2. 알고리즘:

   • QAOA: NISQ 관련 환경을 유지하기 위해 얕은 회로 깊이($p=1$)로 구현된다. 이는 QUBO에서 유도된 비용 해밀토니안과 믹서 해밀토니안을 사용한다.
   • VQE: 더 깊고 표현력이 풍부한 안사츠(5회 반복되는 TwoLocal 회로)와 SPSA 옵티마이저를 사용하여 구현된다. 이는 해밀토니안이 문제 구조를 올바르게 인코딩하는지 확인하기 위한 고정밀 검증 역할을 한다.

3. 분석 프레임워크:

   • 최종 에너지 값에만 의존하는 대신, 저자들은 **최적화 궤적(optimization trajectories)**을 분석한다.
   • 정점 수($N$), 최종 변분 에너지($E_{final}$), 최적화 단계, 총 에너지 감소량($\Delta E$)으로 구성된 특징 벡터를 구축한다.
   • 이 특징들을 일련의 고전 머신러닝 분류기(Logistic Regression, SVM, Random Forest, Gradient Boosting, XGBoost, LightGBM, MLP)에 입력하여, 궤적 수준의 데이터가 동형 및 비동형 쌍 사이의 구별 능력을 개선하는지 테스트한다.

주요 기여 및 결과

1. 동형 쌍의 에너지 클러스터링
본 연구는 동형 그래프 쌍이 변분 에너지 지형에서 일관된 클러스터링을 보임을 관찰한다.

• QAOA: 소규모 시스템($N=4$)의 경우, 동형 쌍은 낮은 에너지 값 주변에 집중된다. 그러나 $N$이 5로 증가함에 따라, 오직 최소 에너지만을 기준으로 구별하는 능력은 급격히 저하된다.
• VQE: 높은 충실도로 클러스터링 현상을 확인하며, 동형 쌍은 0에 가까운 에너지로 수렴하고 비동형 쌍은 양수 값으로 수렴함을 보여준다. 이는 해밀토니안이 구조적 특징을 올바르게 인코딩하고 있음을 검증한다.
• 제어된 절제 실험(Controlled Ablation): 동형성을 유지하면서 그래프 토폴로지(에지 제거)를 변화시키는 실험을 통해, 에너지 변화가 레이블링 아티팩트가 아닌 그래프 구조에 의해 유도됨을 입증하였으며, 이는 해밀토니안 인코딩의 안정성을 확인시켜 준다.

2. 낮은 에너지가 인증 도구로서 갖는 한계
낮은 변분 에너지는 동형성을 보증하는 신뢰할 수 없는 지표라는 점이 핵심적인 발견이다.

• 불가능한 상태(Infeasible States): 최적화 과정에서 전단사 제약(치환 제약)을 위반하는 낮은 에너지 상태로 자주 수렴한다.
• 스펙트럼 중첩(Spectral Overlap): 동형 및 비동형 인스턴스 간에 상당한 에너지 스펙트럼 중첩이 존재한다. 특히 얕은 회로 깊이에서는 많은 비동형 그래프가 동형 그래프와 구별할 수 없는 에너지를 나타낸다.
• 퇴화(Degeneracy): 유효한 치환의 가능한 집합은 전체 힐베르트 공간에 비해 극히 작으므로($N! / 2^{N^2} \to 0$), 지형은 불가능한 중첩 상태에 의해 지배된다.

3. 궤적 기반 분류의 성능
저자들은 단순히 최종 에너지를 보는 것이 아니라 최적화 경로(궤적)를 분석하는 것이 분류 성능을 개선할 수 있는지 테스트했다.

• 결과: 비선형 앙상블 방법(Random Forest, Gradient Boosting)이 선형 분류기보다 우수한 성능을 보였으나, 전반적인 정확도는 여전히 완만했다(최고 정확도 $\approx 75\%$).
• 결론: 이러한 모델들이 신뢰할 만한 분리를 달성하지 못한 것은 분류기가 충분히 표현력이 부족해서가 아니라, 변분 신호 자체가 충분한 식별 정보를 결여하고 있음을 나타낸다. 즉, 낮은 에너지 스펙트럼의 중첩은 현재의 변분 인코딩이 가진 내재적 한계이다.

의의 및 주장

본 논문은 자신의 연구 결과를 확장 가능한 그래프 동형성 솔루션이라기보다 원리 증명(proof-of-principle) 조사로 규정한다.

• 솔버(Solver)가 아닌 진단 도구(Diagnostic Tool): 저자들은 변분 알고리즘이 NISQ 시대에 GI를 위한 솔버로 간주되어서는 안 된다고 주장한다. 대신, 해밀토니안 인코딩의 구조를 탐사하는 진단 도구로서 기능한다. 관찰된 에너지 클러스터링은 해밀토니안이 구조적 특징을 성공적으로 인코딩함을 보여주지만, 에너지 기반의 순수 휴리스틱만으로는 클래스를 분리할 수 없다는 점은 변분 알고리즘의 한계를 부각한다.
• 현재 접근 방식의 한계: 전역적인 치환 제약을 명시적으로 강제하거나 더 발전된 안사츠를 사용하지 않는 한, 변분 알고리즘은 불가능한 저에너지 상태의 범람으로 인해 동형 및 비동형 그래프를 구별하는 데 어려움을 겪을 것임을 강조한다.
• 향후 방향: 본 연구는 더 압축된 QUBO 인코딩, 문제 맞춤형 안사츠, 그리고 제약 인지형 믹서가 필요함을 시사한다. 또한, 시뮬레이션과 실험적 실행 가능성 사이의 간극을 메우기 위해 6~8개 노드로의 스케일링 및 오류 완화 기술을 적용한 실제 하드웨어 테스트가 필요함을 언급한다.

요약하자면, 본 논문은 변분 양자 알고리즘이 그래프 구조에 대응하는 저에너지 분지(basin)를 식별할 수는 있지만, 에너지 최소화 단독으로는 불가능한 상태로의 수렴 가능성과 클래스 간 스펙트럼 중첩으로 인해 확장 가능한 그래프 동형성 구별에 불충분함을 입증한다.