Improved Quantum Algorithms for Rényi Entropies Estimation

技術要約：レニー・エントロピー推定のための改良された量子アルゴリズム

問題提起
本論文は、未知の離散確率分布 $p = (p_i)_{i=1}^n$ のレニー・エントロピー $H_\alpha(p)$ を推定するという根本的な問題に取り組んでいる。目標は、精製された量子オラクルへのクエリ数を最小限に抑えつつ、$H_\alpha(p)$ の加法的 $\epsilon$-近似を計算することである。著者らは、純化された量子クエリ・アクセスモデルを検討している。このモデルでは、ユニタリ・オラクル $U_p$ が状態 $\sum_{i=1}^n \sqrt{p_i}|\phi_i\rangle_G|i\rangle_B$ を準備し、これにより古典的なサンプリングよりも強力なリソースである、オラクル呼び出し間のコヒーレントなアクセスと干渉が可能となる。

具体的な課題は、次数パラメータ $\alpha$ が非整数の領域にあることである。整数次 $\alpha > 1$ の場合は衝突ベースの推定が可能であるが、非整数の次数では、エントロピーの定義における対数変換のため、単なる加法的精度ではなく、べき乗和 $P_\alpha(p) = \sum p_i^\alpha$ を高い相対精度で推定する必要がある。Wang, Zhang, Li [19] や Chen et al. [20] による従来の量子アルゴリズムは、分布のサイズ $n$ と精度 $\epsilon$ に対する依存性において最適ではない上界を提供していた。

手法
著者らは、Chen et al. [20] によって導入されたマルチレベル推定フレームワークを適応および洗練させている。このフレームワークは、確率区間 $[0, 1]$ を幾何級数的に減少するセクションに分割し、分布の汎関数を推定するために**量子特異値変換（QSVT）**を用いた局所多項式近似を使用する。

主な手法的革新は以下の通りである：

1. べき乗和の相対近似： ツァリス・エントロピーではべき乗和の加法的近似で十分であるが、レニー・エントロピーでは $P_\alpha(p)$ の相対精度が必要となる。著者らは、べき乗和の大きさを利用することで、この相対精度を実現するためにマルチレベル・フレームワークを適応させた。
2. 未知の境界のための二分探索： アルゴリズムは当初、$P_\alpha(p)$ の上界が既知であることを仮定している。この要件を取り除くために、著者らは二分探索戦略を採用し、定数相対精度が得られるまで上界を反復的に精緻化し、その後に高精度推定ステップを行う。
3. 異なる領域のための異なる初期状態：
   • $\alpha > 1$ の場合： アルゴリズムは、分布 $p$ から導出される標準的な状態準備を使用する。これは、$P_\alpha(p)$ の既知の上界 $R$ に基づいて幾何学的区間を設定することで、確率の変動を扱う。
   • $0 < \alpha < 1$ の場合： 著者らは、修正された初期状態（ラベルの一様重ね合わせ $\sum \frac{1}{\sqrt{n}}|i\rangle$）を導入する。この変更により、$0 < \alpha < 1$ において問題となる特異関数 $p^{\alpha-1}$ を近似するための局所多項式を必要とせずに済むようになる。
4. 下界構成の強化： $0 < \alpha < 1$ の領域に対して、著者らは、点質量（point mass）を小さなテイルを持つ分布と比較するのではなく、一つの重いアウトカムと一様な軽いテイルを持つ分布の「テイル質量」を摂動させることに基づく下界議論を構築した。

主要な貢献と結果

1. $\alpha > 1$ に対する改善された上界：
   非整数 $\alpha > 1$ に対して、著者らは以下のクエリ複雑量を持つアルゴリズムを提示している：
   $$\tilde{O}\left( \frac{n^{\max\{1/2, 1-1/\alpha\}}}{\epsilon} \right)$$

   • $1 < \alpha < 2$ の場合、複雑量は $\tilde{O}(\sqrt{n}/\epsilon)$ である。
   • $\alpha > 2$ の場合、複雑量は $\tilde{O}(n^{1-1/\alpha}/\epsilon)$ である。
     これは、第1項の $n$ の指数を下げることで Wang et al. [19] の最良の既知の境界を改善し、全 $\alpha > 1$ 領域にわたって $1/\epsilon$ に対する線形依存性を達成している。$1 < \alpha < 2$ において、次元の指数は、劣多項式因子を除いて既知の量子下界と一致する。

2. $0 < \alpha < 1$ に対する改善された上界：
   $0 < \alpha < 1$ の場合、著者らは以下のクエリ複雑量を達成している：
   $$\tilde{O}\left( \frac{n^{1/(2\alpha)}}{\epsilon^{\max\{1, 1/(2\alpha)\}}} \right)$$

   • $0 < \alpha \le 1/2$ の場合、複雑量は $\tilde{O}((n/\epsilon)^{1/(2\alpha)})$ である。
   • $1/2 \le \alpha < 1$ の場合、複雑量は $\tilde{O}(n^{1/(2\alpha)}/\epsilon)$ である。
     この結果は、$n$ への依存性を増やすことなく、現在の最良の境界（2つの以前の境界の最小値）と比較して $1/\epsilon$ への依存性を改善している。

3. $0 < \alpha < 1$ に対する強化された下界：
   著者らは $0 < \alpha < 1$ に対する新しいクエリ下界を証明している：
   $$\Omega\left( n^{\frac{1}{2\alpha} - o(1)} + \frac{n^{\frac{1}{2\alpha} - \frac{1}{2}}}{\epsilon^{\max\{1, 1/(2\alpha)\}}} \right)$$
   これは、Chen, Wang, and Zhang [23] による従来の精度依存項を強化している。この新しい下界を彼らの上界と組み合わせることで、著者らは、彼らのアルゴリズムが（対数因子を除いて）$0 < \alpha < 1$ において最適な精度依存性を達成していることを示している。

意義
本論文は、特に分布のサイズ $n$ と精度 $\epsilon$ の間のトレードオフに関して、レニー・エントロピー推定の量子クエリ複雑性に関する未解決の問いを解決したと主張している。マルチレベル・フレームワークをレニー・エントロピー特有の相対精度要件に適応させ、異なる $\alpha$ 領域に対してカスタマイズされた初期状態を導入することで、よりタイトな上界を確立している。さらに、$0 < \alpha < 1$ に対する強化された下界は、彼らのアルゴリズムが精度依存性において最適であることを裏付けており、これらのパラメータにおける量子推定の根本的な限界を特定している。本研究は、バイアス低減と統計的ゆらぎが量子汎関数推定において果たす異なる役割を浮き彫りにし、非整数レニー・エントロピーに対するコヒーレント・アクセスの優位性を明確にしている。