技術要約：量子状態間のシャテン・ノルムおよびべき距離の推定

問題設定

本論文は、状態準備回路によって与えられる2つの$n$量子ビット量子状態 $\rho_0$ と $\rho_1$ の間の距離を推定する計算複雑性を調査している。主な焦点は、量子シャテン $\alpha$-ノルム距離 $T_\alpha(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\alpha = \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)^{1/\alpha}$ およびそのべき乗版である量子シャテン $\alpha$-べき距離 $\Lambda_\alpha(\rho_0, \rho_1) := \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)$ である。

取り組んでいる中心的な問いは、シャテン $\alpha$-ノルムを用いた量子状態判別問題（QSD$_\alpha$）、すなわち $T_\alpha(\rho_0, \rho_1) \geq 2/5$ か $T_\alpha(\rho_0, \rho_1) \leq 1/5$ かを判定する問題の計算複雑性である。著者らは、トレース距離（$\alpha=1$）がQSZK完全であることが知られている一方で、$\ell_2$ 的な尺度（例：ヒルベルト・シュミット距離、$\alpha=2$）はBQPに含まれるという、既知の二分性を検証している。具体的には、この二分性がすべての定数 $\alpha > 1$ に対して保持されるのか、あるいは $\alpha$ が偶数か奇数かによって複雑性が変化するのかを問うている。

さらに、本論文では $0 < \alpha < 1$ の領域についても研究している。この範囲では、$T_\alpha$ はもはや距離（三角不等式を満たさない）ではないが、$\Lambda_\alpha$ は有効な距離（準ノルムのべき）として残る。著者らは、この領域における $\Lambda_\alpha$ の効率的な推定器を求めている。

手法

1. 効率的な量子推定器

著者らは、**量子特異値変換（QSVT）およびユニタリの線形結合（LCU）**に基づいた量子アルゴリズムを開発している。

• $\alpha > 1$ の場合（ランク非依存）：
  核心となる課題は、関数 $f(x) = \text{sgn}(x)|x|^{\alpha-1}$ を効率的に近似することである。著者らは、符号付き正のべき乗に対する最良一様多項式近似（ベルンシュタインの研究および最近のツァリス・エントロピーに関する結果に着想を得たもの）を利用している。

  • 彼らは、$[-1, 1]$ 上で一様誤差 $\epsilon$ を持つ $\frac{1}{2}\text{sgn}(x)|x|^{\alpha-1}$ を近似する多項式 $P(x)$ を構成する。
  • QSVTを用いて、$\nu = \rho_0 - \rho_1$ に対する $\text{sgn}(\nu)|\nu|^{\alpha-1}$ のブロック符号化を実装する。
  • 距離は、アダマール・テストを通じて $\text{tr}(\rho_0 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1}) - \text{tr}(\rho_1 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1})$ を計算することで推定される。
  • 革新的な点： プロジェクターのランク依存のブロック符号化に依存していた従来のアプローチ（例：[WGL+24]）とは異なり、この手法は状態のランクに依存しない多項式近似を使用しており、ランク非依存のクエリおよびサンプル複雑性を達成している。

• $0 < \alpha < 1$ の場合（ランク効率的）：
  この領域では、関数 $x^{\alpha-1}$ は $x=0$ で特異点を持つ。著者らは、ゼロから離れた場所で有効な（カットオフ $\delta$ を用いた）スケーリングされた符号付きべき乗の多項式近似を使用する。

  • アルゴリズムは、ゼロ付近で誤差が生じるものの有界な多項式を用いて $\text{sgn}(\nu)|\nu|^{\alpha-1}$ を近似することにより、$\Lambda_\alpha$ を推定する。
  • このアプローチはランク依存の複雑さ、具体的にはランク $r$ に関する多項式となるが、従来の境界を改善している。

2. 困難性と下界

計算の困難性を確立するために、著者らはトレース距離 $T(\rho_0, \rho_1)$ と $T_\alpha$ および $\Lambda_\alpha$ を関連付ける新しいランク依存の不等式を導出している。

• 不等式： 純粋状態に対しては $T_\alpha$ と $T$ は定数倍の関係にあることを証明しているが、混合状態については、関係が状態のランクに依存することを証明している。具体的には、$T(\rho_0, \rho_1) \leq 2(\text{rank}(\rho_0)^{1-\alpha} + \text{rank}(\rho_1)^{1-\alpha})^{-1/\alpha} T_\alpha(\rho_0, \rho_1)$ となる。
• 還元：
  • BQP困難性： 純粋状態に限定することで、著者らは $T_\alpha$（$\alpha \geq 1$ の場合）または $\Lambda_\alpha$（$0 < \alpha < 1$ の場合）による状態の判別が、標準的なBQP完全問題（PureQSD）と同等に困難であることを示している。
  • QSZK困難性： $\alpha$ が 1 に極めて近い場合（具体的には $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$）、$T_\alpha$ に対する**部分的偏極補題（partial polarization lemma）**を用いる。この補題により、トレース距離における偏極と同様に $T_\alpha$ のギャップを増幅することが可能となり、この領域において QSD$_\alpha$ が QSZK完全であることを証明している。
  • 定数 $0 < \alpha < 1$ の場合、トレース距離への偏極を適用し、$T^\alpha$ とランクを用いた $\Lambda_\alpha$ の上界を用いることで、PoweredQSD$_\alpha$ が QSZK困難であることを示している。

主要な貢献と結果

1. 効率的な量子アルゴリズム

• 定数 $\alpha > 1$ の場合： 著者らは、$O(1)$ クエリ（ランク非依存）を用いて、加法的誤差 $\epsilon$ で $T_\alpha(\rho_0, \rho_1)$ を推定する効率的な量子アルゴリズムを提示している。実行時間は、状態準備回路が多項式サイズであれば $\text{poly}(n)$ である。
  • これは、ランク $r$ に依存していた以前の最良の結果 [WGL+24]（クエリ複雑度 $\tilde{O}(r^{3+1/\{\alpha/2\}}/\epsilon^{4\alpha+\dots})$）に対する指数関数的な高速化を意味する。
  • サンプル複雑性も $\tilde{O}(1/\epsilon^{3\alpha+2+\dots})$ と改善され、ランクに依存しない。
• 定数 $0 < \alpha < 1$ の場合： 効率的なアルゴリズムが、クエリ複雑度 $\tilde{O}(r^{2/(\alpha-1)}/\epsilon^{2/\alpha})$ で $\Lambda_\alpha(\rho_0, \rho_1)$ を推定する。これは以前の最良の境界 $\tilde{O}(r^{5/\alpha}/\epsilon^{5/\alpha+1})$ を改善しているが、依然としてランク $r$ に依存する。

2. 計算複雑性の二分性

本論文は、QSD$_\alpha$ における鋭いフェーズトランジション（相転移）を確立している：

• ケース $\alpha > 1$ （固定定数）： QSD$_\alpha$ は BQP完全 である。この問題は量子コンピュータ上で効率的に解くことができ、推定器はランク非依存である。
• ケース $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$： QSD$_\alpha$ は QSZK完全 である。BQP = QSZK でない限り、効率的な量子推定器は存在しない。
• ケース $0 < \alpha < 1$ （固定定数）： PoweredQSD$_\alpha$ は QSZK困難 である。

3. 新しい不等式

著者らは、トレース距離をシャテン・ノルムおよびべき距離に結びつける新しいランク依存の不等式を提供している。これらの不等式は独立した関心事であり、特に「容易な」領域（純粋状態）がいかにして「困難な」領域（高ランクの混合状態）へと $\alpha$ が 1 に近づくにつれて移行するかを示すための、困難性還元の鍵となっている。

意義

本論文は、導入部で提起された、一般的なシャテン $\alpha$-ノルムに関する近接性テストの計算複雑性に関する問題 1を解決している。

• これは、$\ell_1$ 的な尺度（QSZK困難）と $\ell_2$ 的な尺度（BQP含有）の間の二分性が、単に偶数と奇数の区別ではなく、$\alpha=1$ と任意の定数 $\alpha > 1$ の間で起こる鋭い転移であることを示している。
• ランク非依存の推定器の開発は、重要な技術的進歩であり、以前は状態のランクに関する知識や依存を必要としていた量子状態の特性評価における主要なボトルネックを取り除いた。
• これらの結果は、量子状態の判別可能性の景観を明確にしている。すなわち、$T_\alpha$（$\alpha > 1$ の場合）はトレース距離の自然な下界を提供する一方で、トレース距離自体とは異なり、任意の固定された $\alpha > 1$ に対して効率的に計算可能であることを示している。

著者らは、$\alpha = \infty$ のケースは依然として未解決の問題であり、関連する約束問題 QSD$_\infty$ は BQP困難であり QMA に含まれるが、BQP への包含については現時点では不明であると述べている。また、表1の定量的境界をさらに厳密化できるかという問いも残されている。