論文の概要: Improved Quantum Algorithms for Rényi Entropies Estimation

• arxiv url: http://arxiv.org/abs/2610.19936v1
• Date: Wed, 14 Oct 2026 10:21:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.100423
• Title: Improved Quantum Algorithms for Rényi Entropies Estimation
• Title（参考訳）: Rényiエントロピー推定のための量子アルゴリズムの改良
• Abstract要約: 任意の分布に対して Rényi entropy $H_(mathbfp)$ を推定する問題を考察する。 我々のアルゴリズムは$H_(mathbfp)$を$widetildemathcalObig(nmax1/2,1-1//big)$クエリだけで追加エラー$$で見積もっている。
• 参考スコア（独自算出の注目度）: 3.8743350688734988
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating Rényi entropy $H_α(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access. For non-integer $α> 1$, our algorithm estimates $H_α(\mathbf{p})$ to within additive error $ε$ using only $\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)$ queries, which improves the best known upper bound for dependence on both $n$ and $1/ε$. For $0<α<1$, our algorithm has query complexity $\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)$, which improves the dependence on $1/ε$ of the current best upper bound without incresing its $n$ dependence. Our approach adapts the multi-level estimation framework to relative approximation of the power sums and leverage binary search to remove the requirement of prior knowledge of them. We also strengthen the precision-dependent lower bound to $Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)$ for $0<α<1$, which identifies the optimal precision dependence of our algorithm.
• Abstract（参考訳）: 離散確率分布のエントロピー推定は、統計的推測と量子特性推定の基本的な問題である。 本稿では,Rényi entropy $H_α(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given the purified quantum query- access。 非整数$α> 1$の場合、我々のアルゴリズムは$H_α(\mathbf{p})$を$\widetilde{\mathcal{O}}\big(n^{\max\{1/2,1-1/α\}}/ε\big)$クエリだけで追加エラー$ε$に見積もる。 0<α<1$の場合、我々のアルゴリズムはクエリ複雑性$\widetilde{\mathcal{O}}\big(n^{1/(2α)}/ε^{\max\{1,1/(2α)\}}\big)$を持ち、$n$依存を増すことなく現在の最高の上限の$/ε$への依存を改善する。 提案手法は,電力和の相対近似に多段階推定フレームワークを適用し,二進探索を利用して事前知識の要求を除去する。 また、精度依存下界を$Ω\big(1/ε^{\max\{1,1/(2α)\}}\big)$ for $0<α<1$とすると、アルゴリズムの最適精度依存性が分かる。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• A Simple Algorithm for Best Separable State [5.5559749120901385]
  本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
  論文  参考訳（メタデータ） (2026-08-10T19:04:15Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。 離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
  論文  参考訳（メタデータ） (2026-05-05T12:25:17Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
  離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。 我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
  論文  参考訳（メタデータ） (2022-12-03T08:01:55Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。