論文の概要: Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

• arxiv url: http://arxiv.org/abs/2410.15544v2
• Date: Mon, 11 Nov 2024 06:47:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 14:04:14.215797
• Title: Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians
• Title（参考訳）: 量子ハミルトニアンに対する絡み合い境界のモノガミーと近似アルゴリズムの改良
• Authors: Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, Stuart Wayland,
• Abstract要約: 我々は、局所項のないランク1プロジェクターの2-局所キュディト・ハミルトン多様体に対するエンタングルメント境界の新しいモノガミーを証明した。 基礎となる相互作用グラフの最大整合性の観点から、低次2乗法証明を用いて基底状態エネルギーを認証する。
• 参考スコア（独自算出の注目度）: 37.96754147111215
• License:
• Abstract: We prove new monogamy of entanglement bounds for 2-local qudit Hamiltonian of rank-one projectors without local terms. In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, we show that a simple matching-based algorithm approximates the ground state energy to at least $1/d$ for general graphs and to at least $1/d + \Theta(1/D)$ for graphs with bounded degree, $D$. This outperforms random assignment, which, in expectation, achieves energy of only $1/d^2$ of the ground state energy for general graphs. Notably, on $D$-regular graphs with degree, $D \leq 5$, and for any local dimension, $d$, we show that this simple matching-based algorithm has an approximation guarantee of $1/2$. Lastly, when $d=2$, we present an algorithm achieving an approximation guarantee of $0.595$, beating that of [PT22, arXiv:2206.08342] (which gave a tight approximation guarantee of $1/2$).
• Abstract（参考訳）: 我々は、局所項のないランク1プロジェクターの2-局所キュディト・ハミルトン多様体に対するエンタングルメント境界の新しいモノガミーを証明する。 特に、基礎となる相互作用グラフの最大整合性の観点から、低次二乗の和証明を用いて基底状態エネルギーを認証する。 アルゴリズムにより、単純なマッチングベースのアルゴリズムは、基底状態エネルギーを、一般グラフに対して少なくとも1/d$、有界グラフに対して少なくとも1/d + \Theta(1/D)$に近似することを示した。 これはランダムな割り当てよりも優れており、予想通り、一般グラフの基底状態エネルギーの1/d^2$のエネルギーしか得られない。 特に、$D$正規グラフにおいて次数$D \leq 5$、任意の局所次元$d$に対して、この単純なマッチングベースのアルゴリズムが1/2$の近似保証を持つことを示す。 最後に、$d=2$のとき、[PT22, arXiv:2206.08342]の近似保証を0.595$のアルゴリズムで達成し、[PT22, arXiv:2206.08342]の近似を保証する。

関連論文リスト

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。 正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
  論文  参考訳（メタデータ） (2023-07-02T05:03:38Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。 重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-02T05:26:10Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Improved approximation algorithms for bounded-degree local Hamiltonians [12.961180148172197]
  与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。 結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
  論文  参考訳（メタデータ） (2021-05-03T22:23:47Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。 任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
  論文  参考訳（メタデータ） (2021-01-14T09:17:20Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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