論文の概要: An (almost) efficient classical algorithm for sampling from typical Gibbs states

• arxiv url: http://arxiv.org/abs/2609.40250v2
• Date: Mon, 05 Oct 2026 17:27:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.48284
• Title: An (almost) efficient classical algorithm for sampling from typical Gibbs states
• Title（参考訳）: 典型的なギブス状態からのサンプリングのための(ほぼ)効率的な古典的アルゴリズム
• Abstract要約: 我々は、量子$p$-spinモデルとして知られる局所システムのアンサンブルに対するギブスサンプリングにおいて指数的な量子優位性を示す。 我々のアルゴリズムはアルゴリズムローカライゼーション(ASL)として知られるメタアルゴリズムに基づいている。 次に、関連するモデルの局所的な期待値を計算するために、既知の準多項式時間アルゴリズムを拡張して、量子$p$-spinモデルに対してこれらの「タイトな手段」を計算する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
• Abstract（参考訳）: ギブス状態の準備は、物理系の研究において量子優位のための潜在的な道として現れた。 最悪ケースギブス状態の局所特性を計算する利点は知られているが、最近の研究では、平均ケースローカルシステムでは異なる図が示されている: ギブス状態が量子的に効率的に準備できる温度では、準多項式時間アルゴリズムも局所期待値を計算することができる。 しかし、このことは、より強力なシミュレーションの概念であるサンプリングの利点の可能性を秘めている。 ギブスサンプリングはボルツマンマシンベースの量子学習アルゴリズムと量子超越性の提案を基礎としているが、物理関連モデルの古典的な平均ケースの複雑さは未解決のままである。 ここでは、量子$p$スピンモデルとして知られる局所系のアンサンブルに対するギブスサンプリングにおいて指数的量子優位性に対する強い証拠を与える。 本稿では,ギブス状態から全変動距離における任意の多項式誤差までをサンプリングする古典的アルゴリズムについて述べる。 アルゴリズムはアルゴリズム確率局在 (ASL) と呼ばれるメタアルゴリズムに基づいている。 我々の主な技術的結果は ASL の一般化収束定理であり、これはハイパーキューブ上の任意の分布からの近似サンプリングを減らし、関連する「タイル分布」の平均を十分に低い加算誤差に推定するものである。 次に、関連する乱れモデルの局所的な期待値を計算するための既知の準多項式時間アルゴリズムを拡張して、量子$p$-spinモデルのこれらの「タイル付き手段」を計算する。 最後に、この平均推定アルゴリズムはスピンガラス転移温度まで作用する、という非厳密な物理論を述べる。 効率的な量子アルゴリズムもこの遷移で失敗するので、古典的アルゴリズムが(ほぼ)効率的である温度以下の温度で量子の$p$-spinモデルをサンプリングすることはできない。

関連論文リスト

• A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations [51.660331450043806]
  ギブス状態における局所観測可能量の推定は、量子シミュレーションにおける中心的な問題である。 我々は,SYK局所熱予測を十分高い温度で推定する準ポリノミカル時間古典アルゴリズムの証明を与える。 この結果は、量子多体システムに広く役立つと思われる新しいWick-pair展開をもたらす。
  論文  参考訳（メタデータ） (2026-04-22T21:14:04Z)
• Efficient Learning Implies Quantum Glassiness [0.0]
  量子学習理論とアルゴリズムの硬さの驚くべき関係を示す。 量子アルゴリズムの「Lipschitz」では,スパース乱れの量子系の近傍状態の発見が平均的に困難であることを示す。
  論文  参考訳（メタデータ） (2025-04-30T18:00:29Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
  行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。 この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
  論文  参考訳（メタデータ） (2023-10-11T18:00:53Z)
• Dissipative Quantum Gibbs Sampling [1.5845445933441118]
  単純で局所的な更新規則を持つ散逸型量子アルゴリズムは、量子ギブス状態からサンプリング可能であることを示す。 これにより、メトロポリスサンプリングの長年続く量子アナログに対する新しい答えが得られる。
  論文  参考訳（メタデータ） (2023-04-10T11:51:50Z)
• Quantum Thermal State Preparation [39.91303506884272]
  量子マスター方程式をシミュレートするための簡単な連続時間量子ギブスサンプリングを導入する。 我々は、特定の純ギブス状態を作成するための証明可能かつ効率的なアルゴリズムを構築した。 アルゴリズムのコストは温度、精度、混合時間に依存している。
  論文  参考訳（メタデータ） (2023-03-31T17:29:56Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。 偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
  論文  参考訳（メタデータ） (2022-11-07T12:00:45Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  我々は、離散化された場振幅ベースで格子ボゾン場の表現に対処する。 本稿では,エラースケーリングを予測し,効率的な量子ビット実装戦略を提案する。
  論文  参考訳（メタデータ） (2021-08-24T15:30:04Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。 変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。 量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
  論文  参考訳（メタデータ） (2021-08-09T18:00:05Z)

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

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