Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

기술 요약: 보슨 샘플링에서의 무작위 가우시안 행렬에 대한 약한 영구적 반집중성(Weak Permanent Anti-Concentration)

문제 정의
양자 컴퓨팅 우위의 입증을 위한 주요 후보인 보슨 샘플링(Boson Sampling)의 고전적 난해성은 아직 증명되지 않은 두 가지 추측, 즉 가우시안 퍼머넌트(Gaussian permanent)의 평균 사례 난해성과 영구적 반집중성 추측(Permanent Anti-Concentration Conjecture, PACC)에 의존한다. PACC는 무작위 복소 가우시안 행렬의 퍼머넌트가 높은 확률로 "초지수적으로(super-exponentially)" 작아지지 않을 것임을, 구체적으로는 $| \text{Per}(M) |$이 그 표준 편차($\sqrt{n!}$)의 역다항식 분수보다 작을 가능성이 낮다는 것을 단언한다. 이산 무작위 행렬(예: 베르누이 행렬)에 대해서는 Tao와 Vu에 의해 전형적인 크기가 확립되었으나, 선형 광학 네트워크의 전이 진폭을 결정하는 복소 가우시안의 경우—이는 수학적으로 미해결 과제로 남아 있었다. 가우시안 행렬에 대한 반집중성 증명이 없다면, 보슨 샘플링의 고전적 불가능성에 대한 이론적 토대는 불완전한 상태로 남게 된다.

방법론
저자들은 Tao와 Vu가 베르누이 행렬을 위해 개발한 "행 노출(row-exposure)" 프레임워크를 무작위 복소 가우시안 행렬의 설정으로 확장한다. 이 접근법은 $n \times n$ 가우시안 행렬 $M$의 행들을 순차적으로 드러내며 부분 행렬(minors)의 퍼머넌트 성장을 추적하는 방식을 포함한다.

이산적 증명을 연속적인 가우시안 영역으로 적응시키기 위해, 저자들은 몇 가지 핵심적인 확률적 도구들을 교체한다:

1. 반집중 경계(Anti-Concentration Bound): Littlewood-Offord-Erdős 부등식이 복소 가우시안 선형 결합에 특화된 특정 반집중 경계(Lemma 3)로 대체된다.
2. 성장 논거(Growth Argument): 소행렬(minor)이 성장할 확률에 대한 조합론적 하한선이 복소 가우시안 분포의 회전 대칭성을 활용한 해석적 논거(Lemma 7)로 대체된다.
3. 집중 부등식(Concentration Inequality): 유계 증가(bounded increments)를 요구하는 Azuma-Hoeffding 부등식이 가우시안 변수의 비유계 지지(unbounded support)를 다루기 위해 McDiarmid 부등식(Lemma 5)으로 대체된다.

증명은 세 단계의 귀납적 과정을 거친다:

• 워밍업(Warm-up): 크기가 $k_0 \approx \epsilon n$인 적어도 하나의 소행렬의 퍼머넌트 절대값이 1 이상임을 확립한다.
• 성장 단계(Growth Phase): 행렬의 크기를 $k_0$에서 $k_1 \approx (1-\epsilon)n$까지 반복적으로 증가시킨다. 이 단계에서 저자들은 "개체군 성장(population growth)"(큰 소행렬의 수를 늘리는 것)과 "크기 성장"(퍼머넌트 값의 하한을 높이는 것) 사이의 트레이드오프를 활용하며, 이는 포텐셜 함수(potential function)에 의해 제어되는 슈퍼마팅게일(supermartingale)로 나타난다.
• 엔드게임(Endgame): $k_1$에서 $n$까지 결과를 확장한다. 마지막 단계에서는 소행렬 간의 높은 상관관계로 인해, 서로 소인 부분 행렬의 여집합(disjoint complements of submatrices)에 대한 별도의 귀납법이 사용된다. 이 단계에서는 $n^{\log n}$의 곱셈적 손실이 발생하며, 이는 점근적 표기법 내로 흡수된다.

주요 기여 및 결과
본 논문은 약한 영구적 반집중 정리(Theorem 1)를 확립한다. 저자들은 $M \sim G_{n \times n}$인 무작위 가우시안 행렬 $M$에 대하여, 충분히 큰 $n$과 임의의 $\alpha > 0$에 대해 다음을 만족하는 상수 $c > 0$가 존재함을 증명한다:
$$\Pr \left( | \text{Per}(M) | < \frac{\sqrt{n!}}{n^{\alpha n}} \right) = O\left(\frac{1}{n^c}\right)$$
이 결과는 퍼머넌트가 초지수적으로 작아질(구체적으로 표준 편차의 $1/n^{\alpha n}$보다 작아질) 확률이 무시할 수 있는 수준임을 의미한다.

직접적인 따름정리로, 저자들은 가우시안 퍼머넌트의 전형적인 크기(Corollary 1)를 확립한다:
$$| \text{Per}(M) | = n^{(1/2 + o(1))n}$$
이는 거의 확실하게(asymptotically almost surely) 성립한다. 이는 베르누이 행렬에서 이전에 알려진 점근적 스케일링과 일치하지만, 복소 가우시안 분포에 대한 최초의 엄밀한 결과이다.

의의 및 시사점
저자들은 자신들의 결과가 복소 가우시안에 대한 퍼머넌트의 전형적인 크기를 입증한 첫 번째 엄밀한 증명이라고 주장한다. 복소 가우시안 분포는 Haar-무작위 유니터리 행렬의 부분 행렬이 i.i.d. 복소 가우시안으로 근사되는 보슨 샘플링에서 물리적으로 유의미하다.

계산 복잡도와 관련하여, 저자들은 자신들의 약한 반집중 경계가 Aaronson과 Arkhipov의 프레임워크와 결합될 때 조건부 난해도 결과를 함의함을 보여준다. 구체적으로, 만약 '가우시안의 퍼머넌트 추측(Permanent-of-Gaussians Conjecture)'이 성립한다고 가정할 때, 초지수적으로 작은 총 변동 거리(specifically $O(1/n^{2\alpha n})$) 내에서 보슨 샘플링을 고전적으로 시뮬레이션하는 것은 다항식 계층(polynomial hierarchy)의 붕괴를 초래할 것이다.

그러나 본 논문은 이러한 결론의 강도에 대해 겸허한 태도를 취한다. 저자들은 자신들의 경계가 완전한 PACC에 비해 "약하다"는 점을 명시적으로 언급한다. 완전한 추측은 확률이 역다항식 분수($1/\text{poly}(n)$)인 경우를 요구하는 반면, 본 연구는 오직 초지수적 분수($1/n^{\alpha n}$)에 대해서만 이를 증명했기 때문이다. 결과적으로, 이 결과는 보슨 샘플링에 대한 이론적 근거를 강화하기는 하지만, 실험적 검증에 필요한 물리적 정확도 임계치(역다항식 오차)에서 근사 보슨 샘플링의 고전적 난해성을 확립하기에는 아직 불충분하다. 이들의 경계에 있는 초지수적 분모와 완전한 PACC가 요구하는 다항식 분모 사이의 간극은 여전히 해결되지 않은 과제로 남아 있다.