論文の概要: Polynomial-Time Approximation of Zero-Free Partition Functions
- arxiv url: http://arxiv.org/abs/2201.12772v1
- Date: Sun, 30 Jan 2022 09:54:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 07:20:08.685672
- Title: Polynomial-Time Approximation of Zero-Free Partition Functions
- Title（参考訳）: ゼロ自由分割関数の多項式時間近似
- Authors: Penghui Yao, Yitong Yin, Xinyuan Zhang
- Abstract要約: 局所ハミルトニアンによって定義された古典的および量子的分割関数を推定するためのアルゴリズム時間アルゴリズムを提案する。
この結果はPaterとRegtsのアプローチを拡張し、一般化する新しい抽象的なフレームワークに基づいています。
- 参考スコア（独自算出の注目度）: 9.153066211741356
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Zero-free based algorithm is a major technique for deterministic approximate
counting. In Barvinok's original framework[Bar17], by calculating truncated
Taylor expansions, a quasi-polynomial time algorithm was given for estimating
zero-free partition functions. Patel and Regts[PR17] later gave a refinement of
Barvinok's framework, which gave a polynomial-time algorithm for a class of
zero-free graph polynomials that can be expressed as counting induced subgraphs
in bounded-degree graphs.
In this paper, we give a polynomial-time algorithm for estimating classical
and quantum partition functions specified by local Hamiltonians with bounded
maximum degree, assuming a zero-free property for the temperature.
Consequently, when the inverse temperature is close enough to zero by a
constant gap, we have polynomial-time approximation algorithm for all such
partition functions. Our result is based on a new abstract framework that
extends and generalizes the approach of Patel and Regts.
- Abstract（参考訳）: ゼロフリーベースアルゴリズムは決定論的近似カウントの主要な手法である。
Barvinok のオリジナルのフレームワーク[Bar17] では、ゼロ自由分割関数を推定するために準多項式時間アルゴリズムが与えられた。
patel と regts[pr17] は後に barvinok のフレームワークを改良し、有界次グラフにおける誘導部分グラフの数え上げとして表現できるゼロフリーグラフ多項式のクラスに対して多項式時間アルゴリズムを与えた。
本稿では,局所ハミルトニアンが有界最大次数で指定する古典的および量子的分割関数を,温度のゼロフリー特性を仮定して推定する多項式時間アルゴリズムを提案する。
したがって、逆温度が一定間隔でゼロに近づくと、そのようなすべての分割関数に対する多項式時間近似アルゴリズムが得られる。
この結果はPaterとRegtsのアプローチを拡張し、一般化する新しい抽象的なフレームワークに基づいています。
関連論文リスト
- Private graphon estimation via sum-of-squares [10.00024942014117]
ブロックモデルを学習し,任意のブロックに対して一定の実行時間でグラフトン推定を行うための,最初の純粋ノード微分プライベートアルゴリズムを開発した。
統計的ユーティリティは、これらの問題に対する以前の最良の情報理論(指数時間)ノードプライドメカニズムのそれと一致することを保証している。
論文 参考訳（メタデータ） (2024-03-18T19:54:59Z) - Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。
我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
論文 参考訳（メタデータ） (2023-12-14T09:53:54Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。
数値実験では, 既存の再起動バージョンよりも改善が見られた。
論文 参考訳（メタデータ） (2021-08-10T07:15:07Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - A quantum version of Pollard's Rho of which Shor's Algorithm is a
particular case [0.0]
ポラードのRhoは整数分解問題の解法である。
ポラードのRhoはショアのアルゴリズムの一般化であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:11:37Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。
問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。
我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文 参考訳（メタデータ） (2020-06-18T17:18:02Z) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。