論文の概要: Quantum Multi-Level Estimation of Functionals of Discrete Distributions
- arxiv url: http://arxiv.org/abs/2605.03685v1
- Date: Tue, 05 May 2026 12:25:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-06 19:35:43.929495
- Title: Quantum Multi-Level Estimation of Functionals of Discrete Distributions
- Title（参考訳）: 離散分布関数の量子マルチレベル推定
- Authors: Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang,
- Abstract要約: 離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。
離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
- 参考スコア（独自算出の注目度）: 23.53427184324404
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a quantum multi-level estimation framework for a functional $\sum_{i=1}^n f(p_i)$ of a discrete distribution $(p_i)_{i=1}^n$. We partition the values $p_i$ into logarithmically many intervals whose length decays exponentially. For each interval, we perform non-destructive singular value discrimination to isolate the relevant $p_i$, enabling adaptive estimation of the partial sum over this interval. Unlike previous variable-time approaches, our method avoids high control overhead and requires only constant extra ancilla qubits. As an application, we present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions. Specifically: (i) For $q > 1$, we obtain a near-optimal quantum algorithm with query complexity $\tildeΘ(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$, improving the prior best $O(1/\varepsilon^{1+1/(q-1)})$ due to Liu and Wang (SODA 2025; IEEE Trans. Inf. Theory 2026). (ii) For $0 < q < 1$, we obtain a quantum algorithm with query complexity $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$, exhibiting a quantum speedup over the near-optimal classical estimators due to Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017). Our results achieve, to our knowledge, the first near-optimal quantum estimators for parameterized $q$-entropy for non-integer $q$.
- Abstract（参考訳）: 離散分布 $(p_i)_{i=1}^n$ の関数 $\sum_{i=1}^n f(p_i)$ に対する量子多値推定フレームワークを提案する。
値 $p_i$ を対数的に長さが指数関数的に減衰する多くの区間に分割する。
各区間において、関連する$p_i$を分離するために非破壊特異値判別を行い、この区間で部分和を適応的に推定することができる。
従来の可変時間アプローチとは異なり、制御オーバーヘッドが高く、一定の余分なアンシラ量子ビットしか必要としない。
応用として、離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
具体的には
(i)$q > 1$ の場合、クエリ複雑性を持つ準最適量子アルゴリズムを$\tildee(1/\varepsilon^{\max\{1/(2(q-1)), 1\}})$ とし、Liu と Wang (SODA 2025; IEEE Trans. Inf. Theory 2026; IEEE Trans. Inf. Theory 2026) により以前の最高値である$O(1/\varepsilon^{1+1/(q-1)} を改善する。
(ii)$0 < q < 1$ に対して、クエリ複雑性を持つ量子アルゴリズム $\tilde{O}(n^{1/q-1/2}/\varepsilon^{1/q})$ を得る。
我々の知識では、非整数$q$に対するパラメータ化$q$-エントロピーに対する最初の近似量子推定器が達成される。
関連論文リスト
- Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。
我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
論文 参考訳（メタデータ） (2024-01-18T12:50:20Z) - 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) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。