論文の概要: Provable Quantum--Classical Separation for Continuous Gibbs Sampling

• arxiv url: http://arxiv.org/abs/2608.24527v1
• Date: Tue, 25 Aug 2026 13:13:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:34.993731
• Title: Provable Quantum--Classical Separation for Continuous Gibbs Sampling
• Title（参考訳）: 連続ギブズサンプリングのための確率量子-古典的分離
• Abstract要約: 連続領域上のサンプリング問題に対する最初の量子-古典的分離を証明した。 古典的境界は情報理論であり、任意の順序でギブスポテンシャルとその微分へのクエリアクセスを持つ全ての古典的アルゴリズムを保持できる。
• 参考スコア（独自算出の注目度）: 2.2476214822407994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the first quantum--classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-βE}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $α=e^{βΔ}$, where $Δ= \max E-\min E$, every classical algorithm---querying the value, gradient, or any higher-order derivatives of the log-density---requires $Ω(α)$ queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with $\tilde{O}\left(\sqrtα\right)$ queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, $e^{Ω(d)}$, at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.
• Abstract（参考訳）: 連続領域上のサンプリング問題に対する最初の量子-古典的分離を証明した。 a class of Gibbs states $p\propto e^{-βE}$ on the torus $\mathbb{T}^d$ with smooth $s$-Gevrey) potential and barrier amplitude $α=e^{βΔ}$, where $Δ= \max E-\min E$, every classical algorithm--querying the value, gradient, or any higher-order derivatives of the log-density--requires $Ω(α)$ query to sample at constant accuracy in total variation distance, while a quantum algorithm based on a quantum singular value thresholding and temperature annealing sample with $\tilde{O}\left(\sqrtα\right)$ query to an oracle for the gradient。 アドバンテージは障壁振幅において二次的であり、低温では次元が指数関数的に$e^{Ω(d)}$となる。 古典的境界は情報理論であり、任意の順序でギブスポテンシャルとその微分へのクエリアクセスを持つ全ての古典的アルゴリズムを保持できる。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation [0.5097809301149342]
  我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。 我々は、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。
  論文  参考訳（メタデータ） (2025-02-06T18:32:26Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits [1.6328866317851185]
  量子位相推定の単一制御量子ビット変種は、系の固有状態を準備できない場合にも、ハイゼンベルク極限を達成することができることを示す。 本稿では,行列鉛筆法を用いてハイゼンベルク限定スケーリングを実現できることを示す。
  論文  参考訳（メタデータ） (2021-07-09T18:00:10Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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