論文の概要: The fixed angle conjecture for QAOA on regular MaxCut graphs
- arxiv url: http://arxiv.org/abs/2107.00677v2
- Date: Mon, 19 Jul 2021 17:20:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-23 20:33:30.611356
- Title: The fixed angle conjecture for QAOA on regular MaxCut graphs
- Title（参考訳）: 正規MaxCutグラフ上のQAOAの固定角度予想
- Authors: Jonathan Wurtz and Danylo Lykov
- Abstract要約: 固定角予想の数値的な証拠を$p12$で提供する。
これらの固定角はQAOAの最適化のないバージョンであり、任意の3つの正規グラフに対して普遍的に優れた性能を持つ。
グラフアンサンブル上の固定角予想に対するヒューリスティックな証拠が示され、これはこれらの固定角が大域的最適に近いことを示唆している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a near-term
combinatorial optimization algorithm suitable for noisy quantum devices.
However, little is known about performance guarantees for $p>2$. A recent work
\cite{Wurtz_guarantee} computing MaxCut performance guarantees for 3-regular
graphs conjectures that any $d$-regular graph evaluated at particular fixed
angles has an approximation ratio greater than some worst-case guarantee. In
this work, we provide numerical evidence for this fixed angle conjecture for
$p<12$. We compute and provide these angles via numerical optimization and
tensor networks. These fixed angles serve for an optimization-free version of
QAOA, and have universally good performance on any 3 regular graph. Heuristic
evidence is presented for the fixed angle conjecture on graph ensembles, which
suggests that these fixed angles are ``close" to global optimum. Under the
fixed angle conjecture, QAOA has a larger performance guarantee than the
Goemans Williamson algorithm on 3-regular graphs for $p\geq 11$.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、雑音量子デバイスに適した短期組合せ最適化アルゴリズムである。
しかし、$p>2$のパフォーマンス保証についてはほとんど知られていない。
三次元正則グラフに対するmaxcut性能保証を計算する最近の研究である \cite{wurtz_guarantee} は、特定の固定角度で評価された任意の$d$正則グラフは、最悪の場合の保証よりも近似比が大きいことを予想している。
本研究では、この固定角予想の数値的な証拠を$p<12$で提供する。
これらの角度を数値最適化とテンソルネットワークを用いて計算し,提供する。
これらの固定角はQAOAの最適化のないバージョンであり、任意の3つの正規グラフに対して普遍的に優れた性能を持つ。
グラフアンサンブル上の固定角予想に対するヒューリスティックな証拠が示され、これはこれらの固定角が大域的最適値に対して ``close' であることを示している。
固定角予想の下では、QAOA は 3 つの正則グラフ上の Goemans Williamson アルゴリズムよりも高い性能を保証する。
関連論文リスト
- Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
本稿では,新しいQAOAアンサッツについて述べる。
我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
論文 参考訳（メタデータ） (2024-11-07T22:20:01Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - 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) - 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) - 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) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - 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) - MAXCUT QAOA performance guarantees for p >1 [0.0]
均一な3つの正則グラフ上でMAXCUTに対する$p=2$および$$QAOAの最悪のケース性能保証を得る。
最悪のケースグラフはサイクルを持たない$leq 2p+1$である。
論文 参考訳（メタデータ） (2020-10-21T18:00:12Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳（メタデータ） (2020-05-18T14:23:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。