技術要約：最適トレース距離推定を用いた演算子ノルム距離の推定

問題設定

本論文は、2つの$n$量子ビット量子状態 $\rho_0$ と $\rho_1$ の間の演算子ノルム距離 $T_\infty(\rho_0, \rho_1)$ を推定することの計算複雑性を調査している。この距離は $T_\infty(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\infty$ と定義される（ここで $\|\cdot\|_\infty$ は演算子ノルム、すなわち最大特異値を表す）。

状態は、多項式サイズの状態準備回路 $Q_0$ および $Q_1$ を通じて提供される。目標は、誤差 $\epsilon$ 以内でこの距離を推定する量子アルゴリズムを設計することであり、そのクエリ複雑性は、状態のランク（したがって次元 $d=2^n$）に依存しないものである。これは、$\alpha > 1$ の場合の古典的な $\ell_\alpha$ 距離の結果と同様に、演算子ノルム距離に対してランクに依存しない境界が存在するかどうかという未解決問題に取り組むものである。

手法

著者らは、ユニタリ拡張（unitary dilation）、量子ビット化（qubitization）、および**最大位相推定（maximum phase estimation）**を組み合わせたフレームワークを採用している。核心となる戦略は、エルミート演算子 $\Delta = (\rho_0 - \rho_1)/2$ の固有値をユニタリ演算子の固有位相にマッピングし、量子位相推定技術を通じて効率的に推定することである。

1. ユニタリ拡張と量子ビット化

状態準備回路による $\rho_0$ と $\rho_1$ が与えられたとき、著者らは**線形結合によるユニタリ（LCU）**技術と純化密度行列の手法を用いて、$\Delta$ のユニタリ拡張 $U_\Delta$ を構成する。

• 彼らは、量子ビット化ユニタリ $W = U R U^\dagger R$ （ここで $R$ は反射演算子）を定義する。
• この構成により、$\Delta$ の固有値 $\lambda$ と $W$ の固有位相 $\theta$ の間に単調な対応関係（$\theta = 2 \arccos(\lambda)$、全位相を除いて）が作成される。
• $\|\Delta\|_\infty$（最大固有値の絶対値）を推定する問題は、$W$ の最大固有位相を推定することへと還元される。

2. 「ウォームスタート（Warm Start）」戦略

位相推定における決定的な課題は、入力状態がターゲットとなる固有空間（$\Delta$ のトップ固有空間）に対して無視できないオーバーラップを持つことを保証することである。論文では、入力状態の純粋性に基づいて2つのケースを区別している。

• ケース1：一方の状態が純粋状態である場合（ウォームスタート・レマ）
  一方の状態（例えば $\rho_0 = |\psi\rangle\langle\psi|$）が純粋であるとき、著者らは構造的レマ（Lemma 3.1）を証明する。彼らは、純粋状態 $|\psi\rangle$ 自体が、$\Delta$ の最大の正の固有値に対応する一意の固有ベクトルに対して、少なくとも $1/2$ の二乗オーバーラップを持つことを示す。

  • 直感: $\rho$ は半正定値であるため、$|\psi\rangle$ に直交する部分空間に対する $\Delta$ の制限は負の半定値である。したがって、いかなゆる正の固有値は、$|\psi\rangle$ と実質的なオーバーラップを持つ固有ベクトルに対応しなければならない。
  • この「ウォームスタート」により、定数オーバーラップパラメータ $\gamma = 1/2$ を用いた最大位相推定の使用が可能になる。

• ケース2：一般的な混合状態（固有値スケールされたオーバーラップ）
  両方の状態が混合状態である場合、定数のオーバーラップは保証されない。著者らは、入力状態の純化とトップ固有空間との間のオーバーラップが、ターゲットとなる固有値に応じてスケールするという、より弱い境界（Lemma 4.1）を導出している：$\|\Pi_{\max} |\psi_0\rangle\|^2 \ge 2\lambda_{\max}(\Delta)$。

  • ターゲットとなる距離は $\epsilon$ であるため、オーバーラップはおよそ $O(\epsilon)$ となる。
  • これを補うために、アルゴリズムは振幅増幅（暗黙的に最大位相推定ルーチンのパラメータを通じて）を採用し、成功確率を定数へと押し上げる。

主要な貢献と結果

1. 一方の純粋状態に対する最適推定

定理 1.1: 一方の状態が純粋であるとき、$T_\infty(\rho, |\psi\rangle\langle\psi|)$ またはトレース距離 $T(\rho, |\psi\rangle\langle\psi|)$ を加法的誤差 $\epsilon$ 以内で推定するための量子クエリ複雑性は $\Theta(1/\epsilon)$ である。

• 意義: これは純粋対純粋の場合の最適な境界と一致する。極めて重要な点は、この複雑性がランクに依存しないことである。従来の近似手法（van Apeldoornら、WangおよびZhangなど）は、ランク $r$ に比例するクエリ複雑性（潜在的に $O(2^n)$）を持っていたが、本手法は定数 $\epsilon$ に対して $\text{poly}(n)$ 時間で動作する。
• サンプル複雑性: サンプル・トゥ・クエリのリフティングを介して、サンプル複雑性は $\Theta(1/\epsilon^2)$ となる。

2. 一般的な状態に対する効率的な推定

定理 1.2: 一般的な量子状態 $\rho_0, \rho_1$ に対して、$T_\infty(\rho_0, \rho_1)$ を推定する量子アルゴリズムが存在し、そのクエリ複雑性は $\tilde{O}(1/\epsilon^{3/2})$ である。

• 意義: これは、$\alpha > 1$ の場合の $\ell_\alpha$ 距離に関する従来の最良の上界（一般に $O(1/\epsilon^{\alpha+1})$ またはそれ以下）を改善している。これは、既知の下界 $\Omega(1/\epsilon)$ との間に平方根の差を残しているのみである。
• サンプル複雑性: サンプル複雑性は $\tilde{O}(1/\epsilon^3)$ である。

3. 計算複雑性クラスの結果

本論文は、約束問題 QSD$_\infty$（$T_\infty \ge 2/5$ か $\le 1/5$ かを判定する問題）の計算複雑性を確立している：

• 系 1.3: QSD$_\infty$ は BQP完全 である。
• 系 1.4: 限定されたバリアントである OnePureQSD$_\alpha$（少なくとも一方の状態が純粋）は、すべての $\alpha \in [1, \infty]$ において BQP完全 である。
• これらの結果は、従来のQMA上界を改善し、演算子ノルム距離の推定が量子証拠を必要とせずに、量子コンピュータ上で効率的に解けることを確認している。

意義と主張

本論文は、演算子ノルム距離の推定におけるランク非依存性に関する長年の未解決問題を解決したと主張している。

• 構造的洞察: 著者らは、演算子ノルム距離の特定の構造的特徴を強調している。すなわち、一方の状態が純粋であるとき、その純粋状態は $\Delta$ のトップ固有空間に対する「ウォームスタート」として機能する。これは、一般的な混合状態には成立しないランク1の摂動現象である。
• 効率性: 提案された推定器は、次元 $d=2^n$ にスケールする状態トモグラフィーベースのアプローチに対して指数的な加速を実現し、ランク依存の従来の推定器に対しては多項式的な加速を実現している。
• 階層の文脈: これらの結果は、演算子ノルム距離（$\alpha = \infty$）が、量子 $\ell_\alpha$ 階層において、クエリ複雑性の観点から最も「容易な」ケース（中間的な $\alpha=2$ や $\alpha=3$ よりも容易）であることを示唆している。

最後に、論文は、一般的な混合状態の場合、上界（$\tilde{O}(1/\epsilon^{3/2})$）と下界（$\Omega(1/\epsilon)$）の間に平方根の差が依然として残っており、この境界の最適性を問うことが今後の課題であると述べている。