論文の概要: Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies
- arxiv url: http://arxiv.org/abs/2608.18070v1
- Date: Tue, 18 Aug 2026 17:56:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.437254
- Title: Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies
- Title（参考訳）: 量子レニイとツァリスエントロピーのサンプル最適推定器
- Abstract要約: 我々は、ほぼ最適なサンプル複雑性を持つ量子レニイとツァリスのエントロピーを推定する。
0$の場合、サンプル複雑性は、Rényiエントロピーが$O(d1+1//varepsilon1/ + d1/-1/varepsilon2)、Tsallisエントロピーが$O(d1+1//varepsilon1/)である。
- 参考スコア（独自算出の注目度）: 14.968127458030251
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we provide estimators for quantum Rényi and Tsallis entropies with nearly optimal sample complexity. Specifically, for order $α$, dimension $d$, and additive error $\varepsilon$, 1. For $0 < α< 1$, the sample complexity is $O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})$ for Rényi entropy and $O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)$ for Tsallis entropy. In particular, for $0 < α\leq 1/2$, the sample complexity for both entropies is $O(d^{1+1/α}/\varepsilon^{1/α})$. 2. For non-integer $α> 1$, the sample complexity is $O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)$ for Rényi entropy. Our upper bounds improve the quantum Rényi entropy estimators due to Acharya, Issa, Shende, and Wagner (2017) and the quantum Tsallis entropy estimators due to Chen, Liu, and Wang (2026), and match the lower bounds recently established by Wang (2026).
- Abstract（参考訳）: 本稿では,量子レニイとツァリスエントロピーをほぼ最適なサンプル複雑性で推定する。
具体的には、次数$α$, dimension $d$, and additive error $\varepsilon$, 1. for $0 < α< 1$, the sample complexity is $O(d^{1+1/α}/\varepsilon^{1/α} + d^{1/α-1}/\varepsilon^{2})$ for Rényi entropy and $O(d^{1+1/α}/\varepsilon^{1/α} + d^{2-2α}/\varepsilon^2)$ for Tsallis entropyである。
特に、$0 < α\leq 1/2$の場合、両方のエントロピーのサンプル複雑性は$O(d^{1+1/α}/\varepsilon^{1/α})$である。
2. 非整数 $α> 1$ の場合、サンプル複雑性は $O(d^2/\varepsilon^{1/α} + d^{1-1/α}/\varepsilon^2)$ である。
我々の上界は、Acharya, Issa, Shende, and Wagner (2017) による量子Rényiエントロピー推定器と、Chen, Liu, and Wang (2026) による量子Tsallisエントロピー推定器を改善し、Wang (2026) によって最近確立された下界と一致する。
関連論文リスト
- Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。
定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
論文 参考訳（メタデータ） (2026-07-18T21:01:38Z) - Computational hardness of estimating quantum entropies via binary entropy bounds [0.2538209532048867]
量子$-Rényi entropy $rm Stt T_q()$を推定する際の計算困難さについて検討する。
すべての正の位数に対して、ランク-$2$の変種が Rank2RényiQEA$_$ と Rank2TsallisQEA$_q$ は $sf BQP$-hard であることを示す。
我々の結果は、異なる順序の$-Rényiあるいは$q$-Tsallis二項エントロピーに関する新しい不等式に基づく還元に由来する。
論文 参考訳（メタデータ） (2026-01-07T09:25:07Z) - Inverse-free quantum state estimation with Heisenberg scaling [4.191671741497842]
ハイゼンベルクスケーリングを実現する逆フリーな純粋量子状態推定プロトコルを提案する。
この結果から,逆自由振幅推定のためのクエリ上界$O(mind3/2/varepsilon,1/varepsilon2)$が示唆された。
論文 参考訳（メタデータ） (2025-10-29T17:48:46Z) - Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation [13.491187998442596]
本稿では,エントロピー推定のための量子アルゴリズムによる情報理論から近似理論への概念的新しい接続を明らかにする。
情報理論的下界$Omega(sqrtn)$を単項$xn$の近似次数で提供し、ニューマンやリヴリンで示される解析的下界と比較する。
これは全てのパラメータに対して最適なクエリ複雑性(多対数因子まで)を持つ最初の量子エントロピー推定器である。
論文 参考訳（メタデータ） (2025-09-03T17:25:28Z) - Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
上界と下界の両方で$operatornametr(rhoq)$を推定することで、サンプルの複雑さを大幅に改善する。
我々の上界は、弱いシュアサンプリングに基づく(プラグインでない)量子推定器によって得られる。
論文 参考訳（メタデータ） (2025-05-14T17:06:33Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。
また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
論文 参考訳（メタデータ） (2024-06-01T07:03:40Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。
これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
論文 参考訳（メタデータ） (2022-05-19T18:51:28Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。