Classical Algorithms for Function Computation in Gaussian Boson Sampling

기술 요약: 가우시안 보존 샘플링에서의 함수 계산을 위한 고전적 알고리즘

문제 정의
가우시안 보존 샘플링(GBS)은 압축 진공 입력을 통과하는 수동 선형 광학 네트워크를 통해 생성된 광자 수 패턴의 전체 출력 분포로부터 샘플링하는 문제의 어려움을 통해, 양자 컴퓨팅 우위를 입증할 수 있는 주요 후보로 부상했습니다. 샘플링 문제 자체는 고전적으로 어렵다고 여겨지지만, GBS의 많은 제안된 응용 분야들은 전체 분포를 재현하는 것을 목표로 하기보다는 측정 결과의 특정 함수(예: 진동 구조 스펙트럼, 그래프 커널 또는 클릭 가중치)를 계산하는 것을 목표로 합니다. 이러한 작업은 특정 관측량의 기댓값을 추정하기 위해 모드별 광자 수 분해(PNR) 결과에 대한 고전적 후처리 과정을 포함합니다.

본 연구에서 다루는 핵심 질문은 GBS 분포의 고전적 샘플링 어려움이 이러한 함수 계산 작업에 대한 양자 우위를 반드시 의미하는가 하는 점입니다. 즉, 어떤 함수 $f(s)$에 대하여, 샘플링 자체가 고전적으로 어려울지라도 해당 함수의 기댓값을 효율적으로 추정하는 고전적 알고리즘이 존재하는가 하는 것입니다. 이전 연구들은 특정 사례(예: 영온도 조화수 인스턴스 또는 적응형 측정이 포함된 회로)에 대해 고전적 시뮬레이션 가능성을 입증한 바 있으나, 하르 무작위(Haar-random) 네트워크에 대한 임의의 다항 시간 계산 가능한 함수에 대한 일반적인 결과는 부족한 상태였습니다.

방법론
저자들은 문제를 고정된 광자 수 섹터로 분해하고, 이를 다시 상관 차수(correlation orders)로 세분화함으로써 GBS 함수 계산을 분석하기 위한 운영 프레임워크를 개발합니다. 핵심 기술적 접근 방식은 다음과 같습니다:

1. 연산자 공간 분해: $n$-광자 섹터 상의 연산자 공간 $\mathcal{B}(\mathcal{H}_{m,n})$을 유니터리 군 $U(m)$의 작용 하에서 기약 부분 모듈 $V_{n,k}$로 분해합니다. 인덱스 $k$는 "상관 차수"를 나타내며, 이는 $k$개의 생성-소멸 쌍을 포함하는 정규 순서 단항식(normally ordered monomials)에 대응합니다.
2. 하인 다항식(Hahn Polynomial) 대응: 포크 기저(Fock basis)에서 대각 성분을 갖는 관측량(결과 함수에 대응함)의 경우, 연산자 공간 분해의 성분들은 다변량 하인 다항식 부 subspace로의 직교 투영으로 직접 매핑됩니다. 이를 통해 기댓값 $\mu_f(U)$를 서로 다른 상관 차수들로부터의 기여분의 합으로 표현할 수 있습니다.
3. 하르 평균 분석: 선형 광학 네트워크 $U$가 하르 측도(Haar measure)로부터 추출된다고 가정함으로써, 저자들은 슈어 직교성(Schur orthogonality)을 활용하여 서로 다른 상관 차수들로부터의 기여분이 서로 상관관계가 없음을 보여줍니다. 결정적으로, 유한한 압축 강도(압축 파라미터 $r_j$가 모드 수 $m$과 독립적으로 유계인 경우)를 가진 입력의 경우, 고차 상관 성분의 가중치가 $m$에 따라 다항식적으로 감소함을 증명합니다.
4. 절단 및 추정: 기댓값은 합을 상수 상관 차수 $K$까지 절단함으로써 근사될 수 있습니다. 이 절단에 의해 발생하는 오차는 높은 확률로 $m$에 대한 역다항식(inverse-polynomial)으로 나타남을 보여줍니다. 저자들은 다음과 같은 고전적 알고리즘을 구축합니다:
   • 광자 쌍의 수 $N$과 상관 차수 $k$를 절단합니다.
   • 남은 섹터들에 대한 축약 밀도 행렬(reduced density matrices)을 계산합니다.
   • 낮은 차수의 축약 상태와 작은 행렬들의 퍼머넌트(permanent)로부터 대각 가중치를 재구성할 수 있다는 점을 활용하여, 광자 수 패턴의 균등 측도에 대한 몬테카를로 샘플링을 사용하여 절단된 평균을 추정합니다.

주요 기여 및 결과
본 논문은 다음의 주요 결과를 확립합니다:

• 정리 1 (주요 결과): $m$개의 모드를 가진 GBS 모델에 대하여, 유한한 압축 강도를 가지고, 알려진 평균 및 분산에 대한 다항 시간 내 계산 가능한 다항식 경계(이는 $U$와 독립적이어야 함)가 제공되는 임의의 결과 함수 $f$에 대하여, 무작위 고전 다항 시간 알고리즘이 존재합니다. 이 알고리즘은 하이-랜덤 네트워크 $U$의 선택에 대해 높은 확률($1 - m^{-\kappa}$)로 기댓값 $\mu_f(U)$를 역다항식 덧셈 오차($m^{-c}$) 내에서 추정합니다. 이러한 명시적 경계가 없는 일반적인 함수들을 위해, 저자들은 유한한 크기의 유계 특성 함수 패밀리를 평가함으로써 평균을 추정하는 위상 재구성(phase-reconstruction) 확장 방식을 제공합니다.
• 자원 경계 식별: 본 연구는 GBS의 고전적 어려움에 필요한 정확한 자원을 구분합니다. 논문의 표 I에 요약된 바와 같이, 고전적 어려움에 대한 증거는 다음 세 가지 요소의 결합에 의존합니다:
  1. 압축된 입력(Squeezed inputs).
  2. 모드 분해 광자 검출(PNR 또는 임계값 검출).
  3. 전체 출력 분포로부터의 샘플링.
     본 논문은 목표가 단순히 함수 계산(평균 추정)이지 전체 분포 샘플링이 아니라면, 압축이 유한하고 함수가 요구되는 경계를 만족하는 한, 해당 작업이 고전적으로 효율적임을 입증합니다.
• 알고리즘 구축: 저자들은 절단된 평균을 추정하는 구체적인 고전 알고리즘을 제공합니다. 이 알고리즘은 전체 하프니안(Hafnian)을 계산하는 지수적 비용을 피하기 위해, 축약 밀도 연산자와 낮은 차수의 퍼머넌트를 결합하여 패턴 공간에 대한 몬테카를로 샘플링을 수행합니다.

의의 및 주장
본 논문은 GBS의 고전적 어려움의 근거를 명확히 함으로써 선형 광학 양자 시스템을 분석하기 위한 새로운 이론적 도구를 제공한다고 주장합니다. 구체적으로, GBS의 고전적 어려움은 전체 확률 분포를 재현하는 것의 어려움에 연결되어 있으며, 특정 통계적 평균을 계산하는 것과는 별개의 문제임을 논합니다.

저자들은 본 연구가 실제 양자 우위가 있는 작업과 고전적으로 효율적으로 시뮬레이션 가능한 작업을 구분하는 경계를 명확히 하는 데 도움이 된다고 강조합니다. 이들의 결과는 GBS의 샘플링 어려움을 부정하는 것이 아니라, 양자 우위가 어디에 있는지에 대한 이해를 정교화하는 것입니다. 즉, 양자 우위는 함수 계산 작업(분자 분광학이나 그래프 문제와 같은 현재 제안된 GBS 응용 분야들)이 아니라, 전체 분포 샘플링 작업에 있다는 점을 명시합니다. 단, 이는 해당 응용 분야들이 본 정리의 범위를 벗어나는 특징(예: $U$에 의존하는 후처리, 최악의 경우 네트워크, 또는 모멘트에 대한 다항식 경계가 없는 함수)을 사용하지 않는다는 전제하에 그러합니다.

본 연구는 향에 대한 진정한 양자 우위를 추구하는 미래의 GBS 응용 분야들이 반드시 전체 분포 샘플링 문제를 타겟으로 하거나, 본 정리의 가정을 위반하는 함수 계산 작업(예: 무한한 압축 사용, 하르-무작위가 아닌 네트워크, 또는 모멘트에 대한 알려진 다항식 경계가 없는 함수 사용)을 식별해야 함을 시사합니다. 저자들은 본 논문의 초점이 엄격하게 GBS 함수 계산 모델에 국한되어 있음을 밝히며, 다른 입력(예: 단일 광자 입력)을 사용하는 다른 샘플링 알고리즘에 대한 결과는 별도의 연구에서 다루고 있음을 언급합니다.