論文の概要: Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation

• arxiv url: http://arxiv.org/abs/2509.03496v1
• Date: Wed, 03 Sep 2025 17:25:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 21:40:46.609602
• Title: Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
• Title（参考訳）: 最適量子タリスエントロピー推定によるモノミアル近似のための情報理論下界
• Authors: Qisheng Wang,
• Abstract要約: 本稿では,エントロピー推定のための量子アルゴリズムによる情報理論から近似理論への概念的新しい接続を明らかにする。 情報理論的下界$Omega(sqrtn)$を単項$xn$の近似次数で提供し、ニューマンやリヴリンで示される解析的下界と比較する。 これは全てのパラメータに対して最適なクエリ複雑性(多対数因子まで)を持つ最初の量子エントロピー推定器である。
• 参考スコア（独自算出の注目度）: 13.491187998442596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper reveals a conceptually new connection from information theory to approximation theory via quantum algorithms for entropy estimation. Specifically, we provide an information-theoretic lower bound $\Omega(\sqrt{n})$ on the approximate degree of the monomial $x^n$, compared to the analytic lower bounds shown in Newman and Rivlin (Aequ. Math. 1976) via Fourier analysis and in Sachdeva and Vishnoi (Found. Trends Theor. Comput. Sci. 2014) via the Markov brothers' inequality. This is done by relating the polynomial approximation of monomials to quantum Tsallis entropy estimation. This further implies a quantum algorithm that estimates to within additive error $\varepsilon$ the Tsallis entropy of integer order $q \geq 2$ of an unknown probability distribution $p$ or an unknown quantum state $\rho$, using $\widetilde \Theta(\frac{1}{\sqrt{q}\varepsilon})$ queries to the quantum oracle that produces a sample from $p$ or prepares a copy of $\rho$, improving the prior best $O(\frac{1}{\varepsilon})$ via the Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki and Kwek (Phys. Rev. Lett. 2002). To the best of our knowledge, this is the first quantum entropy estimator with optimal query complexity (up to polylogarithmic factors) for all parameters simultaneously.
• Abstract（参考訳）: 本稿では,エントロピー推定のための量子アルゴリズムによる情報理論から近似理論への概念的新しい接続を明らかにする。 具体的には、ニューマンとリヴリン(1976年)のフーリエ解析およびザックデヴァとヴィシュノイ(2014年トレンド理論の創始者)による解析的下界と比較して、単項$x^n$の近似次数での情報理論的下界$\Omega(\sqrt{n})$を提供する。 これは、モノミアルの多項式近似を量子的ツァリスエントロピー推定に関連付けて行われる。 さらに、加算誤差 $\varepsilon$ の Tsallis entropy of a unknown probability distribution $p$ または未知の量子状態 $\rho$, using $\widetilde \Theta(\frac{1}{\sqrt{q}\varepsilon})$ 量子オラクルへのクエリは、$p$ からサンプルを生成するか、または$\rho$ のコピーを準備し、前のベストである $O(\frac{1}{\varepsilon})$ を、Ekert, Alves, Oi, Horodecki, Horodecki, Kwek (Phys. Rev. Lett. 2002) によるShift testによって改善する。 我々の知る限りでは、これは全てのパラメータに対して最適なクエリ複雑性(多対数因子まで)を持つ最初の量子エントロピー推定器である。

関連論文リスト

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms [0.0]
  我々は,$O(mboxlog(frac1delta)/epsilon)を$epsilon,deltarightarrow 0arrowとして新しいサンプル複雑性上限を求める。 一般学習の場合、学習速度の量子スピードアップは、$epsilon-1$の2乗である。
  論文  参考訳（メタデータ） (2023-10-24T07:39:16Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• 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)
• Sublinear quantum algorithms for estimating von Neumann entropy [18.30551855632791]
  我々は、確率分布のシャノンエントロピーと混合量子状態のフォン・ノイマンエントロピーの乗法係数$gamma>1$における推定値を得る問題を研究する。 我々は古典的確率分布と混合量子状態の両方を扱える量子純粋クエリーアクセスモデルに取り組んでおり、文献の中では最も一般的な入力モデルである。
  論文  参考訳（メタデータ） (2021-11-22T12:00:45Z)

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

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