Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs

기술 요약: 방향 그래프의 해밀턴 경로 문제를 위한 이분형 가우시안 보존 샘플링(Bipartite Gaussian Boson Sampling)

문제 정의

본 논문은 모든 정점을 정확히 한 번씩 방문하는 사이클이 방향 그래프에 존재하는지 결정하는 고전적인 NP-완전 문제인 방향 해밀턴 사이클(directed Hamiltonian cycle) 문제를 다룹니다. 표준 가우시안 보존 샘플링(GBS)은 대칭 행렬을 인코딩하는 해프니언(Hafnian) 함수를 활용하여 무방향 그래프 문제에는 성공적으로 적용되어 왔으나, 방향 그래프에는 적합하지 않습니다. 방향 그래프는 본질적인 비대칭 구조(비대칭 인접 행렬)를 가지고 있는데, 표준 GBS는 이를 대칭적 임베딩을 통해 구조를 왜곡하지 않고는 자연스럽게 인코딩할 수 없습니다. 또한, 방향 그래프를 위한 기존의 휴리스틱 방법들은 탐색 공간의 지수적 규모 문제로 인해 어려움을 겪는 경우가 많습니다.

방법론

저자들은 클래식 유전 알고리즘(GA)을 위한 휴리스틱 정보를 생성하기 위해 **이분형 가우시안 보존 샘플링(Bipartite Gaussian Boson Sampling, BipartiteGBS)**을 활용하는 프레임워크를 제안합니다.

1. 이론적 기초 (BipartiteGBS):

   • 단일 모드 압축 상태(single-mode squeezed states)를 사용하여 대칭 행렬의 제곱 해프니언에 비례하는 확률을 산출하는 표준 GBS와 달리, BipartiteGBS는 **이중 모드 압축 상태(two-mode squeezed states)**와 두 개의 간섭계를 사용합니다.
   • 이 아키텍처를 통해 출력 확률은 임의의 (비대칭) 복소 행렬의 부분 행렬의 **제곱 퍼머넌트(squared permanents)**에 비례하게 됩니다. 이는 BipartiteGBS가 방향 그래프의 인접 행렬을 인코딩하는 데 자연스러운 후보가 되게 합니다.
   • 저자들은 $k \times k$ 부분 행렬 중 제곱 퍼머넌트를 최대화하는 행렬을 찾는 Max-Perm 문제를 정의합니다. 이들은 **샘플링 향상 계수(sampling enhancement factor, $R_{Per}$)**에 대한 폐쇄형 식을 도출하여, BipartтеGBS가 균등한 클래식 샘플링에 비해 큰 퍼머넌트를 가진 부분 행렬에 대해 상당한 편향(bias)을 제공함을 입증했습니다.

2. 휴리스틱 매핑:

   • 본 논문은 방향 그래프의 인접 행렬의 퍼머넌트와 에지 밀도(edge density) 사이의 연결 고리를 확립합니다. 큰 퍼머넌트가 해밀턴 사이클을 보장하는 것은 아니지만, 이는 사이클 커버(cycle covers)를 포함하는 조밀한 국소적 하부 구조의 존재를 시사합니다.
   • 저자들은 BipartiteGBS 샘플을 "정보가 풍부한" 국소적 증거로 취급합니다. 구체적으로 다음을 추출합니다:
     • 정점 부분 집합 (Vertex Subsets): 충돌이 없는 균형 잡힌 샘플에서 빈번하게 함께 나타나는 정점 세트 ($S \cup T$).
     • 에지 동시 발생 빈도 (Edge Co-occurrence Frequencies): 이러한 샘플링된 정점 풀 내에서 방향 에지의 양 끝점이 함께 나타나는 경험적 빈도.

3. 알고리즘 통합 (BipartiteGBS-GA):

   • BipartiteGBS로부터 유도된 데이터를 사용하여 **유전 알고리즘(GA)**을 강화합니다.
   • 유도된 초기화 (Guided Initialization): 초기 집단은 순수하게 무작위적인 순열이 아니라, BipartiteGBS로 샘플링된 부분 그래프와 높은 빈도의 에지를 사용하여 구성된 순열으로 씨앗(seed)을 심습니다.
   • 강화된 적합도 (Enhanced Fitness): 적합도 함수는 표준 메트릭(경로 내 유효한 에지의 비율)과 BipartiteGBS에서 유도된 에지 동시 발생 빈도에 기반한 가중 항을 결합합니다.
   • 유도된 변이 (Guided Mutation): 변이 연산자는 양자 샘플링 데이터의 안내를 받아 가끔 낮은 빈도의 에지를 수정(repair)하는 것을 목표로 합니다.
   • 다단계 변형 (MS-BipartiteGBS-GA): 두 단계 접근법이 제안됩니다. 먼저 빠른 클래식 GA를 실행하여 좋은 경로를 찾고, 그 후 해당 에지들을 강화한 뒤 BipartiteGBS가 가이드하는 GA를 실행하여 탐색을 정교화합니다.

주요 기여

• BipartiteGBS의 새로운 적용: 본 논문은 표준 GBS의 대칭 제약을 넘어, 방향 그래프 문제를 위해 BipartiteGBS 기반 알고리즘을 제안한 첫 사례입니다.
• Max-Perm 문제 정식화: Max-Perm 문제를 BipartiteGBS를 위한 전형적인 최적화 과제로 도입하고, 균등한 클래식 샘플링 대비 이론적인 샘플링 향상 계수를 도출했습니다.
• 하이브리드 양자-클래식 프레임워크: 양자 샘플링이 구조적 사전 정보(부분 그래프 및 에지 빈도)를 제공하여 클래식 확률적 최적화 도구를 가이드하는 실용적인 파이프라인을 보여줍니다.
• 절제 실험 분석 (Ablation Analysis): 엄격한 구성 요소별 테스트를 통해, BipartiteGBS 유도 초기화가 성능 향상의 지배적인 기여자임을 확인했으며, 적합도 및 변이 연산자에 대한 지속적인 편향은 수익 체감 또는 중립적인 결과를 낳음을 밝혀냈습니다.

결과

수치 시뮬레이션은 크기 $n=15$에서 $n=40$, 에지 확률 $p=0.3$인 Erdős–Rényi 무작위 방향 그래프를 대상으로 수행되었습니다.

• 성공률: BipartiteGBS가 강화된 알고리즘들(BipartiteGBS-GA 및 MS-BipartiteGBS-GA)은 표준 GA 및 차수 중심성 기반 GA(Degree-GA)보다 일관되게 높은 해밀턴 사이클 발견 성공률을 기록했습니다. 예를 들어, $n=40$에서 MS-BipartiteGBS-GA는 표준 GA의 ~60.0% 대비 ~71.3%의 성공률을 달old했습니다.
• 경로 길이: 완전한 해밀턴 사이클을 찾지 못한 경우에도, BipartiteGBS가 강화된 방법들은 현저히 더 긴 유효 경로를 생성하였으며, 이는 부분적인 구조 정보를 추출하고 활용하는 능력이 우수함을 나타냅니다.
• 절제 실험 결과: "InitOnly" 변형(BipartiteGBS 데이터를 초기화에만 사용하는 방식)이 전체 BipartiteGBS-GA(적합도와 변이까지 수정하는 방식)보다 종종 더 나은 성능을 보였습니다. 이는 양자 샘플링이 초기 집단을 위한 제안 메커니즘으로서 가장 효과적이며, 이후의 정교화 작업에는 표준 진화 연산자가 더 적합함을 시사합니다.
• 베이스라인 비교: 단순 정점 차수 통계를 사용하는 Degree-GA는 표준 GA보다 낮은 성능을 보였으며, 이는 개선이 단순한 정점 중심성이 아닌 BipartiteGBS가 제공하는 구조적 정보(부분 그래프 및 동시 발생)에서 기인함을 확인시켜 줍니다.

의의 및 주장

본 논문은 퍼머넌트 기반 광자 샘플링이 비대칭 조합 탐색 문제에 유용한 알고리즘 가이드를 제공할 수 있다고 주장합니다.

• 휴리스틱 성격: 저자들은 자신들의 결과가 휴리스틱한 향상을 나타내는 것이며, 해밀턴 사이클 문제를 해결하기 위한 복잡도 이론적 양자 우위를 주장하는 것이 아님을 명시했습니다. 이 방법은 더 나은 시작점과 구조적 사전 정보를 제공함으로써 클래식 탐색의 효율성을 높입니다.
• 확장성: 이 접근 방식은 양자 샘플링 단계가 그래프 인스턴스당 한 번의 전처리 비용으로 설계되어 있어 확장 가능하며, 실제적인 무거운 작업은 클래식 GA가 수행합니다.
• 향 향후 방향: 저자들은 이 프레임워크가 외판원 문제(TSP)와 같은 다른 방향 그래프 문제로 자연스럽게 확장될 수 있다고 제안하며, 실제 환경의 노이즈와 손실의 영향을 평가하기 위해 광자 칩에서의 실험적 구현이 다음 단계임을 언급했습니다.