A Quantum-Inspired Algorithm for Graph Isomorphism

이 논문은 광자 양자 샘플러에서 영감을 얻은 통계적 특성을 활용하여 그래프 동형성의 필요 조건을 효율적으로 테스트함으로써 비동형 그래프 쌍을 식별하고, 기존의 양자 및 고전적 접근 방식들과 성능을 벤치마킹하는 고전적 알고리즘을 제시한다.

핵심

개요: "그래프 동형성(Graph Isomorphism)" 퍼즐

서로 다르게 생긴 두 개의 도시 지도가 있다고 상상해 보세요. 한 지도의 거리에는 "A, B, C"라는 이름이 붙어 있고, 다른 지도의 거리에는 "X, Y, Z"라는 이름이 붙어 있습니다. 이름은 다르지만, 두 지도는 사실 정확히 같은 도시의 구조를 보여주고 있을 수도 있습니다.

컴퓨터 과학에서는 이를 그래프 동형성(Graph Isomorphism) 문제라고 부릅니다. "그래프"란 점(정점)들이 선(간선)으로 연결된 네트워크를 말합니다. 질문은 이것입니다: 이 두 네트워크는 이름표만 다를 뿐, 비밀리에 같은 모양을 하고 있는가?

두 개의 작은 지도가 같은지 확인하는 것은 쉽지만, 거대하고 복잡한 네트워크 두 개를 확인하는 것은 일반적인 컴퓨터에게 매우 어려운 일입니다. 이는 마치 산더만한 크기의 건초더미 속에서 특정 패턴을 찾는 것과 같습니다.

배경: "노이즈가 있는" 양자 시대

우리는 현재 NISQ 시대(노이즈가 있는 중간 규모 양자 시대)에 살고 있습니다. 이 시기는 양자 컴퓨터의 "프로토타입 단계"라고 생각하면 됩니다. 이 기기들은 강력하지만 "노이즈가 많고"(오류가 발생하기 쉽고), 가장 어려운 문제를 해결하는 데 필요한 거대하고 완벽한 알고리즘을 아직 실행할 수 없습니다.

과학자들은 이 불완만큼한 기계들로 유용하게 할 수 있는 일들을 찾으려 노력하고 있습니다. 한 가지 아이디어는 **가우시안 보존 샘플러(Gaussian Boson Sampler, GBS)**라고 불리는 특정 유형의 양자 기계를 사용하는 것입니다.

• 비유: 거대하고 복잡한 핀볼 기계를 상상해 보세요(양자 장치). 여러분이 위에서 공(광자)을 쏘아 넣으면, 공들은 미로(그래프) 속의 거울 사이를 튕겨 다닙니다. 그리고 아래쪽의 여러 구멍 중 하나로 떨어집니다. 공들이 떨어지는 패턴은 그 미로의 모양에 대해 무언가를 알려줍니다.

양자 접근 방식의 문제점

이전 연구에서는 이 핀볼 기계를 사용하여 그래프 퍼즐을 푸는 방법을 제안했습니다. 아이디어는 다음과 같습니다:

1. 그래프 A를 기계에 인코딩한다.
2. 공을 쏘고 낙하 패턴을 기록한다.
3. 그래프 B에 대해서도 똑같이 수행한다.
4. 두 패턴을 비교한다.

문제점: 두 그래프가 100% 같다는 것을 확신하려면, 우주의 나이보다 더 오랜 시간 동안 엄청나게 많은 공의 패턴을 수집해야 합니다. 이는 마치 모든 물방울이 떨어질 때까지 기다려서 구름의 정확한 모양을 맞추려는 것과 같습니다. 결코 끝낼 수 없는 일입니다.

저자들의 해결책: "양자에서 영감을 받은" 탐정

이 논문의 저자들은 우리가 모든 공의 패턴을 기다릴 수는 없지만, 일반 컴퓨터를 사용하여 공이 어디에 떨어질지에 대한 통계적 평균을 계산할 수 있다는 점을 깨달았습니다.

그들은 실제 양자 기계가 필요 없이 양자 기계의 논리를 모방하는 새로운 고전 알고리즘(일반 컴퓨터용 프로그램)을 만들었습니다.

알고리즘의 작동 방식 ( "지문" 비유)

두 사람이 쌍둥이인지 알고 싶다고 가정해 봅시다.

1. 레벨 1 (단순 확인): 키와 몸무게를 봅니다. 한 명은 180cm이고 다른 한 명은 150cm라면, 그들은 쌍둥이가 아닙니다. (논문에서의 "1차 상관관계" 확인)
2. 레벨 2 (심층 확인): 키가 같다면, 지문을 봅니다. 지문 패턴이 일치하지 않는다면, 그들은 쌍둥이가 아닙니다. (이것이 "2차 상관관계")
3. 레벨 3 (심층 조사): 지문이 일치하면, DNA를 조사합니다.

저자들의 알고리즘은 그래프에 대해 이 과정을 수행합니다:

• 이 알고리즘은 양자 기계가 어떻게 행동할지에 기초하여 그래프의 특정 통계적 "지문"을 계산합니다.
• 단순한 지문부터 시작합니다. 만약 그래프가 서로 다르다면, 알고리즘은 멈추고 **"이 그래프들은 확실히 다르다"**라고 말합니다.
• 만약 지문이 일치하면, 더 복잡하고 상세한 지문 단계로 넘어갑니다.
• 불일치를 찾아내어 (그래프가 다르다는 것을 증명하거나) 시간이 다 될 때까지 계속해서 더 상세한 단계로 들어갑니다.

그들이 실제로 주장하는 바

이 논문은 몇 가지 구체적인 주장을 하고 있으며, 이를 간단히 요약하면 다음과 같습니다:

1. "필요 조건"을 발견함: 그들은 만약 두 그래프가 진정으로 같다면(동형이라면), 그들의 통계적 지문이 반드시 일치해야 한다는 것을 증명했습니다. 만약 지문이 일치하지 않는다면, 그래프는 확실히 다른 것입니다.
2. 고전적 탐정을 구축함: 그들은 양자 기계 없이도 일반 컴퓨터에서 이러한 지문을 계산하는 프로그램을 작성했습니다.
3. 양자 아이디어만큼 우수함 (하지만 더 빠름): 그들의 고전적 프로그램은 제안된 양자 방식만큼 그래프의 차이를 포착하는 데 능숙하지만, "노이즈" 문제나 수십억 번의 공 낙하를 기다려야 하는 문제로부터 자유롭습니다.
4. 만능 해결책은 아님:
   • 기존의 최선인 고전적 방법(예: "Babai 알고리즘")보다 빠른 것은 아닙니다.
   • 완전한 해결책은 아닙니다. 매우 까다롭고 대칭적인 그래프의 경우, 알고즘은 매우 깊은 단계까지 확인했음에도 불구하고 "두 그래프가 같은지 다른지 알 수 없다"라고 말하며 막힐 수 있습니다.
   • 하지만, 이는 새롭고 독특한 방법입니다. 이 방식은 다른 고전적 방법(예: 이웃들에게 서로 다른 색을 칠해 패턴을 확인하는 "색상 정제(Color Refinement)")과는 다르게 그래프를 바라봅니다.

핵심 요약

저자들은 그래프 퍼즐을 푸는 기존보다 더 빠른 방법을 발명한 것이 아닙니다. 대신, 노이즈가 있는 양자 세계의 멋진 아이디어를 가져와서, 이를 일반 컴퓨터에서 계산하는 법을 알아냈고, "가짜" 일치를 걸러내는 데 도움이 되는 새로운 도구를 만들었습니다.

이렇게 생각해보세요: 양자 기계는 두 그림이 동일하다는 것을 증명하기 위해 수백만 장의 사진을 찍는 비싸고 화려한 카메라입니다. 저자들은 그림이 "다르다"는 것을 훨씬 더 빠르게 증명하기 위해 붓 터치와 색감을 분석하는 스마트한 앱을 만든 것입니다. 이는 유용한 도구이지만, 기존 최고의 미술사학자들(Babai 알고리즘)을 대체하는 것은 아닙니다.

기술 요약

기술 요약: 그래프 동형성을 위한 양자 영감 알고리즘

문제 정의
본 논문은 두 이산 그래프가 정점 레이블의 치환(permutation)을 통해 구조적으로 동일한지 결정하는 그래프 동형성(Graph Isomorphism, GI) 문제를 다룬다. 이 문제는 NP-완전(NP-complete)으로 알려져 있지는 않지만, 다항 시간 내에 작동하는 일반적인 알고리즘을 찾는 것은 이론 컴퓨터 과학에서 여전히 중요한 과제로 남아 있다. 현재 최첨단 고전적 접근 방식인 Babai의 알고리즘(2015)은 준다항 시간($2^{O(\log V)^3}$)으로 작동한다. 저자들은 가우시안 보존 샘플링(Gaussian Boson Sampling, GBS)을 중심으로 한 NISQ(잡음이 있는 중간 규모 양자) 시대가 더 효율적인 해결책을 위한 경로를 제공할 수 있는지 조사한다. 그들은 Brádler 등[13]이 제안한 양자 알고리즘을 비판적으로 평가하고, 그 기저 원리에 영감을 받은 고전적 대안을 제안한다.

방법론
저자들은 물리적인 양자 장치를 사용할 필요 없이, GBS 시스템의 통계적 특성을 활용하여 그래프 동형성을 테스트하는 고전적 알고리즘을 개발한다.

1. 인코딩(Encoding): 인접 행렬 $A$의 Autonne-Takagi 분해($A = UDU^T$)를 사용하여 그래프를 GBS 시스템으로 인코딩한다. 유니터리 행렬 $U$는 간섭계(interferometer)를 정의하며, 고윳값(eigenvalues)을 포함하는 대각 행렬 $D$는 입력 스퀴징(squeezing) 파라미터를 결정한다. 이러한 인코딩은 샘플러의 확률 분포가 그래프의 구조를 반영하도록 보장한다.
2. 통계적 불변량(Statistical Invariants): 물리적 샘플을 수집하는 대신(이는 정확한 분포 근사에는 비효율적이다), 알고리즘은 샘플러 출력 분포의 **모드 상관관계(mode correlations, cumulants)**를 계산한다.
   • GBS에서의 출력 패턴 확률은 하프니언(Hafnian)이라는 부분 행렬의 함수에 의해 지배되며, 이는 클래식하게 계산하기 어려운 함수이다.
   • 그러나 저차 상관관계(lower-order cumulants)는 효율적으로 계산할 수 있다. 저자들은 $k$개 출력 모드 사이의 상관관계를 설명하는 어셀 함수(Ursell functions)를 사용하여 $k$차 상관관계 $C^{(k)}$를 정의한다.
   • 결정적으로, 저자들은 균일한 스퀴징을 가정하지 않고, 그래프의 특정 고윳값을 활용하여 비균일 입력을 결정함으로써 사전 등스펙트럼성(isospectrality, 동형성의 필요 조건) 검사를 수행한다.
3. 알고리즘 프로세스:
   • 분해(Decomposition): 두 그래프의 인접 행렬을 $U$와 $D$로 분해한다.
   • 반복적 상관관계 계산: 차수 $k$를 높여가며(1부터 정점의 개수 $M$까지) 상관관계 값을 계산한다.
   • 치환 필터링(Permutation Filtering): 각 차수 $k$에 대해, 두 그래프 간의 상관관계 값 집합을 비교한다. 초기에는 모두 1로 설정된 후보 치환 행렬 $\sigma$를 유지한다. 만약 그래프 1의 정점에 존재하는 상관관계 값이 그래프 2에는 존재하지 않는다면, $\sigma$의 해당 매핑을 제거(0으로 설정)한다.
   • 종료:
     • $\sigma$가 유효하지 않게 되면(행 또는 열이 비게 되면), 두 그래프는 **비동형(non-isomorphic)**으로 선언된다.
     • $\sigma$가 유일한 치환 행렬으로 축소되면, 두 그래프는 동형임이 검증된다.
     • $\sigma$가 미결 상태로 남아 있으면(여러 매핑이 가능한 경우), 다음 상위 차수 $k+1$로 진행한다.
   • 절단(Truncation): 계산 비용이 지나치게 높아지면 최대 차수 $k_{max}$에서 프로세스를 중단할 수 있다.

주요 기여

• 필요 조건 공식화: 저자들은 샘플러로 인코딩된 그래프의 $k$차 모드 상관관계의 동등성에 기반한 그래프 동형성의 필요 조건을 공식화한다. 그들은 두 그래프가 동형이라면, 모든 $k$에 대해 상관관계 집합이 치환적으로 동등해야 함을 증명한다.
• 고전적 알고리즘: 저자들은 이 필요 조건을 테스트하는 고전적 알고리즘을 도입한다. 이 알고리즘은 그래프의 인접 행렬으로부터 유도된, 효율적으로 계산 가능한 통계적 특성(상관관계)을 사용하여 비동형 그래프를 구별한다.
• 복잡도 분석: 본 논문은 제안된 고전적 알고리즘의 계산 복잡도와 그래프 구별 능력이 Brádler 등[13]의 양자 영감 샘플링 알고리즘 및 고전적 색상 정제(Color Refinement, Weisfeiler-Leman) 알고리즘[23]과 유사함을 보여준다.
• 기존 방법과의 차별점: 저자들은 자신들의 방법이 색상 정제 알고리즘(구체적으로 Weisfeiler-Leman 테스트)과 복잡도 특성을 공유하지만, 서로 다른 정보(샘플러 모드 상관관계 vs 이웃 색상 수)를 평가한다는 점을 명확히 한다. 또한, 그들의 방법이 Cai-Fürer-Immerman 그래프와 같은 특정 그래프 패밀리에 대해 Weisfeiler-Leman 테스트와 동일한 한계를 가질지는 미해결 과제라고 언급한다.

결과 및 한계

• 효율성: 상관관계 값의 계산은 정점의 개수 $M$에 대해 다항 시간 내에 이루어지지만, 상관관계 차수 $k$에 따라 지수적으로 증가한다.
• 구별 능력: 알고리즘은 필요 조건의 위반을 보여줌으로써 비동형 그래프를 성공적으로 식별한다. 그러나 색상 정제 알고리즘과 마찬가지로, 저차 상관관계가 동일하게 나타나는 고도로 대칭적인 그래프(예: 정규 그래프)에서는 어려움을 겪는다.
• 완전성: 저자들은 최대 차수($k=M$)에서 이 방법이 관련 확률 분포를 복구하며, 이론적으로 동형성 테스트에 충분하다고 밝힌다. 그러나 계산 비용이 매우 커지기 때문에 이는 효율적이지 않다.
• 최첨단 기술과의 비교: 본 논문은 자신의 방법이 Babai의 최첨단 준다항 시간 알고리즘보다 범주적으로 덜 효율적임을 명시적으로 주장한다. 이는 일반적인 그래프 동형성 문제에 대한 다항 시간 솔루션을 제공하지 않는다.

의의 및 주장
본 논문은 NISQ 시대의 양자 우위 주장에 대한 비판적 평가로서 자리매김한다. 주요 의의는 다음과 같다:

1. 양자 주장의 실체 규명: Brádler 등의 알고리즘에서 제안된 "양자 우위"가 물리적 양자 장치 없이도 동일한 통계적 특성을 계산함으로써 클래식하게 재현될 수 있음을 보여준다.
2. 한계 설정: 선형 광학 양자 컴퓨터를 사용하는 그래프 동형성에 대한 일반적으로 효율적인 양자 알고리즘이 현재 존재하지 않는다는 견해를 강화한다.
3. 방법론적 차별화: 표준 색상 정제와 달리, 최대 차수에서 충분한 조건을 복구할 수 있는 이론적 능력을 갖춘, GBS 통계에 기반한 새로운 구별 가능한 휴리스틱을 확립한다.

저자들은 자신들의 방법이 비동형 그래프를 구별하는 데 유용한 휴리스틱이 될 수는 있지만, 현재로서는 최선의 고전적 접근 방식에 비해 기능적인 양자 우위를 입증하지 못한다고 결론짓는다.