Proof of hiding conjecture in Gaussian boson sampling

기술 요약: 가우시안 보존 샘플링에서의 은닉 추측(Hiding Conjecture) 증명

1. 문제 정의

가우시안 보존 샘플링(Gaussian Boson Sampling, GBS)은 양자 컴퓨팅 우위를 입증하기 위한 유력한 후보입니다. GBS의 고전적 시뮬레이션 난이도에 대한 논거는 행렬의 하프니언(hafnian)을 근사하는 것의 평균 사례 난이도(average-case hardness)에 대한 추측된 난이도와 **은닉 추측(hiding conjecture)**이라는 두 가지 주요 구성 요소에 의존합니다.

은닉 추측은 복소 가우시안 행렬(구체적으로 독립적인 성분을 가진 행렬)이 하르 무작위 유니터리 행렬(Haar-random unitary matrix)의 대칭 곱(symmetric product) 내에 부분 행렬로서 "은닉"될 수 있음을 단언하며, 이 두 분포는 전 변동 거리(total variation distance, TV distance) 측면에서 구별 불가능하다는 것을 의미합니다. 이 속성은 특정하기 어려운 계산 대상인 행렬 $Z$를 GBS 출력 분포에 삽입할 수 있게 해주며, 이를 통해 공격자(또는 고전적 시뮬레이터)가 확률 추정치를 왜곡하기 위해 $Z$의 위치를 식별하는 것을 방지합니다.

표준 (포크, Fock) 보존 샘플링에서는 희소 영역(sparse regimes)에서 은닉 속성이 확립되었으나, 최근의 대규모 GBS 실험과 관련된 영역—모든 $M$개의 입력 모드가 스퀴즈(squeezed)된 경우($K=M$)—에서는 증명되지 않은 상태로 남아 있었습니다. 이 영역에서 관련 부분 행렬은 $M \times M$ 하르 유니터리의 $N \times M$ 직사각형 블록이며, 이는 행 정규화 제약 조건(row normalization constraints)으로 인해 TV 거리에서 가우시안 행렬처럼 보이지 않는 것으로 알려져 있습니다. 열린 문제는 이 비가우시안 부분 행렬의 대칭 곱($U_{N,M}U_{N,M}^T$)이 그럼에도 불구하고 TV 거리에서 복소 대칭 가우시안 행렬로 수렴하는지 여부였습니다.

2. 방법론

저자들은 모든 입력 모드가 스퀴즈된 경우($K=M$)에 대한 엄밀한 증명을 제공합니다. 핵심 방법론은 다음과 같습니다:

• 랜덤 행렬 이론 공식화: 이 문제는 $M \times M$ 순환 직교 앙상블(Circular Orthogonal Ensemble, COE) 랜덤 행렬 $A$의 상좌측 $N \times N$ 부분 행렬($U$가 하르 무작위일 때 $UU^T$로 분포됨)이 $\sqrt{M}$에 의해 스케일링될 때 복소 대칭 가우시안 행렬 $G \sim \mathcal{G}^{\text{sym}}_N$로 수렴함을 보이는 문제로 매핑됩니다.
• KL 발산을 통한 전 변동 거리 측정: 저자들은 직접적인 결합(coupling) 대신, 두 분포 사이의 쿨백-라이블러(Kullback-Leibler, KL) 발산과 관련된 **핀스커 부등식(Pinsker's inequality)**을 사용하여 TV 거리를 제한합니다.
• 밀도 분석:
  • COE 부분 행렬의 확률 밀도 함수(PDF)는 기존 문헌(Hua, 1963; Kieburg et al., 2013)으로부터 유도되며, $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$라는 행렬식 항을 포함합니다.
  • 대상 가우시안 행렬의 PDF는 표준 복소 대칭 가우시안입니다.
• 정규화 상수 처리: 기술적 혁신 중 하나는 COE 밀도의 복잡한 복소 정규화 상수를 명시적으로 계산하는 것을 피하는 것입니다. 대신, 저자들은 스케일링 인자 $\zeta$를 도입하고, 행렬의 특이값(singular values)에 대한 경계값을 사용하여 $M \to \infty$일 때 $\zeta \to 1$임을 증명합니다. 이를 통해 어려운 점근적 확장(asymptotic expansion) 과정을 우회하면서도 수렴 증명의 타당성을 유지할 수 있습니다.
• 모멘트 경계: 증명은 특이값(행렬 $A^\dagger A$의 고유값)의 모멘트를 계산하기 위해 와이팅게이트 계산법(Weingarten calculus)을 활용하며, 큰 고유값의 확률을 제한하기 위해 집중 부등식(concentration inequalities, subgaussian concentration)을 사용하여 로그 밀도 항의 테일러 전개가 유효함을 보장합니다.

3. 주요 기여 및 결과

정리 1.1 / 정리 1.2 (주요 결과):
저자들은 모든 입력 모드가 스퀴즈된($K=M$) GBS에 대한 은닉 추측을 증명합니다. 구체적으로, $N = o(\sqrt{M})$일 때, 스케일링된 COE 부분 행렬 $\sqrt{M}A$와 복소 대칭 가우시안 행렬 $G$ 사이의 전 변동 거리는 $M \to \infty$임에 따라 소멸함을 보입니다:
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
이는 대칭 곱 $U_{N,M}U_{N,M}^T$가 실험적으로 유의미한 영역에서 복소 대칭 가우시안 행렬에 의해 잘 근사됨을 입증합니다.

따름정리 1.1:
저자들은 복소 대칭 가우시안 행렬 $G$(독립적인 성분을 가짐)와 직사각형 가우시안 행렬의 대칭 곱 $GG^T$가 성분별 최대 노름(entrywise maximum norm)에서 유사함(따라서 충분히 작은 $N$에 대해 TV 거리에서도 유사함)을 보여줍니다. 이는 관련 영역에서 $\text{Haf}(G)$를 근사하는 것의 난이도가 $\text{Haf}(GG^T)$를 근사하는 것과 본질적으로 동등함을 의미합니다.

정리 1.3 (곱셈적 추정치):
본 논문은 밀도 함수에 대한 곱셈적 경계 $f(Z) \leq (1 + O(N^3/M))g(Z)$를 제공합니다. 이 결과는 난이도 증명에 사용되는 "인스턴스 생성(instance generating)" 방식에 필수적이며, 특정 가우시안 행렬을 은닉된 부분 행렬로 포함하는 무작위 유니터리를 생성할 수 있게 합니다.

정리 1.5 & 1.6 (희소 영역 확장):
본 논문은 은닉 속성을 희소 영역($NK = o(M)$)으로 확장하여, 이 영역에서 $K < M$일 때 은닉 추측이 성립함을 확인하고, 포크 보존 샘플링에 대한 알려진 경계를 최대 크기 $N = o(\sqrt{M})$까지 개선합니다.

4. 의의 및 주장

본 논문은 최대 스퀴즈 입력 모드($K=M$)를 사용하는 가우시안 보존 샘플링의 은닉 속성에 대한 최초의 엄밀한 증명을 제공한다고 주장합니다.

• 난이도 논거: 은닉 추측을 증명함으로써, 저자들은 최대 스퀴즈 입력 모드를 가진 GBS의 고전적 시뮬레이션 난이도에 대한 논거를 기존 포크 보존 샘플링(Aaronson and Arkhipov, 2013)의 난이도 논거와 "비교 가능한 수준"으로 올려놓았습니다.
• 실험적 관련성: 이 결과는 완전한 스퀴즈 입력 상태를 사용하는 최근의 대규모 GBS 실험(예: Madsen et al., Nature 2022)에 대한 계산 이론적 정당성을 직접적으로 뒷받침합니다.
• 이론적 미묘함: 저자들은 증명이 부분 행렬 자체가 아니라 부분 행렬의 대칭 곱의 분포에 의존한다는 점을 강조합니다. 부분 행렬 $U_{N,M}$은 TV 거리에서 가우시안과는 거리가 멀지만, 그 대칭 곱 $U_{N,M}U_{N,M}^T$는 가우시안 행렬로 수렴합니다. 이 구분은 매우 중요한데, 포크 보존 샘플링의 은닉 속성으로부터 GBS의 난이도를 도출하려 했던 이전의 시도들이 이 밀집된(dense) 영역에서는 실패했기 때문입니다.

논문은 $K=M$ 케이스는 해결되었으나, 중간 단계의 케이스($K=cM, c<1$)에 대한 은닉 추측은 본 연구에서는 미해결 상태로 남아 있다고 언급하며 마무리합니다(단, 저자들은 후속 연구[47]에서 해결되었음을 명시함). 이 작업은 충돌 없는 영역(collision-free regime, $N \ll M$)을 엄격히 준수하며, 하프니언 근사의 평균 사례 난이도에 관한 표준적인 계산 이론적 추측에 의존합니다.