論文の概要: Near optimal quantum algorithm for estimating Shannon entropy
- arxiv url: http://arxiv.org/abs/2509.07452v1
- Date: Tue, 09 Sep 2025 07:24:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-10 14:38:27.202397
- Title: Near optimal quantum algorithm for estimating Shannon entropy
- Title（参考訳）: シャノンエントロピー推定のための近似量子アルゴリズム
- Authors: Myeongjin Shin, Kabgyun Jeong,
- Abstract要約: 我々は、量子確率オラクルモデルにおけるシャノンエントロピーを推定するために、対数係数まで、ほぼ最適の量子アルゴリズムを提案する。
以上の結果から,Shannonエントロピーを$epsilon$-additiveエラーで推定する際の厳密なクエリ複雑性は,$tildeThetaleft(tfracsqrtnepsilonright)$で与えられることがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a near-optimal quantum algorithm, up to logarithmic factors, for estimating the Shannon entropy in the quantum probability oracle model. Our approach combines the singular value separation algorithm with quantum amplitude amplification, followed by the application of quantum singular value transformation. On the lower bound side, we construct probability distributions encoded via Hamming weights in the oracle, establishing a tight query lower bound up to logarithmic factors. Consequently, our results show that the tight query complexity for estimating the Shannon entropy within $\epsilon$-additive error is given by $\tilde{\Theta}\left(\tfrac{\sqrt{n}}{\epsilon}\right)$.
- Abstract（参考訳）: 我々は、量子確率オラクルモデルにおけるシャノンエントロピーを推定するために、対数係数まで、ほぼ最適の量子アルゴリズムを提案する。
本手法では, 特異値分離アルゴリズムと量子振幅増幅法を併用し, 量子特異値変換を適用する。
下界側では、オラクルのハミング重みによって符号化された確率分布を構築し、対数的要因までの厳密な問合せを確立する。
その結果,シャノンエントロピーを$\epsilon$-additive errorで推定するクエリの複雑さは$\tilde{\Theta}\left(\tfrac{\sqrt{n}}{\epsilon}\right)$で与えられることがわかった。
関連論文リスト
- Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
パウリ分解において、与えられたハミルトニアンに対する量子状態準備のエネルギーを推定する問題を考える。
状態の実際の分散を用いた適応推定器を構築する。
論文 参考訳（メタデータ） (2025-02-03T19:00:01Z) - Semidefinite optimization of the quantum relative entropy of channels [3.9134031118910264]
本稿では,チャネルの量子相対エントロピーを計算する方法を提案する。
これは、任意の所望の精度で真の値をサンドイッチする効率的な計算可能な上界と下界を提供する。
論文 参考訳（メタデータ） (2024-10-21T18:00:01Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Algorithmic Cluster Expansions for Quantum Problems [0.0]
計算問題のクラスに対して近似アルゴリズムを開発するための一般的な枠組みを確立する。
我々は,その同一性に近い量子回路の確率振幅を近似するために,我々の枠組みを適用した。
我々のアルゴリズム条件は期待値に対してほぼ最適であり、ゼロ自由度という意味での熱予測値に対して最適であることを示す。
論文 参考訳（メタデータ） (2023-06-15T09:11:48Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。
我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
論文 参考訳（メタデータ） (2021-11-01T16:35:41Z) - Quantum Sub-Gaussian Mean Estimator [0.0]
実数値確率変数の平均を推定する新しい量子アルゴリズムを提案する。
我々の推定器は古典的なi.d.サンプルの数に対して、ほぼ最適2次高速化を達成する。
論文 参考訳（メタデータ） (2021-08-27T08:34:26Z) - Bosonic field digitization for quantum computers [62.997667081978825]
我々は、離散化された場振幅ベースで格子ボゾン場の表現に対処する。
本稿では,エラースケーリングを予測し,効率的な量子ビット実装戦略を提案する。
論文 参考訳（メタデータ） (2021-08-24T15:30:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。