技術要約：クディットにおけるベル・サンプリングの再征服

1. 問題提起

ベル・サンプリングは、特にスタビライザー状態や「マジック」（非スタビライザー資源）を分析する際に、量子情報理論における基本的なプリミティブである。キュービット（$d=2$）の場合、ベル・サンプリング（2つの状態をベル基底で測定すること）およびその変種であるベル差分サンプリングは、未知のスタビライザー状態の効率的な学習、スタビライザー特性のテスト、および擬似ランダム状態とハール乱数状態の識別を可能にする。

しかし、これらの手法をクディット（次元 $d \geq 2$ のシステム）へ一般化することは困難であることが判明している。著者らによる先行研究（arXiv'24）は、「自然な」拡張としての任意の次元へのベル・サンプリングは失敗することを示した。すなわち、スタビライザー状態の2つのコピーを一般化されたベル基底で測定すると、完全にランダムな出力が得られ、基礎となるスタビライザー群に関する情報が全く得られない。この失敗は、転置写像（複素共役）が完全正値ではないこと、そして $d > 2$ の場合、スタビライザー状態 $|S\rangle$ とその複素共役 $|S^*\rangle$ が、キュービットの場合（$|S^*\rangle = W_z |S\rangle$）のように単純なパウリ演算子によって関連付けられるとは限らないことに起因する。

本論文が取り組む中心的な問題は、すべての次元 $d \geq 2$ のクディットに対して、キュービットの強力な特性（特にスタビライザー群の生成元をサンプリングする能力）を保持した、有用なクディット版ベル・サンプリングの一般化を開発することである。

2. メソドロジーとコア・プリミティブ

著者らは、自然な拡張の限界を克服する新しいサブーチン、**歪んだベル差分サンプリング（Skewed Bell Difference Sampling）**を提案する。核心となる革新は、ラグランジュの四平方定理に基づく特定のユニタリ変換である。

$B_R$ ユニタリ

この手法は、スタビライラー状態 $|S\rangle^{\otimes 4}$ の4つのコピーに作用するユニタリ演算子 $B_R$ に依存している。ユニタリは、非負整数 $a_1, a_2, a_3, a_4$ を用いて $a_1^2 + a_2^2 + a_3^2 + a_4^2 = d-1$ を満たすように構成された行列 $R \in \mathbb{Z}_d^{4 \times 4}$ から定義される。
行列 $R$ は、$R J R = -I \pmod d$ となるように構成されている（ここで $J$ はシンプレクティック・モジュールの対合写像である）。

主要な特性: 任意のスタビライザー状態 $|S\rangle$ に対して、ユニタリ $B_R$ は4つのコピーを（パウリ演算子を除いて）その複素共役へと写す：
$$B_R |S\rangle^{\otimes 4} = P(S) |S^*\rangle^{\otimes 4}$$
ここで $P(S)$ は $|S\rangle$ に依存するパウリ演算子である。この変換は、状態を「混合」することで、スタビライザー群とその複素共役を整列させる。これは、サンプリングを成功させるための必須条件である。

注： 特定の次元（例：$-1$が平方剰余である素数$d$の場合）では、4つ未満のコピー（例：2つのコピー、あるいは$d \equiv 1 \pmod 4$ であれば1つのコピー）でも十分な場合がある。

サンプリング手順

完全な歪んだベル差分サンプリングアルゴリズムは以下の通りである：

1. 状態 $|\psi\rangle$ の8つのコピーを用意する。
2. 4つのコピーにユニタリ $B_R$ を適用し、それらを $|S^*\rangle^{\otimes 4}$ （パウリを除いて）へと変換する。
3. 変換されたコピーを、元の4つのコピーとペアにする。
4. 各ペア $(|S\rangle, |S^*\rangle)$ に対して標準的なベル・サンプリングを実行する。
5. 出力の差分を計算する。

得られる分布 $\hat{p}_\psi$ は、符号なしスタビライザー群 $Weyl(|\psi\rangle)$ の直交補空間上に支持されることが示されている。$|\psi\rangle$ がスタビライザー状態である場合、サンプルはスタビライザー群自体上に一様に分布する。

3. 主な貢献と結果

本論文は、この新しいプリミティブが、キュービットベースのいくつかの主要な結果をすべての $d \geq 2$ のクディットへと引き上げることを実証している。

A. スタビライザー状態の学習と隠れたスタビライザー群問題

• 問題: 未知のスタビライザー状態 $|S\rangle$ または隠れたスタビライザー群 $Weyl(|\psi\rangle)$ を、状態のコピーを与えられた状態で特定する。
• 結果: 著者らは、高い確率でスタビライザー群を特定する量子アルゴリズムを、$O(n)$ 個のサンプルと $O(n^3)$ の時間で提供する。
• 改善点: これは、Hinsche, Eisert, and Carrasco [HEC26] による最近のフーリエ・サンプリング・アプローチ（$O(n \log d \max\{d, \epsilon^{-1}\})$ 個のサンプルを必要とした）を改善するものである。新手法は一度に最大8つのコピー（素数次元では4つ）で動作し、以前の手法は $D$ 個のコピー（$D$ は $2d$ になり得る）を必要としていたため、より実現可能性が高い。

B. スタビライザー・サイズ・プロパティ・テスティング

• 問題: 状態がスタビライザー・サイズ（符号なしスタビライザー群の濃度）として少なくとも $d^t$ を持つか、あるいはそのような状態から $\epsilon$ だけ離れているかをテストする。
• 結果: アルゴリズムは、$O(n/\epsilon)$ 個のサンプルを用いて $O(n^3/\epsilon)$ 時間でこれらを識別する。
• 意義: この結果は、Grewalら [GIKL25] によるキュービットの結果を、任意の次元へと一般化するものである。この解析には、体上のベクトル空間ではなく、環 $\mathbb{Z}_d$ 上の加群（モジュール）の扱いが必要であり、サンプルのスパンを分析するためにスミス標準形を用いる必要がある。

C. ドープされたクリフォード回路と擬似ランダム性のテスト

• 問題: ハール乱数状態と、$t$-ドープされたクリフォード回路（$t$ 個の非クリフォード・ゲートを持つクリフォード回路）の出力とを識別する。
• 結果: 著者らは、$t < n/2$ である任意の $t$-ドープされたクリフォード回路は、擬似ランダムな状態を生成できないことを証明した。
• 改善点: これは、クディットにおける擬似ランダム性に必要な非クリフォード・ゲートの個数の下限が $n/2$ であることを確立するものである。これは、以前のクディット特有の境界（$O(\log_d n)$）に対する指数関数的な改善であり、キュービットにおける最良の既知の境界と一致する。アルゴリズムは、$O(n)$ 個のサンプルを用いて $O(n^3)$ 時間でこれらを識別する。

D. 耐容スタビライザー・テスティング（Tolerant Stabilizer Testing）

• 問題: 状態がスタビライザー・フィデリティとして少なくとも $1-\epsilon_1$ を持つか、あるいは最大で $1-\epsilon_2$ を持つか（ここで $\epsilon_1 < \epsilon_2$）を判定する。
• 結果: 論文では2つのアルゴリズムを提案している：
  1. POVMベース: 特定の POVM $\Pi_r^+$ を用いた Gross-Nezami-Walter (GNW) プロトコルの拡張。
  2. ベル・サンプリングベース: 歪んだベル差分サンプリングと特定の測定を組み合わせたプロトコル。
• 複雑性: 両アルゴリズムとも、$O(d^2 \epsilon_2 / (\epsilon_2 - \epsilon_1)^2)$ 程度のサンプル複雑性を達成する。ベル・サンプリング・アプローチは、（多くのコピーを必要とする可能性がある $2r$ 個のコピーを必要とする）POVM アプローチと比較して、より少ないコピー（8個）で済むが、POVM アプローチの方が特定の次元において、より広いパラメータ範囲を提供できる可能性がある。

4. 意義と主張

本論文は、有用な一般化を提供することで、クディットにおけるベル・サンプリングを「再征服」したと主張している。

• 理論的突破口: ラグランジュの四平方定理に基づくユニタリ $B_R$ の構成は、高次元においてスタビライザー状態をその複素共役に写す際の根本的な障害を解決する、独立した関心を持つプリミティブとして提示されている。
• 統一: 本研究は、スタビラー状態の理論を、素数次元の制限を超えて、すべての次元 $d \geq 2$ において統一するものである。
• 効率性: アルゴリズムは、$\mathbb{Z}_d$ 上の加群を扱うことによる代数的複雑さが増しているにもかかわらず、キュービットの場合と同等の多項式時間およびサンプル複雑性（$O(n^3)$ および $O(n)$）を維持している。
• 擬似ランダム性の境界: クディットにおける擬似ランダム性に $n/2$ 個の非クリフォード・ゲートが必要であるという結果は、以前の境界を大幅にタイトニングしたものであり、キュービットとクディットの理論の間のギャップを埋めるものである。

著者らは、彼らの結果が新しいサンプリング分布 $\hat{p}_\psi$ の性質に厳密に由来しており、未証明の予想に依存していないことを強調している。また、耐容テスティングのサンプル複雑性が、最良のキュービットの結果と比較して $d^2$ の係数分だけわずかに劣るものの、これは一般的なクディットへの最初の成功した拡張であることを明記している。