論文の概要: A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy

• arxiv url: http://arxiv.org/abs/2507.09247v1
• Date: Sat, 12 Jul 2025 10:58:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:22.855316
• Title: A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy
• Title（参考訳）: CLuPアルゴリズムによる$\sim 0.76$SK-モデル基底自由エネルギーの実現
• Authors: Mihailo Stojnic,
• Abstract要約: シェリントン・カークパトリック (SK) スピングラス基底自由エネルギーのアルゴリズムによる決定について検討する。 CLuP-SKモデルに付随するアルゴリズムの典型的成功を解析する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider algorithmic determination of the $n$-dimensional Sherrington-Kirkpatrick (SK) spin glass model ground state free energy. It corresponds to a binary maximization of an indefinite quadratic form and under the \emph{worst case} principles of the classical NP complexity theory it is hard to approximate within a $\log(n)^{const.}$ factor. On the other hand, the SK's random nature allows (polynomial) spectral methods to \emph{typically} approach the optimum within a constant factor. Naturally one is left with the fundamental question: can the residual (constant) \emph{computational gap} be erased? Following the success of \emph{Controlled Loosening-up} (CLuP) algorithms in planted models, we here devise a simple practical CLuP-SK algorithmic procedure for (non-planted) SK models. To analyze the \emph{typical} success of the algorithm we associate to it (random) CLuP-SK models. Further connecting to recent random processes studies [94,97], we characterize the models and CLuP-SK algorithm via fully lifted random duality theory (fl RDT) [98]. Moreover, running the algorithm we demonstrate that its performance is in an excellent agrement with theoretical predictions. In particular, already for $n$ on the order of a few thousands CLuP-SK achieves $\sim 0.76$ ground state free energy and remarkably closely approaches theoretical $n\rightarrow\infty$ limit $\approx 0.763$. For all practical purposes, this renders computing SK model's near ground state free energy as a \emph{typically} easy problem.
• Abstract（参考訳）: 我々は,SKスピンガラスの基底状態自由エネルギーを$n$次元シェリントン・カークパトリック(英語版)で決定するアルゴリズムについて検討する。 これは不定二次形式の二項最大化に対応し、古典的なNP複雑性理論の \emph{worst case} の原理の下では、$\log(n)^{const 内で近似することは困難である。 $ factor.*。 一方、SKのランダムな性質は、(ポリノミカルな)スペクトル法が定数係数内で最適に近づくことを可能にする。 残差(定数) \emph{computational gap} を消せるか? 植木モデルにおける \emph{Controlled Loosening-up} (CLuP) アルゴリズムの成功に続いて, 簡単な実用的 CLuP-SK アルゴリズムを考案した。 アルゴリズムの成功を解析するために、CLuP-SKモデルと(ランダムに)関連付ける。 近年のランダムプロセス研究 [94,97] にさらに接続し, 完全昇降ランダム双対性理論 (fl RDT) [98] を用いてモデルとCLuP-SKアルゴリズムを特徴付ける。 さらに,提案アルゴリズムの実行により,その性能が理論的予測に優れることを示した。 特に、既に数千の順序で$n$に対して CLuP-SK は$\sim 0.76$の基底自由エネルギーを達成し、理論上の$n\rightarrow\infty$ limit $\approx 0.763$に非常に近づいた。 全ての実用目的のために、これは SK モデルの準基底自由エネルギーを \emph{typically} 簡単な問題として表す。

関連論文リスト

• Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case [3.4872784636892047]
  Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、量子最適化アルゴリズムであり、その性能は深さ$p$で単調に向上する。 無限大の極限においてSKモデルに適用されたQAOAを解析し、回路深さ$mathcalO(n/epsilon1.13)$の最適エネルギーに対して1-epsilon$の近似が得られるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2025-05-12T18:00:01Z)
• Even-Cycle Detection in the Randomized and Quantum CONGEST Model [1.5566524830295314]
  すべての$kgeq 2$に対して、$C_2k$-freenessは、CONGESTモデルで$O(n1-1/k)$ラウンドで決定できることを示す。 また、量子設定において、円複雑度$tilde O(nfrac12-frac12k)$を達成するためのアルゴリズムの量子化方法を示す。
  論文  参考訳（メタデータ） (2024-02-19T10:23:37Z)
• On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
  NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。 ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。 近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
  論文  参考訳（メタデータ） (2023-12-11T04:15:55Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。 1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
  論文  参考訳（メタデータ） (2021-06-10T16:28:23Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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