論文の概要: Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
- arxiv url: http://arxiv.org/abs/2607.07540v1
- Date: Wed, 08 Jul 2026 15:38:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-09 22:50:30.441446
- Title: Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
- Title（参考訳）: 量子論法による高次関数の最小値推定に向けて
- Abstract要約: 本稿では,量子コンピューティングの観点から,高次関数の最小値推定に対する新しいアプローチを提案する。
我々の推定子は、量子プリミティブを用いて統一されたフレームワークで構築され、量子コンピュータ上で実行される。
- 参考スコア（独自算出の注目度）: 13.491187998442596
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number $α\gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_α(P) = \sum_{i=1}^S p_i^α$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)$ of a mixed state $ρ$. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal $L_2$ rate $α\mathsf{n}^{-1}$ in the range $α\lesssim \mathsf{n} \lesssim α^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $ρ$ can be much larger than the number of samples $\mathsf{n}$. As a result, both estimators achieve the \textit{optimal} sample complexity $\mathsf{n} \asymp α$, improving upon the prior best upper bounds $O(α^2)$ established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.
- Abstract（参考訳）: 本稿では,量子コンピューティングの観点から,高次関数の最小値推定に対する新しいアプローチを提案する。
具体的には、任意の実数 $α\gg 1$ に対して、古典函数 $\mathrm{F}_α(P) = \sum_{i=1}^S p_i^α$ を離散分布 $P$ とし、量子函数 $\mathrm{F}_α(ρ) = \operatorname{tr}(ρ^α)$ を混合状態 $ρ$ とする。
これらの函数は、レニイエントロピーやツァリスエントロピーと密接な関係を持つ。
両推定器は、最小最大値$L_2$ rate$α\mathsf{n}^{-1}$を、サポートサイズ$S$の$P$または$ρ$の次元がサンプル数$\mathsf{n}$よりもはるかに大きい範囲$α\lesssim \mathsf{n} \lesssim α^{3-o(1)}$とすることを示す。
結果として、両方の推定子は、古典汎函数に対して、Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) によって確立された前の最高の上限である$O(α^2)$を改善し、量子汎函数に対して Chen と Wang (COLT 2025) を改良して、 \textit{optimal} サンプル複雑性 $\mathsf{n} \asymp α$ を達成する。
我々の推定子は、量子プリミティブを用いて統一されたフレームワークで構築され、量子コンピュータ上で線形時間で実行される。
この研究は、量子コンピューティングから統計への予期せぬ経路を明らかにし、関数的推定のための概念的に新しい方法論を提案する。
これは古典定理の量子証明の増大リストに加えられる。
関連論文リスト
- Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。
離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
論文 参考訳（メタデータ） (2026-05-05T12:25:17Z) - On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。
格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。
$d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
論文 参考訳（メタデータ） (2026-04-27T10:23:24Z) - Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation [13.491187998442596]
本稿では,エントロピー推定のための量子アルゴリズムによる情報理論から近似理論への概念的新しい接続を明らかにする。
情報理論的下界$Omega(sqrtn)$を単項$xn$の近似次数で提供し、ニューマンやリヴリンで示される解析的下界と比較する。
これは全てのパラメータに対して最適なクエリ複雑性(多対数因子まで)を持つ最初の量子エントロピー推定器である。
論文 参考訳（メタデータ） (2025-09-03T17:25:28Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Maximal intrinsic randomness of a quantum state [1.0470286407954037]
量子情報科学は、過去10年間に固有の、または秘密の量子ランダム性の研究で大きく進歩してきた。
この問題は、条件最小エントロピー、条件フォン・ノイマンエントロピー、条件最大エントロピーの3つの異なるランダム性定量化器に答える。
条件付きフォン・ノイマンエントロピーの場合、最大値は$H*= log_2d-S(rho)$, with $S(rho)$ フォン・ノイマンエントロピーは$rho$、条件付き最大エントロピーでは$となる。
論文 参考訳（メタデータ） (2023-07-28T17:58:13Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-26T03:19:40Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。