기술 요약: 양자 동형 및 동형 불구별성을 위한 NPA 계층 구조

1. 문제 정의 및 동기

본 논문은 그래프 간의 **양자 동형(quantum isomorphism)**에 대한 계산적 및 구조적 특성화를 다룬다. 두 그래프 $G$와 $H$가 양자 동형($G \cong_q H$)이라는 것은 공유된 얽힘과 국소 측정을 포함하는 그래프 동형 게임에 대한 완벽한 양자 전략이 존재함을 의미한다.

고전적 그래프 동형 문제는 준다항 시간(quasipolynomial time) 내에 해결 가능(decidable)하지만, Mančinska와 Roberson [FOCS'20]은 양자 동형을 결정하는 문제가 일반적으로 **결정 불가능(undecidable)**함을 증명했다. 이는 양자 상관관계를 근사하기 위한 일련의 준정부호 계획법(semidefinite programming, SDP) 완화 기법인 NPA 계층(NPA hierarchy)(Navascués, Pironio, Acín의 이름을 딴 것)에 대한 연구를 촉발했다.

동형 불구별성(homomorphism indistinguishability)의 부상하는 이론에서 핵심적인 질문은, 이러한 SDP 완화의 각 단계의 타당성(feasibility)을 조합론적으로 특성화할 수 있는가 하는 점이다. 구체적으로 저자들은 다음과 같이 질문한다: $(G, H)$-동형 게임에 대한 NPA 계층의 $k$번째 단계의 타당성이 $G$와 $H$가 특정 그래프 클래스에 대해 동형 불구별(homomorphism indistinguishable)한 것과 동치인가?

2. 방법론 및 증명 기법

본 논문은 대수적 조합론, 연산자 이론, 그리고 그래프 이론의 합성을 활용한다. 핵심 방법론은 **이중 라벨링 그래프(bilabelled graphs)**와 동형 텐서(homomorphism tensors) 사이의 대응 관계에 의존한다.

주요 도구

• 이중 라벨링 그래프와 동형 텐서: $(k, l)$-이중 라벨링 그래프 $F = (F, u, v)$는 텐서 $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$와 연관되며, 여기서 엔트리는 입력 라벨 $u$를 $x$로, 출력 라벨 $v$를 $y$로 매핑하는 동형(homomorphism)의 수를 센다. 이중 라벨링 그래프의 조합론적 연산(직렬 합성, 병렬 합성, 라벨의 순환 치환)은 텐서의 대수적 연산(행렬 곱셈, 슈어 곱(Schur product), 치환)에 대응한다.
• NPA 계층 재정식화: 저자들은 $k$번째 단계의 NPA 계층에 대한 증명서(certificate)의 존재를 **레벨-$k$ 양자 동형 맵(level-$k$ quantum isomorphism map)**의 존재로 재정식화한다. 이는 특정 구조적 성질을 보존하는 행렬 대수 사이의 완전 양의 맵(completely positive map)이다.
• 대수적 $k$-동치(Algebraic $k$-equivalence): 저자들은 특정 원자적 그래프들의 동형 텐서에 의해 생성되는 부분 대수 사이의 대수 동형(algebra isomorphism)으로 정의되는 대수적 $k$-동치의 개념을 도입한다.

증명 구조

주요 정리의 증명은 다음의 동치 사슬을 통해 진행된다:

1. NPA 타당성 $\iff$ 양자 동형 맵: NPA 증명서의 주 부분 행렬(principal submatrix)은 완전 양의 맵의 Choi 행렬으로 해석된다. NPA 계층의 제약 조건은 레벨-$k$ 양자 동형 맵의 공리들과 동치임이 밝혀진다 (정리 3.6).
2. 양자 동형 맵 $\iff$ 대수적 $k$-동치: 양자 동형 맵은 특정 원자적 그래프들 $Q_k$의 동형 텐서에 의해 생성되는 대수들 사이의 동형으로 제한됨이 보여진다 (정리 3.9).
3. 대수적 $k$-동치 $\iff$ 동형 불구별성: 그래프 연산과 텐서 대수 사이의 대응 관계를 사용하여, 그러한 대수 동형의 존재는 $G$와 $H$가 구성된 그래프 클래스 $P_k$로부터 동일한 동형 개수를 가짐과 동치임이 보여진다 (정리 4.4).

3. 주요 기여 및 결과

주요 정리 (정리 1.1)

그래프 $G, H$와 정수 $k \ge 1$에 대하여, 다음은 동치이다:

1. $(G, H)$-동형 게임에 대한 $k$번째 단계의 NPA 계층이 타당하다.
2. $G$에서 $H$로의 레벨-$k$ 양자 동형 맵이 존재한다.
3. $G$와 $H$는 대수적으로 $k$-동치이다.
4. $G$와 $H$는 그래프 클래스 $P_k$에 대해 동형 불구별이다.

여기서 $P_k$는 원자적 그래프 $Q_k$로부터 직렬 합성, 특정 원자적 그래프와의 병렬 합성, 그리고 순환 라벨 치환을 사용하여 귀납적으로 구성된 **평면 이중 라벨링 그래프(planar bilabelled graphs)**의 클래스이다.

그래프 클래스 $P_k$의 성질

• 평면성(Planarity): $P_k$의 모든 그래프는 평면 그래프이다 (보조정리 4.7).
• 유계된 트리의 폭(Bounded Treewidth): $P_k$의 기저 그래프들은 최대 $3k-1$의 트리의 폭을 갖는다 (보조정리 4.5).
• 마이너 폐쇄성(Minor-Closed): 클래스 $P_k$는 마이너(minor)를 취하는 것에 대해 닫혀 있다 (보조정리 4.8).
• 합집합(Union): 모든 $k \in \mathbb{N}$에 대한 $P_k$의 기저 라벨 없는 그래프들의 합집합은 정확히 모든 평면 그래프의 집합이다 (결론 4.12).

알고리즘 결과 (정리 1.2)

본 논문은 고정된 $k$에 대해 NPA 계층의 정확한 타당성을 결정하는 무작위 다항 시간 알고리즘을 제시한다.

• 실행 시간: $n^{O(k)} k^{O(1)}$, 여기서 $n = \max\{|V(G)|, |V(H)|\}$이다.
• 방법: SDP를 직접 푸는 대신, 무작위로 선택된 소수 $p$에 대해 $P_k$ 상에서의 동형 불구별성을 확인한다. 유한체 위에서 $P_k$에 속하는 그래프들의 동형 텐서들에 의해 생성되는 벡터 공간의 기저를 계산한다.
• 의의: 이는 표준 SDP 솔버(예: 타원체 방법)에 내재된 근사 문제를 피하며, 고정된 단계에 대한 정확한 결정 절차를 제공한다.

Mančinska와 Roberson [FOCS'20]의 대안적 증명

NPA 계층의 수렴성과 $\bigcup_k P_k$가 모든 평면 그래프라는 사실을 주 정리와 결합함으로써, 저자들은 $G \cong_q H$일 필요충분조건이 $G$와 $H$가 모든 평면 그래프에 대해 동형 불구별하다는 새로운 증명을 도출한다.

• 차이점: **컴팩트 양자 군(compact quantum groups)**과 인터티너(intertwiner) 이론에 크게 의존했던 기존의 [FOCS'20] 증명과 달리, 이 증명은 순수하게 조합론적이고 대수적이며, NPA 계층과 동형 텐서를 활용한다.

4. 의의 및 주장

본 논문은 NPA 계층에 대한 동형 불구별성 특성화를 제공함으로써, 양자 동형 완화 모델을 동형 불구별 관계라는 더 넓은 이론적 틀 안에 배치한다고 주장한다.

• 이론적 통합: 비가환(non-commutative) NPA 계층과, Roberson와 Seppelt [ICALP'23]가 그래프 클래스 $L_k$를 사용하여 특성화했던 고전적 Lasserre 계층 사이의 간극을 메운다.
• 계산적 이점: 고정된 $k$에 대해 NPA 계층의 정확한 타당성이 확률적 다항 시간 내에 결정 가능하다는 것을 입증하였는데, 이는 SDP 공식화 자체만으로는 즉각적으로 명확하지 않은 결과이다.
• 양자 동형 이론의 단순화: 저자들은 양자 군의 "무거운 도구"를 사용하지 않고 NPA 제약의 조합론적 구조에 의존하여, 양자 동형(평면 그래프를 통한)의 근본적인 특성화를 제공하는 증명을 제시한다.

저자들은 $P_k$가 유계된 트리의 폭을 가진 평면 그래프의 부분 클래스이지만, $P_k$와 고전적 동형 완화를 위해 사용되는 그래프 클래스 $L_k$ 사이의 정확한 구조적 관계는 여전히 미해결 과제로 남아 있다고 언급한다 (문제 6.1). 또한, 양자 동형이 특정 수준의 NPA 계층에 의해 결정되지만 고전적 동형과는 다른 그래프 클래스가 존재하는지에 대한 질문도 던진다 (문제 6.2).