技術要約：トリプル効率的なシャドウ・トモグラフィーにおける分数彩色予想への反例

1. 問題設定

本論文は、未知の量子状態 $\varrho$ のコピーを最小限数用いて、一連のパウリ観測量 $S \subseteq \mathcal{P}_n$ の期待値 $\text{tr}(\varrho P)$ を推定することを目的としたパウリ・シャドウ・トモグラフィーの効率性について扱う。

King, Gosset, Kothari, および Babbush (KGKB) によって提案された2コピー・プロトコルなどの最近のプロトコルは、観測量に関連する反交換グラフ $G(S)$ の分数グラフ彩色に依存している。このグラフにおいて、頂点はパウリ文字列を表し、エッジはそれらが反交換する関係にあることを示す。これらのプロトコルのサンプルおよび時間計算量は、分数彩色数 $\chi_f(G)$ に直接比例する。

中心となる問いは、$\chi_f$ が期待値の大きさにどのようにスケールするかである。$B_\epsilon(\varrho)$ を、状態 $\varrho$ において期待値の絶対値が少なくとも $\epsilon$ であるパウリ観測量の集合とする。予想2（KGKBにおける予想13）は、すべての状態 $\varrho$ と誤差 $\epsilon$ に対して、以下の不等式を満たす普遍的な定数 $C$ が存在すると仮定している：
$$\chi_f(B_\epsilon(\varrho)) \cdot \epsilon^2 \leq C$$
もしこれが真であれば、2コピー・プロトコルのサンプル計算量は $O(\log|S|/\epsilon^4)$ となり、任意のパウリの部分集合に対して「サンプル効率的」であることが意味される。本論文は、この予想が普遍的に成立するかどうかを調査するものである。

2. 手法

著者らは、特定の量子状態および観測量の集合において、積 $\chi_f \cdot \epsilon^2$ がシステムサイズが増大するにつれて非有界に増大することを示すことで、予想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$ は独立数、$\beta$ は可換指数（または $\beta$-数）である。

2. テンソル積による増幅: 著者らは、グラフ積を量子系へとマッピングする。基本グラフ $G$ の $m$ 回の辞書式積を取ることで、対応するパウリ観測量の集合 $A_m$ と量子状態 $\varrho_m$（$\beta$-数を最大化する状態のテンソル積によって構成される）を構築する。このセットアップにより、分数彩色数と期待値の二乗の比率を増幅させることが可能となる。

3. 主要な貢献と結果

定理 A: アンチ・ヘプタゴンによる具体的な反例

著者らは、アンチ・ヘプタゴン・グラフ ($C_7$)、すなわち7サイクル ($C_7$) の補グラフを用いた具体的な反例を提示している。

• 構成: 著者らは $C_7$ を実現する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よりも厳密に大きく、増幅のための「種」として機能することにある。
• 増幅: $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$ が $(\frac{\beta(G)}{\alpha(G)})^m$ に比例する項によって下限付けられることを示す。この構成は、$\beta(G)$ の最大値を実現する状態 $\sigma$ を利用しており、これは必ずしもハミルトニアンの基底状態ではない。
• 存在性: $\alpha(G) < \beta(G)$ を満たすグラフ（例：$2 < \frac{9+4\sqrt{2}}{7}$ となるアンチ・ヘプタゴン）が存在するため、この予想は一般には成立しない。

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$ に対して）というより弱い境界が存在する可能性は依然として開かれた問題である。もしそのような境界が存在すれば、スケーリングは異なってはいるものの、依然としてサンプル効率的なプロトコルは可能である。
• 理論的洞察: 本研究は、量子測定タスクの複雑性を分析する上での、辞書式グラフ積と $\beta$-数の有用性を強調しており、グラフ不変量と量子期待値の関係を理解するための新しい枠組みを提供している。

結論として、本論文は、グラフ理論的な増幅テクニックを用いて明示的な反例を構築することにより、シャドウ・トモグラフィーにおける分数彩色数のスケーリングに関する特定の予想を厳密に数学的に論破している。