Fugu-MT 論文翻訳(概要): Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs

論文の概要: Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs

arxiv url: http://arxiv.org/abs/2410.04409v1
Date: Sun, 6 Oct 2024 08:57:30 GMT
ステータス: 処理完了
システム内更新日: 2024-11-02 08:00:46.489223
Title: Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs
Title（参考訳）: 低次グラフ上での最大カットのための量子近似最適化アルゴリズム
Authors: Tongyang Li, Yuexin Su, Ziyi Yang, Shengyu Zhang,
Abstract要約: 量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。本稿では、加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。
参考スコア（独自算出の注目度）: 26.8902894372334
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.
Abstract（参考訳）: グラフ上の最大カット(MaxCut)は古典的なNPハード問題である。量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。カット分数(全エッジの出力カットのエッジの分数)に対する保証は、主に長い周期しか持たないグラフに対して研究された。一方、低木グラフは理論計算機科学においてユビキタスであり、拡張グラフは理論上およびそれ以上に広く応用された優れた例である。本稿では、加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。さらに,多角QAOA (ma-QAOA) を用いて,加算積グラフのグラフ構造をよりよく活用する。理論的には、そのようなグラフの期待切断率を計算するための反復公式を導出する。一方,古典的局所アルゴリズムとQAOAを一定深度で比較するため,数値実験を行った。以上の結果から,QAOAはいくつかの付加積グラフで0.3%から5.2%,ma-QAOAは0.6%から2.5%でこの優位性を高めた。特に,ma-QAOAはよく知られた古典的アルゴリズムよりも優れているが,QAOAはそうではない。さらに、我々は実験をタイリンググリッドグラフのような平面グラフに拡張し、QAOAが有利であることを示す。

関連論文リスト

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)
Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文参考訳（メタデータ） (2024-08-23T16:35:47Z)
Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文参考訳（メタデータ） (2023-10-26T16:19:24Z)
Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文参考訳（メタデータ） (2023-02-08T08:17:43Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Impact of Graph Structures for QAOA on MaxCut [0.2609784101826761]
量子近似最適化アルゴリズム(QAOA)は、量子コンピューティングを用いて最適化問題を解くための有望な方法である。我々は、すべての連結非同型グラフに対するMaxCut問題において、少なくとも3つの深さでのQAOAの性能を評価する。構造と性能の関係を知ることで、量子的優位性を示す可能性のある問題のクラスを特定できる。
論文参考訳（メタデータ） (2021-02-11T13:32:00Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)
Dirichlet Graph Variational Autoencoder [65.94744123832338]
本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
論文参考訳（メタデータ） (2020-10-09T07:35:26Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)
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)
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
論文参考訳（メタデータ） (2020-04-20T00:48:02Z)

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

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