論文の概要: Quantum Speedups for Log-Concave Sampling from Local Structure

• arxiv url: http://arxiv.org/abs/2609.20253v1
• Date: Fri, 14 Aug 2026 07:46:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 16:32:15.685995
• Title: Quantum Speedups for Log-Concave Sampling from Local Structure
• Title（参考訳）: 局所構造からのログコンケーブサンプリングのための量子スピードアップ
• Abstract要約: 本稿では,$widetildeO(sqrtd)$ローカルクエリを用いて,強い対数対数サンプリングを行う量子アルゴリズムを提案する。 我々の量子サンプリングは、統計計算や機械学習から局所的に構造化されたモデルの幅広いクラスに適用できる。
• 参考スコア（独自算出の注目度）: 12.276617184875
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For a convex function $f \colon \mathbb{R}^d \to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ is called log-concave sampling. In many practical scenarios, the function $f(x)$ turns out to admit a local decomposition $f(x) = \sum_{a=1}^R ψ_a(x_{S_a})$. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause $ψ_a(\cdot)$, which can be computationally much cheaper than the queries to $f(x)$ itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using $\widetilde{O}(\sqrtκd)$ local queries, where $κ$ is the condition number. This improves the prior best classical result $\widetilde{O}(κd)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{O}(\sqrtκ d^2)$ implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.
• Abstract（参考訳）: 凸函数 $f \colon \mathbb{R}^d \to \mathbb{R}$ に対して、$e^{-f(x)}$ に比例する分布からサンプリングする問題は、対数凹サンプリング(log-concave sample)と呼ばれる。 多くの現実的なシナリオにおいて、関数 $f(x)$ は局所分解 $f(x) = \sum_{a=1}^R >_a(x_{S_a})$ を許容する。 本稿では,局所クエリを用いたログコンケーブサンプリング,すなわち,各節に対する評価および勾配クエリを,$f(x)$自体よりも計算的にはるかに安価に行うことを検討する。 各座標が少数の節にしか現れない場合、$\widetilde{O}(\sqrtκd)$ local query を用いて強い対数のサンプリングを行う量子アルゴリズムが存在し、$κ$ は条件数である。 これにより、Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) による以前の最高の古典的な結果 $\widetilde{O}(κd)$ と、Childs et al (NeurIPS 2022) による量子結果 $\widetilde{O}(\sqrtκ d^2)$ が改善される。 我々の量子サンプリングは、統計計算や機械学習から、ガウス確率場、有限要素ラテントガウスモデル、スパース一般化線形モデルなど、幅広い局所構造モデルに適用される。 これらの結果は、局所構造は単に実装の詳細ではなく、高次元サンプリングのための量子アルゴリズム資源であることを示している。

関連論文リスト

• Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility [0.0]
  正規化されたガウス確率ベクトルの正確なシミュレーションのための量子アルゴリズムを提案する。 ファイナンシャル・アプリケーションによって動機付けられ、エンド・ツー・エンドのリソース分析を提供する。
  論文  参考訳（メタデータ） (2026-04-24T11:29:09Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。 広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
  論文  参考訳（メタデータ） (2025-02-10T06:54:16Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
  我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。 凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
  論文  参考訳（メタデータ） (2020-10-07T01:43:07Z)

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

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