Predicting properties of Scrooge ensembles with high accuracy and low sample complexity

기술 요약: 높은 정확도와 낮은 샘플 복잡도로 스쿠루지 앙상블(Scrooge Ensembles)의 성질 예측하기

문제 정의
밀도 행렬 $\rho$와 연관된 스쿠루지 앙상블은 평균 밀도 행렬이 $\rho$인 순수 상태들의 최대 무작위 앙상블으로 정의된다. 이 앙상블은 양자 다체 역학, 깊은 열화(deep thermalization), 그리고 섀도 토모그래피(shadow tomography) 및 시뮬레이터 벤치마킹과 같은 양자 정보 처리 과업을 이해하는 데 매우 중요하다. 그러나 이러한 앙상블을 분석하고 준비하는 것은 계산적으로 매우 까다롭다.

스쿠루지 앙상블의 고유한 통계적 성질은 그들의 고차 모멘트 $\chi^{(k)}_{Sc}(\rho)$에 인코딩되어 있다. 하르-무작위(Haar-random) 모멘트가 깔끔한 해석적 공식을 갖는 것과 달리, 스쿠루지 모멘트는 분모 항 $\langle \psi | \rho | \psi \rangle^{k-1}$을 포함하는 비다항식 적분 형태를 띤다. 이러한 구조는 표준적인 하르 적분 기법의 직접적인 적용을 차단한다. 기존의 물리적 메커니즘들—투영된 앙상블(얽힌 상태의 일부를 측정) 또는 시간적 앙상블(시간 진화)을 통해 스쿠루지 앙상블으로부터 샘플링하는 방식—은 비효율적이다. 투영된 앙상블은 일반적으로 비용이 많이 드는 사후 선택(postselection)을 요구하며(성공 확률이 $1/k!$로 스케일링됨), 시간적 앙상블은 최소 에너지 갭에 반비로 스케일링되는 시간 동안의 진화가 필요하여 대규모 시스템에서는 실용적이지 않다.

방법론
저자들은 이러한 장벽을 극복하기 위해 두 가지 접근 방식, 즉 모멘트 연산자의 고정밀 다항식 근사와 이를 구현하기 위한 효율적인 양자 알고리즘을 제안한다.

1. 스쿠루지 모멘트의 다항식 근사:
   핵심적인 어려움은 스쿠루지 모멘트 정의의 분모에 있다:
   $$\chi^{(k)}_{Sc}(\rho) = \mathbb{E}_{\psi \sim \text{Haar}} \left[ \frac{D (\sqrt{\rho} |\psi\rangle\langle\psi| \sqrt{\rho})^{\otimes k}}{\langle \psi | \rho | \psi \rangle^{k-1}} \right]$$
   저자들은 하르-무작로 상태에 대해, 양 $r_\phi = D \langle \phi | \rho | \phi \rangle$가 $\rho$의 순도가 충분히 낮을 때(즉, $\|\rho\|_\infty$가 작을 때) 1 근처로 집중된다는 점에 주목한다. 이들은 특이 항 $1/r_\phi^{k-1}$을 $x=1$ 주변에서의 테일러 급수 전개를 통해 유도된 조절 가능한 다항식 근사 $g_\lambda(x)$로 대체한다.
   $$g_\lambda(x) = \sum_{j=0}^{\lambda-1} (1-x)^j$$
   이를 통해 스쿠루지 모멘트를 해석적으로 다룰 수 있는 표준 하르 모멘트들의 선형 결합으로 변환한다. 근사 오차는 조절 가능하다. 즉, 확장 차수 $\lambda$를 높임으로써 오차를 $1/\|\rho\|_\infty$에 대해 지수적으로 작게 줄일 수 있으며, 이는 기존 결과들이 오차가 $\|\rho\|_\infty$에 대해 다항식적으로 스케일링되었던 것보다 크게 개선된 것이다.

2. 효율적인 대칭 부분 공간 투영:
   $\rho^{(k)}_{\text{sym}} = \rho^{\otimes k} \Pi^{(k)}_{\text{sym}} / p_{\text{sym}}$ 형태의 상태를 구현하기 위해, 저자들은 $\Pi^{(k)}_{\text{sym}}$를 $k$-중 대칭 부분 공간으로의 투영사라고 할 때, 이를 구현해야 한다. 표준적인 사후 선택은 비효율적이다($O(k!)$ 비용).
   대신, 저자들은 **슈어-바일 듀얼리티(Schur-Weyl duality)**를 활용한다. $\rho^{\otimes m}$ ($m \ge k$)에 슈어 변환을 적용하여, 영 다이어그램(Young diagrams) $\gamma$로 라벨링된 기약 표현 섹터들로 상태를 분해한다. 각 섹터 내에서 치환 레지스터의 상태는 알려져 있다. 알고리즘은 치환 레지스터를 해당 섹터에 필요한 특정 대칭 상태로 조건부로 교체함으로써, 사후 선택 없이 대칭 부분 공간으로 효과적으로 투영한다. 이 절차에는 $O(k^3/\epsilon^2)$개의 $\rho$ 샘플이 필요하다.

3. 기댓값 계산을 위한 양자 알고리즘:
   다항식 근사와 효율적인 투영을 결합하여, 저자들은 임의의 관측량 $O_k$에 대해 $\text{Tr}[\chi^{(k)}_{Sc}(\rho) O_k]$를 추정하는 양자 알고리즘을 구성한다. 이 알고리즘은 견고성을 보장하기 위해 중앙값-평균(median-of-means) 추정기를 사용하여 다항식 전개의 각 항에 대한 정규화 인자와 기댓값의 곱을 추정한다.

주요 기여 및 결과

• 고정밀 근사: 본 논문은 $\|\rho\|_\infty$에 대해 지수적으로 작은 오차를 달성하는 스쿠루지 $k$차 모멘트의 다항식 근사를 도입한다. 이는 이전 방법들이 요구했던 매우 혼합된 상태를 넘어, 더 넓은 범위의 상태에 대해 정확한 근사가 가능하도록 확장한다.
• 효율적인 양자 알고리즘: 저자들은 스쿠루지 모서 댓값의 기댓값을 추정하는 최초의 효율적인 양자 알고리즘을 제시한다. 목표 오차 $\epsilon$에 대해, 알고리즘은 $\tilde{O}(k^3/\epsilon^5)$개의 $\rho$ 복사본을 필요로 한다.
• 사후 선택이 없는 투영: 핵심 서브루틴은 $\rho^{\otimes k}$를 $O(k^3/\epsilon^2)$ 샘플을 사용하여 대칭 부분 공간으로 투영하는 효율적인 방법이다. 이는 표준 사후 선택의 가혹한 $k!$ 비용을 피한다.
• 블록 인코딩 구성: $\rho$의 정제(purification)를 위한 준비 회로가 주어질 때, 저자들은 스쿠루지 $k$차 모멘트의 블록 인코딩을 구성한다. 이는 스쿠루지 모멘트를 표준 블록 인코딩 프레임워크에 통합하여, 양자 특이값 변환(QSVT)과 같은 고급 양자 알고리즘에서 사용할 수 있게 한다.
• 수치적 검증: 횡장 이징 모델(transverse-field Ising chain)의 깁스 상태에 대한 수치 시뮬레이션을 통해, 근사 오차가 확장 차수 $\lambda$에 따라 빠르게 감소하며 이론적 상한보다 훨씬 작음을 확인하였다.

의의 및 주장
본 논문은 스쿠루지 앙상블의 성질에 대한 이론적 분석과 실제 예측을 위한 최초의 효율적이고 고정밀한 도구를 제공한다고 주장한다. 비다항식 적분 형태를 조절 가능한 다항식으로 대체하고, 사후 선택을 우회하기 위해 슈어-바일 듀얼리티를 활용함으로써, 이 연구는 연관된 밀도 행렬의 복사본만을 사용하여 깊게 열화된 앙상블을 연구할 수 있게 한다. 이러한 복사본은 앙상블 자체보다 준비하기가 더 쉽다.

저자들은 다음과 같은 잠재적 응용 분야를 제시한다:

• 다체 계의 정보 이론적 양의 정밀한 특성화.
• 양자 시뮬레이터의 벤치마킹 프로토콜 개선.
• 재가중치(reweighting)를 위해 스쿠루지 모멘트를 활용함으로써 섀도 토모그래피 프로토콜을 향상시킬 가능성 (단, 이 특정 응용에 대한 구체적인 구현과 복잡도 보장은 아직 확립되지 않았음을 명시함).

본 논문은 고순도 상태에 대해서는 신중한 입장을 유지하며, 현재의 근사 보장이 $\|\rho\|_\infty$가 증가함에 따라 약화된다는 점을 인정하고, 임의의 밀도 행렬으로의 확장을 향후 연구를 위한 미해결 과제로 남겨두었다.