Efficient classical algorithm for estimating linear statistics of Boson Sampling

문제 정의
보손 샘플링(Boson Sampling)은 양자 컴퓨팅 우위를 입증할 수 있는 유력한 후보이지만, 결과 공간의 지수적 크기와 분포의 반집중(anti-concentration) 특성으로 인해 실질적인 활용에 제약이 있습니다. 보손 샘플링을 물리적 관측량을 추정하거나 계산 작업을 수행하는 데 활용하려면, 출력 분포를 "거칠게 입자화(coarse graining)"해야 합니다. 개별 출력 확률을 정확하게 계산하는 것은 #P-hard 문제이지만, 많은 제안된 응용 분야는 가법 오차(additive error) 내에서 특정 물리적 관측량이나 그룹화된 확률만을 요구합니다. 핵심적인 미해결 과제는 어떤 유형의 거친 입자화 분포가 효율적으로 고전적으로 시뮬레이션 가능하며, 어떤 것이 양자적 난해성을 유지하느냐는 것입니다. 본 논문은 선형 통계량(출력 광자 점유수의 선형 함수로부터 유도된 확률 분포)의 복잡도를 다루며, 이것이 고전적으로 효율적으로 근사될 수 있는지, 즉 기존의 양자 영감 알고리즘들을 통합하거나 특정 암호학적 제안을 약화시킬 수 있는지를 조사합니다.

방법론
저자들은 그룹 확률의 푸리에 분해(Fourier decomposition)를 기반으로 한 효율적인 고전 알고리즘을 개발했습니다. 핵심 방법론은 다음 단계들을 포함합니다:

1. 선형 통계량의 정의: 본 논문은 선형 통계량을 $k = \omega \cdot s$ (여기서 $s$는 출력 광자 점유 벡터, $\omega$는 비음수 정수 가중치 벡터)의 확률 분포로 정의합니다. 결과값들은 이러한 값들의 연속적인 구간에 따라 빈(bin) $B_j$로 그룹화됩니다.
2. 특성 함수와의 연결: 저자들은 선형 통계량의 특성 함수 $\chi_\omega(\theta) = \mathbb{E}[e^{i\theta f_\omega(s)}]$를 선형 광학 회로의 전이 진폭(transition amplitude)과 연관시킵니다. 구체적으로, $\chi_\omega(\theta)$는 유니터리 $V_{\Omega, \theta} = U^\dagger e^{i\theta \Omega} U$와 관련된 선형 간섭계 연산자 $\langle t | \hat{V}_{\Omega, \theta} | t \rangle$와 같음을 보여줍니다.
3. 푸리에 추정: 이산 푸리에 변환을 사용하여, 누적 분포 함수(CDF) $S(x) = \Pr[f_\omega(s) \leq x]$를 특성 함수의 이산 집합에 대한 기댓값으로 표현합니다.
4. 중요도 샘플링(Importance Sampling): CDF를 효율적으로 추정하기 위해, 저자들은 $1/k$에 비례하는 중요도 샘플링 분포 $q(k)$를 사용합니다. 이는 추정치의 범위가 다항식 수준($O(\log N)$)으로 유지되도록 하여, 역다항식 가법 오차 내에서 CDF를 효율적으로 고전적 추정할 수 있게 합니다.
5. 일반 입력으로의 확장: 이 프레임워크는 특성 함수를 효율적으로 계산하거나 근사할 수 있는 능력에 의존합니다. 저자들은 행렬 퍼머넌트(matrix permanent)나 헤피언(Hafnian)에 기반한 기존 알고리즘을 활용하여, 폭스 상태(Fock states), 가우시안 상태(변위된 스퀴즈드 진공), 그리고 부분적으로 구별 가능한 광자를 포함한 다양한 입력 상태에 대해 이것이 가능하다는 것을 입증합니다.

주요 기여 및 결과

• 효율적인 고전 알고리즘: 본 논문은 $n$개의 광자와 $m$개의 모드를 가진 보손 샘플링에 대해 $m$, $\epsilon^{-1}$, 그리고 $\log(1/\delta)$에 대한 기대 다항 시간 내에 선형 통계량의 누적 분포를 추정하는 무작위 고전 알고리즘을 제시합니다. 이는 폭스 상태 및 스퀴즈드 상태를 포함한 광범위한 클래스의 입력 상태에 대해 유효합니다.
• 기존 결과의 통합: 이 알고리즘은 분자 진동 스펙트럼의 효율적인 양자 영감 고전 시뮬레이션과 검출기 빈닝(detector binning)에 기반한 거친 입자화 분포의 효율적 근사를 단일 선형 통계량 프레임워크 아래 통합합니다.
• 암호학적 함의: 저자들은 보손 샘플링 기반 일방향 함수의 핵심 구성 요소인 "최빈 빈(most probable bin)" 문제에 이 알고즘을 적용합니다. 그들은 이 특정 문제가 실제 실험을 실행하는 것과 동일한 효율성으로 고전적으로 평가될 수 있음을 보여줌으로써, 해당 암호학적 제안이 고전 시뮬레이션 대비 양자 우위를 제공하지 못함을 입증합니다.
• 노이즈에 대한 견고성: 이 프레임워크는 특성 함수를 수정함으로써 광자 손실 및 부분적 구별 가능성과 같은 실험적 결함을 자연스럽게 포함하며, 이 과정에서 시뮬레이션의 계산 복잡도는 증가하지 않습니다.
• 한계 및 향란한 질문: 본 논문은 자신들의 기법이 비선형 통계량이나 순열 또는 비선형 후처리(예: 충돌 없는 이벤트를 다르게 취급하는 경우)를 포함하는 빈닝 전략에는 적용되지 않음을 명시합니다. 저자들은 비선형 통계량(특히 이차 함수)의 시뮬레이션을 단일 층의 광자-광자 상호작용(Kerr 상호작용)을 가진 선형 광학 회로에서의 전이 진폭 계산 문제와 연결합니다.

의의
본 논문은 보손 샘플링 응용 분야의 고전적 시뮬레이션 가능성에 대한 명확한 경계를 설정합니다. 출력의 선형 함수로 정의되는 광범위한 거친 입자화 문제들이 고전적으로 효율적으로 근사될 수 있으므로 양자 우위를 제공하지 못한다는 것을 입증합니다. 이 결과는 보손 샘플링에 기반한 특정 암호학적 제안의 타당성에 도전하는 동시에, 분자 분광학 및 장치 검증을 위한 양자 영감 알고리즘의 효율성을 검증합니다. 이 연구는 비선형 통계량에 대한 고전적 시뮬레이션 가능성 문제를 열어두며, 이러한 문제의 난해성이 단일 층 비선형 광학 상호작용의 시뮬레이션 복잡도와 본질적으로 연결되어 있을 수 있음을 시사합니다. 저자들은 특정 파라미터에 대해 자신들의 방법이 이상적인 실험보다 더 많은 수의 샘플을 필요로 할 수 있지만, 유한한 크기의 실험에 대한 고전적 실행 시간은 현재의 노이즈가 있는 양자 하드웨어로부터 충분한 샘플을 얻는 데 걸리는 시간보다 현저히 짧을 수 있음을 강조합니다.