論文の概要: Testing APS conjecture on regular graphs
- arxiv url: http://arxiv.org/abs/2507.10050v1
- Date: Mon, 14 Jul 2025 08:31:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-15 18:48:24.559267
- Title: Testing APS conjecture on regular graphs
- Title（参考訳）: 正規グラフ上のAPS予想のテスト
- Authors: Wenxuan Tao, Fen Zuo,
- Abstract要約: 近年、Apte, Parekh and Sud(APS) は MWFM を最大重量マッチング (MWM) に置き換えることで境界を補強できると推測している。
ここではこの予想を、ヘニングとヨーが何年も前に構築した特別な正則グラフのクラスで検証する。
ヘニングヨーグラフ上のEPRモデルにFEDアルゴリズムを適用することで、可能な限り高いエネルギーと一致した値が得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The maximum energy of the EPR model on a weighted graph is known to be upper-bounded by the sum of the total weight and the value of maximum-weight fractional matching~(MWFM). Recently, Apte, Parekh and Sud~(APS) conjecture that the bound could be strengthened by replacing MWFM with maximum weight matching~(MWM). Here we test this conjecture on a special class of regular graphs that Henning and Yeo constructed many years ago. On this class of regular graphs, MWMs achieve tight lower bounds. As for the maximum energy of the EPR model, we have recently devised a new algorithm called Fractional Entanglement Distribution~(FED) based on quasi-homogeneous fractional matchings, which could achieve rather high accuracy. Applying the FED algorithm to the EPR model on Henning-Yeo graphs, we could thus obtain energy as high as possible and matching value as low as possible, and then make high-precision tests of the APS conjecture. Nevertheless, our numerical results do not show any evidence that the APS conjecture could be violated.
- Abstract（参考訳）: 重み付きグラフ上のEPRモデルの最大エネルギーは、全重みの和と最大重み付き分数マッチング~(MWFM)の値によって上界であることが知られている。
近年、Apte, Parekh and Sud~(APS) は MWFM を最大重量マッチング~(MWM)に置き換えることで境界を補強できると予想している。
ここではこの予想を、ヘニングとヨーが何年も前に構築した特別な正則グラフのクラスで検証する。
この正規グラフのクラスでは、MWMは厳密な下界を達成する。
EPRモデルの最大エネルギーについて、我々は最近、準均質な分数マッチングに基づくフラクショナルエンタングルメント分布~(FED)と呼ばれる新しいアルゴリズムを考案した。
ヘニングヨーグラフ上のEPRモデルにFEDアルゴリズムを適用することで、可能な限り高いエネルギーと一致した値を得ることができ、それからAPS予想の高精度なテストを行うことができる。
それでも、我々の数値結果は、APS予想が破られるという証拠を示さない。
関連論文リスト
- A Refined Algorithm For the EPR model [0.0]
2つのグループは、近似比$frac1+sqrt54approx.809$の高エネルギー状態の特定のアルゴリズムを独立に開発している。
ここでは、等質/準同質な分数マッチングを考案することにより、2つのアルゴリズムのうちの1つを洗練しようと試みる。
不規則グラフの場合、分数マッチングが適切に選択されていれば、そのような改善が良好な性能を保証できることが示される。
論文 参考訳（メタデータ） (2025-06-10T08:12:14Z) - A Unified Analysis for Finite Weight Averaging [50.75116992029417]
Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。
本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
論文 参考訳（メタデータ） (2024-11-20T10:08:22Z) - Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality [40.215737469808026]
ハイパーグラフはグループ関係を研究するときに現れ、機械学習の分野で広く使われている。
ハイパーグラフの統一的な定式化は行われていないが、最近提案されたエッジ依存レイリー重み付け(EDVW)モデリングは、ハイパーグラフの最も一般化されたモデリング手法の1つである。
グラフ上の対応する定義と整合性を持つハイパーグラフQuotient, NCut, boundary/cut, volume, and conductance の定義を提案する。
そして、正規化されたハイパーグラフラプラシアンがNCut値と関連があることを証明し、スペクトルクラスタリングのためのHyperClus-Gアルゴリズムを刺激する。
論文 参考訳（メタデータ） (2024-10-23T05:16:48Z) - Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs [26.8902894372334]
量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。
加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。
我々は、よく知られた古典的局所アルゴリズムとQAOAを一定の深さで比較するために数値実験を行う。
論文 参考訳（メタデータ） (2024-10-06T08:57:30Z) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳（メタデータ） (2024-08-23T16:35:47Z) - Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文 参考訳（メタデータ） (2024-06-20T18:00:02Z) - EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
人口のログライクな独特な非自明な点は、その大域的な最大点であることを示す。
予測最大化アルゴリズムは、単一の潜在変数の場合に収束することが保証される。
論文 参考訳（メタデータ） (2022-11-21T23:12:58Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
本論文は,最適化が容易なjmmdの統一形式を理論的に導出する。
統合JMMDから、JMMDは分類に有利な特徴ラベル依存を低下させることを示す。
本稿では,その依存を促進する新たなmmd行列を提案し,ラベル分布シフトにロバストな新しいラベルカーネルを考案する。
論文 参考訳（メタデータ） (2021-01-25T09:46:14Z) - Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。
問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。
我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
論文 参考訳（メタデータ） (2020-06-18T17:18:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。