Simulating Gaussian boson sampling on graphs in polynomial time

기술 요약: 그래프 상에서의 가우시안 보존 샘플링(Gaussian Boson Sampling)에 대한 다항 시간 내 시뮬레이션

문제 정의
본 논문은 보존 샘플링(Boson Sampling, BS) 및 가우시안 보존 샘플링(Gaussian Boson Sampling, GBS)과 관련된 분포의 계산 복잡도를 다룬다. Aaronson과 Arkipov [1]는 BS를 양자 우위를 입증하기 위한 모델로 제안하였으며, 영구식(permanent)의 비집중성(anti-concentration) 및 가우시안 영구식에 관한 가설을 전제로 할 때, 정확한 출력 분포로부터 샘플링하는 클래식 알고리즘은 계산적으로 불가능하다고(다항 계층의 붕괴를 초래하며) 믿어진다. 이와 유사하게, 스퀴즈드 상태(squeezed states)를 사용하여 광자 소스 비용을 피하기 위해 제안된 변형인 GBS는 완전 매칭(perfect matchings) 계산, 최대 밀도 부분 그래프(densest subgraphs) 찾기, 그래프 동형성(graph isomorphism) 등 어려운 그래프 문제들을 해결하는 데 사용된다.

본 논문이 다루는 핵심적인 미해결 문제는 그래프 상의 GBS 분포, 즉 $\mu_{GBS,G} \propto c^{2|S|} \text{PM}(S)^2$ (여기서 $\text{PM}(S)$는 유도된 부분 그래프 $G[S]$의 완전 매칭 수)로부터 샘플링하는 효율적인 클래식 알고리즘이 존재하는가 하는 점이다. 이전 연구인 Zhang 등 [12]은 매우 조밀한 그래프에 대해서만 빠른 알고리즘을 제공하였고, Oh 등 [13]은 $\text{PM}(S)^2$ 대신 $\text{PM}(S)$에 비례하는 약간 다른 분포에 대한 클래식 알고리즘을 제안하였으나, 비음수(non-negative) GBS 케이스는 여전히 열려 있는 상태였다.

방법론
저자들은 대상 샘플링 분포를 그래프의 가중치 완전 매칭 문제로 매핑하는 환원 전략을 사용한다. 이들은 특정 조건 하에서 완전 매칭의 근사 샘플링을 허용하는 Jerrum과 Sinclair [14], 그리고 Jerrum, Sinclair, Vigoda [17]가 개발한 마르코프 체인 몬테카를로(MCMC) 알고리즘을 활용한다.

1. 비음수 보존 샘플링 (정리 1.3):
   저자들은 주어진 비음수 실수 행렬 $A$로부터 이분 그래프(bipartite graph) $G$를 구성한다. 이 구성은 정점 집합 $L_1, L_2$와 $R_1, R_2$를 생성하고, $A$의 성분들에 의해 가중치가 부여된 에지를 포함한다. 이 구성된 그래프에서 특정 에지 가중치를 가진 완전 매칭을 샘플링함으로써, $R_1$에 있는 매칭된 정점들의 주변 분포는 보존 샘플링 분포 $\mu_{BS}$를 근사하게 된다. 근사 오차는 $k$ (정점의 복제 수)라는 파라미터에 의해 제어되며, $k$는 충분히 큰 값($O(n^2/\varepsilon)$)으로 선택된다.

2. 그래프 상의 가우시안 보존 샘플링 (정리 1.1):
   저자들은 GBS 분포 $\mu_{GBS,G}(S) \propto c^{2|S|} \text{PM}(S)^2$를 정의한다. 이를 샘플링하기 위해, 입력 그래프 $G$와 에지 $K_2$의 카테시안 곱(Cartesian product)인 $G \square K_2$를 구성한다.

• 구성: $G \square K_2$는 두 개의 $G$ 복사본($G$와 $G'$)과 서로 대응하는 정점들을 연결하는 에지들로 구성된다.
• 가중치 부여: $G$와 $G'$ 내부의 에지들(집합 $E$와 $E'$)에는 가중치 $c^2$가 할당되고, 복사본들을 연결하는 에지들(집합 $E_0$)에는 가중치 $1$이 할당된다.
• 환원: $G \square K_2$에서의 완전 매칭은 원 그래프의 부분 집합 $S \subseteq V$ (자신의 복사본 내에서 매칭된 정점들)를 유도한다. 특정 집합 $S$를 유도할 확률은 $c^{2|S|} \text{Haf}(A_S)^2$에 비례함이 나타나며, 이는 유도된 부분 그래프에 대해 $c^{2|S|} \text{PM}(S)^2$와 같다.
• 효율성 조건: Jerrum-Sinclair 알고리즘은 근완전 매칭(near-perfect matchings) 대 완전 매칭의 비율이 다항식으로 유계되어야 한다. 이를 보장하기 위해 저자들은 새로운 가중치 함수 $\lambda'$ ( $4n^2$에 의해 스케일링됨)를 정의하고, 이 새로운 가중치 하에서 근완전 매칭의 총 가중치($Z'_{n-1}$)와 완전 매칭의 총 가중치($Z'_n$)의 비율이 상수(구체적으로 $Z'_{n-1} \le Z'_n/2$)로 유계됨을 증명한다. 이는 원래의 가중치에 대한 $Z_{n-1} < 2n^2 Z_n$이라는 관계를 확립한 Lemma 4.2와 매칭 다항식의 로그-오목성(log-concavity, Heilmann 및 Lieb [20]) 및 AM-GM 부등식을 통해 도출된다. 이는 마르코프 체인이 다항 시간 내에 혼합(mix)됨을 보장한다.

주요 기여 및 결과
본 논문은 두 가지 주요 정리를 통해 다항 시간 클래식 알고리즘을 제시한다:

• 정리 1.1 (그래프 상의 GBS): 그래프 $G$와 실수 파라미터 $c > 0$가 주어졌을 때, 총 변동 거리(total variation distance) 관점에서 $\mu_{GBS,G}$에 $\varepsilon$-가까운 분포로부터 샘플링하는 알고리즘이 존재한다. 실행 시간은 $O(\bar{c}mn^4 \log^2(nc/\varepsilon))$이며, 여기서 $m=|E|$, $n=|V|$, $\bar{c} = \max\{1, c\}$이다. 이 결과는 조밀한 그래프뿐만 아니라 모든 그래프에 대해 성립한다.
• 정리 1.3 (비음수 보존 샘플링): 비음수 실수 행렬 $A$ (여기서 $A$는 반드시 절단된 유니터리 행렬일 필요는 없음)가 주어졌을 때, 보존 샘플링 분포 $\mu_{BS}$에 $\varepsilon$-가까운 분포로부터 샘플링하는 알고리즘이 $O(m^7 n^{14} \varepsilon^{-7} \log^4(mn/\varepsilon))$ 시간에 존재한다.

의의 및 주장
저자들은 자신들의 결과가 $\mu_{GBS,G}$ 분포로부터의 샘플링에 기반한 응용 분야에서 양자 알고리즘이 지수적 가속(exponential speedup)을 제공하지 못함을 보여준다고 주장한다. 많은 제안된 GBS 응용 사례들(예: 그래프 동형성, 완전 매칭 계산)이 이 특정 분포로부터의 샘플링에 의존하므로, 다항 시간 내의 클래식 샘플러의 존재는 이러한 특정 작업들이 표준 GBS 모델 하에서 양자 우위를 나타내지 않음을 의미한다.

저자들은 Jerrum-Sinclair-Vigoda 알고리즘이 일반적인 보존 샘플링(입력 행렬이 복소수 성분을 가진 절단된 유니터리 행 matrix인 경우)에 직접 적용되지는 않는다는 점을 언급한다. 왜냐하면 그들의 구성은 샘플링 문제를 복소 가중치 행렬의 영구식(permanent) 근사 문제로 환원시키기 때문이다. 영구식 근사는 일반적으로 NP-hard이므로, 일반적인 보존 샘플링의 클래식 시뮬레이션은 여전히 어렵다. 그러나 비음수 행렬 및 그래프 기반 GBS의 특정 케이스에 대해서는, 저자들은 효율적인 클래식 시뮬레이션이 가능하다는 것을 입증하였다.

본 연구는 카테시안 곱 구성을 사용하여 (Zhang 등의 [12]와 같은) 이전 접근 방식보다 더 넓은 범위(조밀한 그래프뿐만 아니라 모든 그래프)에 적용 가능하며, 더 단순하고 빠른 알고리즘을 활용한다는 점에서 차별화된다.