Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

기술 요약: 삼중 효율적 섀도 토모그래피를 위한 분수 채색 추측에 대한 반례

1. 문제 정의

본 논문은 미지의 양자 상태 $\varrho$의 복사본을 최소한으로 사용하여, 파울리 관측량 집합 $S \subseteq \mathcal{P}_n$에 대한 기댓값 $\text{tr}(\varrho P)$를 추정하는 작업인 **파울리 섀도 토모그래피(Pauli shadow tomography)**의 효율성을 다룬다.

King, Gosset, Kothari, 그리고 Babbush(KGKB)가 제안한 2-복사 프로토콜과 같은 최근의 프로토콜들은 관측량들과 연관된 반교환 그래프(anticommutation graph) $G(S)$의 **분수 그래프 채색(fractional graph coloring)**에 의존한다. 이 그래프에서 정점은 파울리 문자열을 나타내며, 간선은 서로 반교환하는 문자열들을 연결한다. 이러한 프로토콜의 샘플 및 시간 복잡도는 관측량들의 분수 색수(fractional chromatic number) $\chi_f(G)$에 직접적으로 비례한다.

이 분야의 핵심 질문은 $\chi_f$가 기댓값의 크기에 따라 어떻게 스케일링되는가이다. $B_\epsilon(\varrho)$를 기댓값의 절댓값이 $\epsilon$ 이상인 파울리 관측량들의 집합이라고 하자. 추측 2(원래 KGKB의 추측 13)는 모든 상태 $\varrho$와 오차 $\epsilon$에 대하여 다음을 만족하는 보편적인 상수 $C$가 존재한다고 가정한다:
$$\chi_f(B_\epsilon(\varrho)) \cdot \epsilon^2 \leq C$$
만약 이 추측이 참이라면, 이는 2-복사 프로토콜의 샘플 복잡도가 $O(\log|S|/\epsilon^4)$로 스케일링되어, 어떤 파울리 부분집합에 대해서도 "샘플 효율적(sample-efficient)"임을 의미할 것이다. 본 논문은 이 $\chi_f$가 보편적으로 성립하는지 조사한다.

2. 방법론

저자들은 시스템 크기가 증가함에 따라 곱 $\chi_f \cdot \epsilon^2$이 무한히 커지는 특정 양자 상태 및 관측량 집합을 구성함으로써 추측 2를 반증한다. 연구 방법론은 두 가지 주요 이론적 도구에 의존한다:

1. 사전식 그래프 곱(Lexicographic Graph Products): 저자들은 그래프 $G$의 각 정점에 그래프 $H$의 복사본을 배치하는 구성인 사전식 곱($G \text{ lex } H$)을 활용한다. 이 구성에서 활용되는 핵심 속성은 그래프 불변량의 곱셈성이다:

   • $\chi_f(G \text{ lex } H) = \chi_f(G) \cdot \chi_f(H)$
   • $\beta(G \text{ lex } H) = \beta(G) \cdot \beta(H)$
   • $\alpha(G \text{ lex } H) = \alpha(G) \cdot \alpha(H)$
     여기서 $\alpha$는 독립수(independence number)이고 $\beta$는 교환 지수(commutativity index 또는 $\beta$-number)이다.

2. 텐서 곱을 통한 증폭(Amplification via Tensor Products): 저자들은 그래프 곱을 양자 시스템으로 매핑한다. 베이스 그래프 $G$의 $m$중 사전식 곱을 취함으로써, 그에 대응하는 파울리 관측량 집합 $A_m$과 양자 상태 $\varrho_m$($\beta$-수를 최대화하는 상태들의 텐서 곱으로 구성됨)을 구축한다. 이 설정은 분수 색수와 제곱된 기댓값 사이의 비율을 증폭시킨다.

3. 주요 기여 및 결과

정리 A: 안티-헵타곤(Anti-heptagon)을 통한 구체적 반례

저자들은 안티-헵타곤 그래프($C_7$, 즉 7-사이클의 여그래프)를 사용하는 구체적인 반례를 제시한다.

• 구성: 이들은 7개의 파울리 문자열로 $C_7$을 구현하는 집합을 정의하고, 해밀토니안 $H = \sum_{A \in A} A$를 고려한다. 이 해밀토니안의 바닥 상태 $\varrho$는 모든 관측량에 대해 동일한 기댓값 $a = | \text{tr}(\varrho A) | = \frac{1 + 2\sqrt{2}}{7}$를 갖는다.
• 초기 위반: 베이스 케이스의 경우, $\chi_f(C_7) = 7/2$이다. 이때 곱 $\chi_f \cdot a^2 \approx 1.0469$이다. 이 값이 1을 초과하긴 하지만, 추측은 모든 상태와 그래프에 대해 곱을 제한하는 어떤 상수 $C$가 존재함을 주장하는 것이다. 이 값의 중요성은 이것이 1보다 엄격히 크며, 증폭을 위한 시드(seed) 역할을 한다는 점에 있다.
• 증폭: $m$중 사전식 거듭제곱 $C_7^{\text{lex } m}$을 취함으로써, 분수 색수는 $(7/2)^m$으로 스케일링되는 반면, 기댓값은 $a^m$으로 스케일링된다. 따라서 곱은 다음과 같이 된다:
  $$\chi_f(B_{\epsilon_m}) \cdot \epsilon_m^2 \geq \left( \frac{9 + 4\sqrt{2}}{14} \right)^m \approx (1.046918)^m$$
  $m \to \infty$일 때, 이 값은 무한대로 발산하며, 모든 상태와 그래프에 대해 위 부등식을 만족하는 유한한 상수 $C$가 존재하지 않음을 증명한다.
• 스케일링: 저자들은 이 계열에 대해 $\chi_f$가 $\Omega(\epsilon^{-2.07598})$로 스케일링되어, 추측된 $O(\epsilon^{-2})$ 경계를 위반함을 도출한다.

정리 B: $\beta$-수를 통한 일반적 반례

저자들은 $\beta$-수(교환 지수)를 사용하여 결과를 일반화한다. $\beta(G) = \max_\varrho \sum_{A \in A} \text{tr}(\varrho A)^2$로 정의된다.

• 조건: $\alpha(G) < \beta(G)$를 만족하는 임의의 그래프 $G$는 추측 2의 반례를 제공한다.
• 메커니즘: 충분히 높은 기댓값을 가진 관측량들을 선택하기 위해 "임계 정리(Threshold Lemma)"를 사용하여, 이러한 그래프들에 대해 $\chi_f(B_{\epsilon_m}) \cdot \epsilon_m^2$가 $\beta(G)/\alpha(G)$의 $m$승에 비례하는 항에 의해 하한이 됨을 증명한다. 이 구성은 해밀토니안의 바닥 상태가 아닐 수도 있는, $\beta(G)$의 최댓값을 달성하는 상태 $\sigma$를 활용한다.
• 존재성: $\alpha(G) < \beta(G)$를 만족하는 그래프(예: $2 < \frac{9+4\sqrt{2}}{7}$인 안티-헵타곤)가 존재하므로, 추측 2는 일반적으로 거짓이다.

4. 의의 및 주장

본 논문은 추측 2가 거짓임을 확립한다. 구체적으로, 모든 양자 상태와 오차 임계값에 대하여 $\chi_f(B_\epsilon(\varrho)) \cdot \epsilon^2 \leq C$를 만족하는 보편적인 상수 $C$는 존재하지 않음을 입증하였다.

저자들은 이 결과의 함의를 다음과 같이 신중하게 설명한다:

• 특정 경계의 반증: 이 결과는 $\chi_f$가 $O(\epsilon^{-2})$로 스케일링된다는 특정 주장을 반증한다.
• 효율성에 관한 열린 질문: 저자들은 추측 2를 반증하는 것이 삼중 효율적 섀도 토모그래피 프로토콜의 존재 가능성을 배제하는 것은 아님을 명시적으로 밝힌다. $\chi_f = O(\epsilon^{-\kappa})$ (단, $\kappa > 0$)와 같은 더 약한 경계가 존재할 가능성은 여전히 열려 있는 문제이다. 만약 그러한 경계가 존재한다면, 스케일링은 추측된 $O(\epsilon^{-2})$와 다르겠지만, 여전히 샘플 효율적인 프로토콜은 가능할 것이다.
• 이론적 통찰: 이 연구는 양자 측정 작업의 복잡성을 분석하는 데 있어 사전식 그래프 곱과 $\beta$-수의 유용성을 강조하며, 그래프 불변량과 양자 기댓값 사이의 관계를 이해하기 위한 새로운 프레임워크를 제공한다.

결론적으로, 본 논문은 명시적인 반례를 구성하기 위해 그래프 이론적 증폭 기법을 활용하여, 섀도 토모그래피에서의 분수 색수 스케일링에 관한 특정 추측을 엄밀하게 수학적으로 반증하였다.