論文の概要: Breaking the Multiplicative Overhead in Quantum Entropy Estimation

• arxiv url: http://arxiv.org/abs/2609.40179v1
• Date: Wed, 30 Sep 2026 17:04:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.126081
• Title: Breaking the Multiplicative Overhead in Quantum Entropy Estimation
• Title（参考訳）: 量子エントロピー推定における乗法オーバーヘッドの破れ
• Abstract要約: Von Neumann, Tsallis, and Rényi entropies は量子情報の基本的な測度である。 一般的な推定戦略は、スペクトル変換と統計的読み出しの最悪のコストを乗じて、下位境界の問合せにギャップを残している。 局所正規化と精度割当を用いるマルチレベルアルゴリズムを用いる一方、可変時間推定は高価なスペクトルテストに到達する確率を考慮に入れている。
• 参考スコア（独自算出の注目度）: 16.869656377471564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error $\varepsilon$, rank upper bound $R$, and fixed order $α$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(α-1)})$ for $1<α<2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\widetilde O(1/\varepsilon)$ for $α\ge2$, where $\widetilde O$ suppresses logarithmic factors. The first saves a factor $1/\varepsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\widetilde O(R/\varepsilon^2)$ to $\widetilde O(R/\varepsilon)$ and obtain $\widetilde O(R/\varepsilon)$ for noninteger Rényi orders $1<α<3$, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using $\widetilde O(R/\varepsilon)$ queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.
• Abstract（参考訳）: フォン・ノイマン、ツァリス、レナイエントロピーは量子情報の基本的な測度である。 一般的な推定戦略は、スペクトル変換と統計的読み出しの最悪のコストを乗じて、下位境界の問合せにギャップを残している。 このオーバヘッドを局所正規化と精度割当を用いたマルチレベルアルゴリズムで削減する一方、可変時間推定は高価なスペクトルテストに到達する確率を考慮に入れている。 制御されたアクセスとその逆で、加算誤差 $\varepsilon$, rank upper bound $R$, fixed order $α$ のバウンダリを得る。 Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(α-1)})$ for $1<α<2$, the possible dimension and rankallow the lower-bound instance, $\widetilde O(1/\varepsilon)$ for $α\ge2$, where $\widetilde O$ can suppresss logarithmic factors。 第1は1/\varepsilon$を保存し、第2は既知の整数階数スケーリングを非整数階数に拡張する。 我々はまた、フォン・ノイマンエントロピー境界を$\widetilde O(R/\varepsilon^2)$から$\widetilde O(R/\varepsilon)$に改善し、非整数 Rényi に対して$\widetilde O(R/\varepsilon)$ を得る。 我々の関数推定定理は、関数の大きさとスペクトル質量によって重み付けられた局所的なコストの和によって、大域的な積を置き換える。 さらに、$\widetilde O(R/\varepsilon)$クエリを用いて、固定対数モーメントとエントロピーの分散を推定し、有限ブロック長量子圧縮と純粋状態エンタングルメント変換に入る変動パラメータへの効率的なアクセスを提供する。 より広範に、我々のフレームワークはエントロピーを超えて密度行列関数の幅広いクラスに拡張し、量子スペクトル推定における最適なクエリ複雑性への体系的なアプローチを提供する。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers [0.0]
  量子線形システム解法は、量子コンピューティングにおいて中心となるアルゴリズムプリミティブの1つを形成する。 $と$varepsilonへの依存はすでによく理解されています。 スパースアクセスモデルにおいて、完全関節下界$(sqrts)$を証明します。
  論文  参考訳（メタデータ） (2026-09-18T18:02:04Z)
• 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)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。 離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
  論文  参考訳（メタデータ） (2026-05-05T12:25:17Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Asymptotically Optimal Quantum Amplitude Estimation by Generalized Qubitization [5.0755851789013535]
  まず、標準値が約1.28 L-1$で、$L$はクエリの数であることを示す。 次に、複数の関数を同時にブロックエンコードできる一般化量子化法を提案し、量子振幅を推定して最適な精度を達成する方法を示す。
  論文  参考訳（メタデータ） (2023-06-29T05:31:52Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)

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

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