Exact sampling beyond Fock inputs and linear optics: photon-number superpositions, photonic matrix-product states, adaptive and non-linear circuits

기술 요약: 포크(Fock) 입력 및 선형 광학을 넘어선 정밀 샘플링

문제 정의
광자 시스템에서의 양자 우위 주장은 장치가 샘플링하는 것과 고전 컴퓨터가 정확하게 샘플링할 수 있는 것 사이의 계산적 격차에 의존한다. $n$개의 단일 광자가 $m$개의 모드 선형 간섭계에 있는 표준 보존 샘플링(Boson Sampling)은 출력 확률이 행렬의 퍼머넌트(permanent)에 해당하며, 이는 #P-어려움(hard) 문제이기 때문에 고전적으로 어렵다. 그러나 실제 세계의 광자 장치는 이러한 이상적인 모델에서 벗어난다. 소스(source)는 진공과 단일 광자의 중첩 상태를 방출하거나(중첩된 소스), 얽힌 시퀀스(광자 행렬 곱 상태, Photonic Matrix-Product States)를 방출할 수 있다. 또한, 회로는 중간 회로 측정과 피드포워드(적응형 광학, Adaptive Optics) 또는 비선형 요소(비선형 사이트)를 포함할 수 있다. 기존의 정밀 고전 샘플러, 예를 들어 단일 광자에 대한 Clifford and Clifford 알고리즘은 이러한 일반화된 시나리오에 직접 적용되지 않는다. 본 논문은 이러한 비표준 입력 및 회로 구성을 위한 정밀 샘플러의 필요성을 다룬다.

방법론: 세트-체인 렌마(Set-Chain Lemma)
핵심적인 방법론적 기여는 Clifford and Clifford가 사용한 "무작위 순서(random-order)" 샘플링 기법의 일반화이다. 저자들은 세트-체인 렌마(Lemma 1)를 도입하며, 이는 "체인 일관적 세트 가중치(chain-consistent set weights)"에 기반한 정밀 샘플링 기준을 제공한다.

• 메커니즘: 출력 모드를 고정된 입력 순서에 따라 순차적으로 샘플링하는 대신, 알고리즘은 입력 슬롯(소스 또는 방출)의 균등 무작위 순서를 추출한다. 그 후 출력 행을 하나씩 샘플링한다.
• 조건: 샘플러가 정밀하기 위해서는 부분 출력 시퀀스 $z$와 활성 입력 슬롯 세트 $T$에 결합된 가중치 $f_j(z; T)$가 특정 한계 항등식(Condition C2)을 만족해야 한다. 이 항등식은 다음 가능한 출력 행에 대해 합산하는 과정이 이전 단계의 올바른 가중치를 생성하도록 보장하며, 결과적으로 퍼머넌트(또는 그 일반화된 형태)의 라플라스 전개를 더 작은 세트에 대한 합으로 변환한다.
• 사후 추론: 이 구성의 핵심 특징은 명시적인 모든 부분 집합의 열거 없이도 "숨겨진" 입력 세트(예: 어떤 소스가 실제로 광자를 방출했는지 또는 어떤 방출이 트레이스 아웃되었는지)에 대한 사후 분포를 동시에 제공한다는 점이다.

주요 기여: 네 가지 정밀 샘플러
저자들은 세트-체인 렌마를 바탕으로 표준 모델에서 벗어난 네 가지 구체적인 샘플러를 구축한다.

1. 중첩된 소스 (진공 + 단일 광자):

   • 모델: 소스는 $\cos \alpha |0\rangle + \sin \alpha |1\rangle$를 방출한다. 총 광자 수 $k$는 이항 분포를 따른다.
   • 방법: 샘플러는 "오프셋-스타트(offset-start)" 순서를 사용한다. 빈 입력 세트에서 시작하는 대신, 체인은 $n-k$개의 소스(여기서 $n$은 총 소스 수)로부터 시작한다.
   • 가중치: 가중치는 제곱 직사각형 퍼머넌트, $|\text{Per}_{\square} A[z, T]|^2$이다.
   • 비용: 계산 비용은 손실 $\eta = \sin^2 \alpha$ 하에서의 단일 광수 지수에 따라 스케일링된다. 알고리즘은 이 문제를 감소된 유효 광자 수를 가진 단일 광자 샘플링 문제로 취급한다.

2. 광자 행렬 곱 상태 (Photonic Matrix-Product States, MPS):

   • 모델: 내부 메모리(차원 $\chi$)를 가진 양자 방출기가 $n$개의 광자를 순차적으로 방출하여 얽힌 MPS(예: 선형 클러스터 상태)를 생성한다.
   • 방법: 저자들은 "갭-바이-갭 크라머스 수축(gap-by-gap Kraus contraction)"을 도입한다. 무작위 순서가 유지되는 방출 사이에 트레이스 아웃된 방출의 간극을 만들기 때문에, 유지된 광자들의 혼합 상태는 제곱 진폭의 합으로 분해된다.

• 가중치: 가중치는 $R_j$개의 제곱 진폭의 합이며, 각 진폭은 행렬 값 글린 합(matrix-valued Glynn sums)을 사용하여 평가된다.
• 비용: 비용은 항 개수 $R_j$에 의해 결정된다. 선형 클러스터 상태에 대한 경험적 측정에 따르면, $R_j$는 작게 유지되며(중간 단계에서 약 $n/2.5$로 정점을 찍고 마지막 단계에서는 1~2로 떨어짐), 테스트된 인스턴스($n \le 20$)에 대해 관리 가능한 오버헤드를 유지한다.

3. 적응형 선형 광학 (Adaptive Linear Optics):

   • 모델: 중간 회로 광자 계측과 피드포워드가 후속 모드에 적용되는 유니터리를 변경한다.
   • 방법: 샘플러는 관찰된 적응형 카운트에 따라 표준 포크(단일 광자) 체인을 조건화한다. 이는 "접두사(prefix)"를 먼저 샘플링한 후 표준 Clifford-Clifford 단계를 계속하는 방식으로 진행된다.
   • 거부(Rejection): 미래의 광자가 이미 측정된 적응형 모드에 도달하지 않아야 한다는 제약 조건은 체인 일관성이 없다. 샘러는 이를 거부 원칙을 통해 강제한다: 만약 체인이 접두사가 고정된 후 적응형 모드에 광자를 배치하면, 해당 체인은 중단되고 다시 그려진다.
   • 비용: 적응형 모드($K$)의 수가 고정되었을 때, 오버헤드는 표준 샘플러의 상수 배(예: $K=3$일 때 약 1.1배) 내에 머문다.

4. 비선형 사이트 (Non-Linear Sites):

   • 모델: 선형 간섭계 사이의 단일 모드 비선형성(예: 커 효과 위상)을 포함한다.
   • 방법: 자연스러운 비선형 회로의 가중치는 서로 다른 선형 브랜치들이 숨겨진 입력 세트를 결합하기 때문에 체인 일관성 조건을 위반한다. 저자들은 선형 브랜치의 혼합에 대해 거부 원칙을 적용한다.
   • 알고리즘: 브랜치 $b$는 $|c_b|$에 비례하는 확률로 선택되며, 표준 포크 샘플이 해당 브랜치에서 추출되고, 코시-슈바르츠 부등식으로부터 유도된 확률에 따라 샘플이 수락된다.
   • 비용: 수락 확률은 정확히 $1/\|c\|_1^2$이다. 짧은 주기를 가진 비선형성(예: $\phi = \pi/2$)의 경우 브랜치 $B$가 작아 상수 오버헤드(약 4배)가 발생한다. 일반적인 응답의 경우 비용은 $n$에 따라 다항식적으로 증가한다.

결과 및 검증

• 검증: 네 가지 샘플러 모두 작은 인스턴스에 대해 강력한 시뮬레이션(SLOS 및 기타 정밀 방법 사용)을 통해 검증되었다. 샘플러의 출력과 오라클 사이의 측정된 총 변동 거리(Total Variation Distance, TVD)는 통계적 노이즈(정밀 추출의 약 1.7 표준 편차) 범위 내에 있었다.
• 성능:
  • 중첩된 소스: 비용은 손실 지수를 따른다. $\sin^2 \alpha = 0.8$일 때, 비용은 동일한 크기의 단일 광자 샘플러보다 약 4배 높다.
  • 광자 MPS: 측정된 열($n \le 20$)에서 오버헤드는 낮다. 왜냐하면 가장 비용이 많이 드는 마지막 단계에서 $R_j$가 작기 때문이다.
  • 적응형 광학: 최대 3개의 적응형 모드를 사용하는 샘플링은 표준 단일 광자 샘플러 대비 10% 이내의 비용을 소모한다.
  • 비선형 사이트: $\phi = \pi/2$인 비선형 사이트는 표준 샘플러의 약 4배 비용이 든다.

의의 및 주장
본 논문은 "무작위 순서" 샘플링 패러다임이 생각보다 더 견고하며, 세트-체인 렌마의 한계 항등식이 성립하는 한 제품 포크 입력(product Fock inputs)을 넘어 얽히거나 중첩된 상태까지 확장될 수 있음을 주장한다.

• 지수율(Exponential Rates): 저자들은 중첩된 소스, 적응형 광학(고정된 $K$에 대해), 그리고 짧은 주기의 비선형성에 대해, 정밀 고전 시뮬레이션의 지수율이 변하지 않거나(또는 유효 손실에 따라 스케일링됨을) 입증했다. 이러한 기능들은 그 자체만으로는 단일 광자 사례와 비교했을 때 고전적 시뮬레이션이 불가능한 영역으로 문제를 밀어넣지 않는다.
• 열린 질문: 저자들은 $n$이 증가함에 따라 광자 MPS의 $R_j$ 증가가 어떻게 될지는 여전히 미지수라고 언급했다. 만약 $R_j$가 지수적으로 증가한다면, 접두사-진폭 샘플러(polynomial overhead를 가진)가 결국 더 우월할 수 있다. 마찬가지로, 일반적인 비선형성에 대한 체인 일관적 가족(chain-consistent family)은 아직 알려지지 않았으며, 거부 방법은 일반적인 응답에 대해 비용이 많이 든다.
• 구현: 샘플러들은 통합된 GPU 코드베이스(photonic-engines)로 구현되었으며, 검증된 도구 세트를 제공하기 위해 Lean 4로 정형화되었다.

요약하자면, 이 연구는 광자 장치의 광범위한 클래스를 정확하게 시뮬레이션하기 위한 통합된 이론적 프레임워크와 실질적인 알고리즘을 제공하며, 표준 보존 샘플링 모델의 확장이 어떤 경우에 고전적으로 다루기 쉬운지, 그리고 어떤 경우에 상당한 오버헤드를 유발하는지를 명확히 한다.