論文の概要: Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs

• arxiv url: http://arxiv.org/abs/2504.11120v1
• Date: Tue, 15 Apr 2025 12:08:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-16 22:06:28.886655
• Title: Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
• Title（参考訳）: 一般・三角形自由・二部グラフ上の量子マックス・カット問題に対する近似比の改善
• Authors: Sander Gribling, Lennart Sinjorgo, Renata Sotirov,
• Abstract要約: QMC(Quantum Max-Cut)問題は、特定の2n倍の2n$行列の最大の固有値を決定することである。 現在知られている一般グラフのQMC近似アルゴリズムについて,より精密な解析を行う。 三角形自由グラフと二部グラフ上のQMC問題に対する2つの新しい近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.9374652839580183
• License:
• Abstract: We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes.
• Abstract（参考訳）: 本稿では,QMC問題に対する多項式時間近似アルゴリズムについて検討する。 n 頂点上の辺重み付きグラフ $G$ が与えられたとき、QMC の問題は、$G$ に対応する特定の 2^n \times 2^n$ 行列の最大の固有値を決定することである。 現在知られている一般グラフのQMC近似アルゴリズムについて,より精密な解析を行う。 このアルゴリズムは0.599$の近似比を達成し、分析により0.603$に改善した。 さらに、三角形自由グラフと二部グラフのQMC問題に対する2つの新しい近似アルゴリズムを提案し、それぞれ0.61383$と0.8162$の近似比を得る。 これらはそれぞれのグラフクラスに対する最もよく知られた近似比である。

関連論文リスト

• Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms [1.2622634782102324]
  我々はQAOA入力問題グラフをより小さな問題に分解するアルゴリズムを開発し、削減グラフ上でQAOAを用いてMaxCutを解く。 量子量子コンピュータH1-1上で1層QAOA回路を動作させることにより、10個の100頂点グラフに対する最適解を測定することができる。
  論文  参考訳（メタデータ） (2023-06-01T09:44:17Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• An explicit vector algorithm for high-girth MaxCut [0.0]
  すべての$d geq 3$と$k geq 4$に対して、我々の近似保証は著者に知られている他の古典的および量子的アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2021-08-27T19:47:56Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• 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)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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