A Memory-Magic Exchange Law in Streaming Clifford+T Compilation

技術要約：ストリーミングClifford+Tコンパイルにおけるメモリとマジックの交換則

問題提起
本論文は、フォールトトレラント量子計算におけるストリーミング・コンパイルの文脈において、古典的メモリと量子「マジック」（非Clifford Tゲート）の間のリソース・トレードオフを扱う。多くの量子アルゴリズム（例：トロッター・ステップ、ランダム化コンパイル、フェーズ・多項式スケジューリング）では、目標となる回転角が、複数ラウンドにわたって配信される「シェア（分担量）」の総和として提示される。コンパイラは各シェアの到着時に、以下の選択を迫られる：

1. メモリ： 総和が判明するまでシェアを古典的メモリに保存し、その後、単一の回転を合成する。これには、古典ビット（スナップショット・サイズ）のコストが発生する。
2. マジック： 各シェアが到着するたびに、回転を即座に合成して実行する。これには、最終的な総和が判明する前にコミットされるTゲート（マジック状態）のコストが発生する。

中心となる問いは、失われるメモリのビット数と、必要とされるコミットされたTゲート数の間の交換率 $\alpha$ はいくらであるか、ということである。具体的には、コンパイラがシェアを保存しないことを選択した場合、正当性を維持するためにいくつのTゲートをコミットしなければならないのか。

手法
著者らは、この問題をアンシラフリーの座標ごとのClifford+Tモデル（各フェーズ多項式の座標が、座標間のキャンセルやアンシラの助けを借りずに、単一の単一量子ビット・シンセサイザによって独立して合成されるモデル）の中で分析している。

その手法は、情報理論的な下界と、算術幾何学およびスペクトル理論を組み合わせたものである：

1. 情報理論的下界： ファノの不等式とMatsumoto–AmanoによるClifford+Tユニタリの計数を用いて、欠落したシェアのエントロピーとコミットされたTゲート数の関係を示すベースラインの境界を確立する。
2. スペクトル法（ヘッケ作用素）： 特定のTカウント $\tau$ を持つClifford+Tワードのうち、回転余剰（rotation coset）の $\epsilon$-チューブ内に存在するものの数を数える。著者らは、回転余剰の分布を推定するために、Lubotzky–Phillips–Sarnak (LPS) エクスパンダーグラフ（ヘッケ作用素経由）のラマヌジャン境界を利用する。これにより、誤差項における「平方根の障壁」が得られる。
3. 初等行列式法： スペクトル的障壁を超えるために、著者らは数論的幾何学の手法（Bombieri–PilaおよびHeath-Brownに着想を得たもの）を採用する。彼らは、$\mathbb{Z}[\sqrt{2}]$ の実埋め込みにおける球体上の格子点へとClifford+Tワードを持ち上げる。小さなボックス内の点のアフィン行列式を分析し、高さの二分法を用いることで、自己型関数（automorphic forms）に依存せずに、余剰付近のワードの数をより厳密に計数する。
4. 数値的列挙： 著者らは、理論的な計数を検証し、等分布予想をテストし、調整されたグリッド上での正確な合成コストを測定するために、Tカウント22までのすべての単一量子ビットClifford+Tユニタリ（$3.0 \times 10^8$ ワード）の徹底的な列挙を行う。
5. 拡張： 確率的混合（混合ユニタリ・チャネル）および測定適応型プロトコルへの拡張を行い、これらの手法が交換率をどのように変化させるかを決定する。

主要な貢献と結果

• 無条件の下界（レート1）： 本論文は、失われた1ビットのメモリにつき、少なくとも1つのコミットされたTゲートが必要であることを証明している。これは、Tゲートが最大でも1ビットの角度情報しか持たないという事実（Matsumoto–Amano計数）から導かれる。
• レート2（スペクトル境界）： ラマヌジャン境界を用いて、回転余剰付近のワードの数は $2^{\tau/2}$ に比例する項で抑えられることを示す。これは、Tカウント $\tau$ のコミットされたワードが、その座標について最大 $\tau/2$ ビットの情報を持つことを意味する。したがって、交換率は少なくとも $\alpha \ge 2$ である。この境界は、明示的な加法的定数と共に無条件に成立する。
• レート11/5 および 17/7（行列式法）： スペクトル境界を初等行列式法に置き換えることで、誤差項の指数を改善する。
  • 著者らは、漸近的に $\alpha \ge 11/5 = 2.2$ の無条件のレートを証明する。この結果は定理4（$20/9 L$ までのTカウントに関する境界を確立）に基づいているが、定理5（レート11/5）は、$L \ge 110$ である場合に限定される。
  • ハイパープレーンの高さによる高さの二分法（球面の断面を分割する）を導入することで、漸近的レートを $\alpha \ge 17/7 \approx 2.43$ に引き上げる。この結果（定理7）は、Tカウントが $17/7 (L+2)$ までの場合に適用されるが、著者らは暗示される定数が天文学的に大きいことを指摘しており、これは実用的な精度においては空虚な記述であるため、主に漸近的レートに関する記述である。
• レート3（予想および典型的なケース）： 著者らは、予想1 を提示し、余剰付近のワードの数はボリューム則 $O(2^{\tau} \epsilon^2)$ （無限次ワードに対する線形加法的項を含む）に従うと主張している。もしこれが真であれば、交換率は $\alpha = 1 + \beta = 3$ （ここで $\beta=2$ は$SU(2)$における回転余剰の余次元）となる。
  • 定理11 は、「回転セグメント化された」プロセス（コミットされた各セグメントがCliffordフレームの回転に近いもの）において、レートが3に近づくことを無条件に証明している。
  • 定理8 は、平均単一回転合成コストが $(3+o(1))L$ である場合に、レートが3に近づく「分数パススルー（fractional passthrough）」スキームを提示している。$\epsilon = 10^{-10}$ における数値的証拠は、$\approx 3.20$ の達成されたレートを示している。
• コミットメントの量子化： メモリは、座標内において小さな単位で削減することはできない。より多くの $O(\log L)$ ビットの情報を運ぶためには、「入場料」（およそ $2L$ の最小Tカウント）が必要となる。この料金を下回る場合、利用可能なのは疎なワードの集合（Tの累乗や安価な無限次ワード）のみである。
• サイド情報： 境界は条件付きエントロピーを用いて精緻化される。コンパイラがサイド情報（例：ランダム化コンパイルのシード）を保持している場合、コストは全集計サイズ（$m \log K$）ではなく、欠落しているエントロピー（$\lambda$ ビット）に対して課される。
• モデル依存性：
  • 確率的混合： 交換率を1/2の係数でリスケールし（レートは $\approx 1.5$ となる）、最初の $\frac{1}{2}L - O(\log L)$ ビットを「無料」にすることを可能にするが、残りの「粗い」ビットに対するレートは2（または予想の下では3）のままである。
  • フェーズ勾配レジスタ： クリーンなアンシラと触媒的なフェーズ勾配レジスタを使用することで、座標を跨いだバッチ処理が可能になり、レートを $O(1/\log \log(1/\epsilon))$ に減少させ、座標ごとの合成における定数レートの法則を打破できる。

意義と主張
本論文は、単純な「1ゲートあたり1ビット」の限界を超える、ストリーミング・コンパイルにおけるメモリとマジックの交換率に関する、初の厳密かつ無条件な下界を確立したと主張している。

• 著者らは、$\alpha = 2$ をスペクトル法の自然な閾値とし、$\alpha = 17/7$ を現在の初等的な幾何学的手法の限界としている。
• 著者らは、真のレートは $\alpha = 3$ （単一回転のRoss–Selinger合成コストと一致する）であると仮定しているが、これを証明するには、数論的幾何学におけるギャップ（具体的には、回転余剰付近の格子点の等分布予想）を埋める必要があると述べている。
• 著者らは、この「料金」（情報を運ぶためのエントリーコスト）は、決定論的なユニタリモデルと合成メカニズムの特性であり、一般的なフォールトトレラント合成全般の特性ではないことを強調している。
• これらの結果は座標ごとの合成に特化したものである。論文は、アンシラ支援型の合成（例：フェーズ勾配レジスタ）を用いることで、これらの定数レートの法則を回避できることを明記しており、導出された境界はアンシラフリーかつ座標ごとのモデルに固有のものであるとしている。

本論文は、レートが正確に3であるという予想を証明したとも、新しい実験的プロトコルを提案したとも主張していない。むしろ、決定を下すことを遅らせることの根本的な限界を理解するための厳密な枠組みを提供し、「メモリレス（記憶を持たないこと）」のコストを、マジック状態の消費量の観点から定量化している。