論文の概要: Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- arxiv url: http://arxiv.org/abs/2610.04987v1
- Date: Sun, 04 Oct 2026 06:15:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-11 07:20:15.859919
- Title: Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
- Title（参考訳）: 量子凸体体積推定のための上下境界の改善
- Abstract要約: 高次元凸体の体積を推定することは、理論計算機科学の基本的な問題である。
相対誤差に対して$mathrmvol(K)$を推定すると、$varepsilon$は$widetilde O(d5/2+d3/2/varepsilon)$クエリを取る。
- 参考スコア（独自算出の注目度）: 2.004129703898208
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\mathbb{R}^d$, we show that estimating $\mathrm{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al. (ACM TQC 2023) and Cornelissen--Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound $\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an $Ω(d)$ quantum query lower bound for constant relative error, improving the previous $Ω(\sqrt d)$ lower bound.
- Abstract（参考訳）: 高次元凸体の体積を推定することは、理論計算機科学の基本的な問題である。
凸体 $K\subset\mathbb{R}^d$ の量子メンバシップオラクルが与えられると、相対誤差 $\varepsilon$ が $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ のクエリを推定できることが示される。
これにより、以前の量子上界$\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al (ACM TQC 2023) と Cornelissen--Hamoudi (SODA 2023) が改善され、現在最高の古典上界$\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al (JACM 2026) よりも大きな量子スピードアップを達成する。
我々の量子アルゴリズムは、一様古典的ウォームスタート混合境界に基づく量子ウォークの入力依存効果的なスペクトルギャップ解析と、古典的橋梁サンプリングに基づく模擬焼鈍における正規化率の積の1つの量子推定器を組み合わせた。
また、定数相対誤差に対して$Ω(d)$量子クエリローバウンドを証明し、以前の$Ω(\sqrt d)$ローバウンドを改善する。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
離散分布の関数 $sum_i=1n f(p_i)$ に対する量子多値推定フレームワークを提案する。
離散分布の$q$-Tsallisエントロピーに対する効率的な量子推定器を提案する。
論文 参考訳（メタデータ） (2026-05-05T12:25:17Z) - Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes [2.7340036787711646]
我々は、$textitNesterov の反復滑らか化の行列変種が、量子零サムゲームにおいて線形速度で終点収束を達成することを証明した。
副産物として、厳密な正の半定値プログラムの並列近似のための古典的ジャイナ・ワトラス [arXiv:0808.2775] 法を指数関数的に高速化する。
論文 参考訳（メタデータ） (2025-09-25T20:51:13Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation [13.491187998442596]
本稿では,エントロピー推定のための量子アルゴリズムによる情報理論から近似理論への概念的新しい接続を明らかにする。
情報理論的下界$Omega(sqrtn)$を単項$xn$の近似次数で提供し、ニューマンやリヴリンで示される解析的下界と比較する。
これは全てのパラメータに対して最適なクエリ複雑性(多対数因子まで)を持つ最初の量子エントロピー推定器である。
論文 参考訳（メタデータ） (2025-09-03T17:25:28Z) - Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
上界と下界の両方で$operatornametr(rhoq)$を推定することで、サンプルの複雑さを大幅に改善する。
我々の上界は、弱いシュアサンプリングに基づく(プラグインでない)量子推定器によって得られる。
論文 参考訳（メタデータ） (2025-05-14T17:06:33Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。