論文の概要: Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

• arxiv url: http://arxiv.org/abs/2605.14994v1
• Date: Thu, 14 May 2026 15:56:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-16 00:43:04.132178
• Title: Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
• Title（参考訳）: 菊池グラフの固有値に関するシャープ境界と量子最大カットへの応用
• Authors: Ainesh Bakshi, Arpon Basu, Pravesh Kothari, Anqi Li,
• Abstract要約: レベル$k$菊池グラフのラプラシアンの最大固有値が$m$エッジを持つ任意のグラフ$G$は、最大$m+k$であることを示す。 また、ブローワー予想を緩やかに前進させ、グラフラプラシアンのトップ-$k$固有値の和上のルーの有界性を改善する。
• 参考スコア（独自算出の注目度）: 4.812727079006245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.
• Abstract（参考訳）: 我々は、レベル$k$菊池グラフの(符号付きおよび符号なしの)ラプラシアンの最大固有値が、任意のグラフ$G$と$m$エッジの任意のグラフ$m+k$であることを示す。 これは、Apte、Parekh、Sudの4つの最近の予想を裏付ける。 応用として、1および2つの量子ビット積状態のテンソル積は、量子マックスカットに対して5/8ドル、XYハミルトニアンに対して5/7ドルという近似比が得られる。 さらに、Apte、Parekh、Sudによって分析されたアルゴリズムと組み合わせることで、量子マックスカットの近似比が0.614ドル、XYハミルトニアンの0.674ドルとなる効率的なアルゴリズムが得られる。 最後に、ブローワー予想を緩やかに前進させ、グラフラプラシアンの上位k$固有値の和上のルーの有界性を改善する。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• A Lovász theta lower bound on Quantum Max Cut [2.0305676256390934]
  我々は、グラフの量子マックスカットへの下界を、その補体のロヴシュ・テータ函数の観点から証明する。 境界は量子マックスカットに適用されたときの古典的境界よりも優れる。
  論文  参考訳（メタデータ） (2025-12-23T12:53:40Z)
• Quantum Max-Cut is NP hard to approximate [0.06768558752130309]
  我々は、定数有界グラフ上の QUANTUM MAX-CUT 問題に対する定数乗法近似を計算するのがNPハードであることを証明する。
  論文  参考訳（メタデータ） (2025-10-09T09:32:08Z)
• Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs [0.9374652839580183]
  QMC(Quantum Max-Cut)問題は、特定の2n倍の2n$行列の最大の固有値を決定することである。 現在知られている一般グラフのQMC近似アルゴリズムについて,より精密な解析を行う。 三角形自由グラフと二部グラフ上のQMC問題に対する2つの新しい近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-15T12:08:07Z)
• Improved approximation algorithms for the EPR Hamiltonian [0.0]
  EPRハミルトニアン(EPR Hamiltonian)は、キングによって導入された2局所量子ハミルトニアン(arXiv:2202589)の族である。 EPRハミルトニアンの基底エネルギーを計算するための時間$frac1+sqrt54$-approximationアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-04-14T21:08:40Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings [0.7366405857677227]
  ランダムウォークに基づく埋め込み手法の理論解析を行う。 いくつかの弱い仮定の下では、コーポラはランダムウォークの個数の極限$N to infty$と、ランダムウォークの2つの極限$N$と各ランダムウォークの長さ$Ltoinfty$の両方に収束する。
  論文  参考訳（メタデータ） (2021-07-21T11:23:04Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)

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

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