論文の概要: Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs

• arxiv url: http://arxiv.org/abs/2101.05513v2
• Date: Thu, 15 Apr 2021 05:08:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-15 05:25:42.464466
• Title: Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Title（参考訳）: 局所古典MAX-CUTアルゴリズムは高次正規グラフ上で$p=2$QAOAを上回る
• Authors: Kunal Marwaha
• Abstract要約: すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。 任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The $p$-stage Quantum Approximate Optimization Algorithm (QAOA$_p$) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond $p=1$. We analyze QAOA$_2$ for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any $D$-regular graph of girth $> 5$ (i.e. without triangles, squares, or pentagons). We show that for all degrees $D \ge 2$ and every $D$-regular graph $G$ of girth $> 5$, QAOA$_2$ has a larger expected cut fraction than QAOA$_1$ on $G$. However, we also show that there exists a $2$-local randomized classical algorithm $A$ such that $A$ has a larger expected cut fraction than QAOA$_2$ on all $G$. This supports our conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (QAOA$_p$) は、ノイズの多い中間スケール量子 (NISQ) デバイスに対する組合せ最適化のための有望な手法であるが、その理論的挙動は$p=1$を超えてはよく理解されていない。 最大カット問題 (最大カット) に対してqaoa$_2$を分析し, 5$ (三角形, 正方形, 五角形なし) の任意の$d$-正則グラフ上で, 期待されるカット分数に対するグラフサイズ非依存表現を導出する。 すべての次数$D \ge 2$とすべての$D$-正則グラフ$G$ of girth $> 5$に対して、QAOA$_2$はQAOA$_1$ on $G$よりも大きなカット率を持つことを示す。 しかし、我々はまた、$a$がすべての$g$に対してqaoa$_2$よりも大きなカット率を持つように、ローカルなランダム化古典的アルゴリズムである$a$があることも示している。 これは、全ての定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在するという予想を支持する。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。 我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
  論文  参考訳（メタデータ） (2022-12-29T19:26:12Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• 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)
• 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)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。 任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。 我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
  論文  参考訳（メタデータ） (2021-10-27T06:35:59Z)
• An explicit vector algorithm for high-girth MaxCut [0.0]
  すべての$d geq 3$と$k geq 4$に対して、我々の近似保証は著者に知られている他の古典的および量子的アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2021-08-27T19:47:56Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。 1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
  論文  参考訳（メタデータ） (2021-06-10T16:28:23Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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