論文の概要: Algorithms and Sum-of-Squares Certificates for Qudit Hamiltonians Over Maximally Entangles States

• arxiv url: http://arxiv.org/abs/2410.15544v1
• Date: Mon, 21 Oct 2024 00:10:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:18:02.021090
• Title: Algorithms and Sum-of-Squares Certificates for Qudit Hamiltonians Over Maximally Entangles States
• Title（参考訳）: 極大エンタングル状態上のクイット・ハミルトンのアルゴリズムと正方形証明
• Authors: Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, Stuart Wayland,
• Abstract要約: 最大エンタングルメント問題の基底状態エネルギーを証明し、エンタングルメント境界のモノガミーを証明する。 単純なマッチングに基づくアルゴリズムは、一般グラフの基底状態エネルギーの少なくとも1/d$のエネルギーを出力する。
• 参考スコア（独自算出の注目度）: 37.96754147111215
• License:
• Abstract: We introduce the Maximal Entanglement problem, a 2-local qudit Hamiltonian that we view as a quantum generalization of Unique Games and which naturally encodes the frustration present in entanglement over multiple systems. We prove monogamy of entanglement bounds by certifying the ground state energy of the Maximal Entanglement problem in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, while a random assignment achieves energy of at least $1/d^2$ times the ground state energy, we show that a simple matching-based algorithm outputs a state with energy at least $1/d$ of the ground state energy for general graphs and at least $1/d + \Theta(1/D)$ for graphs with bounded degree, $D$. Moreover, we show that this state has energy at least $1/2$ of the ground state energy on $D$-regular graphs with degree, $D \leq 5$, for any local dimension, $d$.
• Abstract（参考訳）: 最大エンタングルメント問題(英: Maximal Entanglement problem)とは、2-局所クディット・ハミルトン問題であり、ユニクティックゲームの量子一般化と見なし、複数のシステムにまたがる絡み合いに存在するフラストレーションを自然にエンコードする問題である。 最大絡み合い問題の基底状態エネルギーを低次和の証明によって基礎となる相互作用グラフの最大整合性の観点から証明することにより、絡み合い境界のモノガミーを証明する。 アルゴリズム的には、ランダム代入は基底状態エネルギーの少なくとも1/d^2$のエネルギーを達成するが、単純なマッチングベースのアルゴリズムは、一般グラフに対する基底状態エネルギーの少なくとも1/d$と、有界グラフに対する少なくとも1/d + \Theta(1/D)$のエネルギーを出力する。 さらに、この状態は、次数$D$正則グラフ上の基底状態エネルギーの少なくとも1/2$、任意の局所次元$D$に対して$D \leq 5$であることを示す。

関連論文リスト

• 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)

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

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