論文の概要: MAXCUT QAOA performance guarantees for p >1

• arxiv url: http://arxiv.org/abs/2010.11209v2
• Date: Tue, 2 Feb 2021 21:25:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-28 03:01:13.051668
• Title: MAXCUT QAOA performance guarantees for p >1
• Title（参考訳）: maxcut qaoa による p > 1 のパフォーマンス保証
• Authors: Jonathan Wurtz, Peter J. Love
• Abstract要約: 均一な3つの正則グラフ上でMAXCUTに対する$p=2$および$$QAOAの最悪のケース性能保証を得る。 最悪のケースグラフはサイクルを持たない$leq 2p+1$である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of $0.692$ for $p=1$. We find a lower bound of $0.7559$ for $p=2$, where worst case graphs are those with no cycles $\leq 5$. This bound holds for any 3 regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $\leq 2p+1$. Under this conjecture, the approximation ratio is at least $0.7924$ for all 3 regular graphs and $p=3$. In addition, using a simple indistinguishability argument we find an upper bound on the worst case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.
• Abstract（参考訳）: 均一な3つの正則グラフ上でMAXCUTに対する$p=2$および$$QAOAの最悪のケース性能保証を得る。 Farhiらによる以前の研究は、近似比が0.692$ for $p=1$の低い境界を得た。 0.7559$ for $p=2$で、最悪のケースグラフはサイクルのないグラフである。 この境界は、特定の固定パラメータで評価された任意の3つの正規グラフに対して成り立つ。 最悪のケースグラフがサイクルを持たないすべての$p$に対して$\leq 2p+1$を予想する。 この予想の下で、近似比は3つの正則グラフすべてに対して少なくとも$0.7924$であり、$p=3$である。 さらに、単純な区別不可能な議論を用いて、すべての$p$に対する最悪のケース近似比の上限を見つけ、これは少なくとも$p<6$に対して量子的優位性を持たないグラフのクラスを示す。

関連論文リスト

• Extremal Maximal Entanglement [12.189398760348018]
  n$=$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$6$のときだけ、絶対的に極端に絡み合った状態が存在する。 どの$n-qubit純状態が最大混合の$lfloor n/2 rfloor-party還元数を持つのか?
  論文  参考訳（メタデータ） (2024-11-19T03:56:34Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Repeated Averages on Graphs [2.363388546004777]
  我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。 また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
  論文  参考訳（メタデータ） (2022-05-09T20:18:31Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• The fixed angle conjecture for QAOA on regular MaxCut graphs [0.0]
  固定角予想の数値的な証拠を$p12$で提供する。 これらの固定角はQAOAの最適化のないバージョンであり、任意の3つの正規グラフに対して普遍的に優れた性能を持つ。 グラフアンサンブル上の固定角予想に対するヒューリスティックな証拠が示され、これはこれらの固定角が大域的最適に近いことを示唆している。
  論文  参考訳（メタデータ） (2021-07-01T18:02:36Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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