論文の概要: Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA

• arxiv url: http://arxiv.org/abs/2411.05216v1
• Date: Thu, 07 Nov 2024 22:20:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 14:53:51.870448
• Title: Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA
• Title（参考訳）: 問題ハミルトニアンにおけるファントムエッジ:QAOAのパフォーマンス向上とグラフ可視性
• Authors: Quinn Langfitt, Reuben Tate, Stephan Eidenbenz,
• Abstract要約: 本稿では,新しいQAOAアンサッツについて述べる。 我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm designed to solve combinatorial optimization problems. However, a key limitation of QAOA is that it is a "local algorithm," meaning it can only optimize over local properties of the graph for finite circuit depths. In this work, we present a new QAOA ansatz that introduces only one additional parameter to the standard ansatz, regardless of system size, allowing QAOA to "see" more of the graph at a given depth $p$. We achieve this by modifying the target graph to include additional $\alpha$-weighted edges, with $\alpha$ serving as a tunable parameter. This modified graph is then used to construct the phase operator and allows QAOA to explore a wider range of the graph's features for a smaller $p$. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs. We also provide numerical experiments that demonstrate significant improvements in the approximation ratio for the Max-Cut problem over the standard QAOA ansatz for $p=1$ and $p=2$ on random regular graphs up to 16 nodes.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題を解決するために設計された変分量子アルゴリズムである。 しかし、QAOAの鍵となる制限は、これは「局所アルゴリズム」であり、有限回路深さに対してグラフの局所特性を最適化することしかできないことである。 本研究では, システムサイズに関わらず, 標準アンサッツに1つの追加パラメータのみを導入する新たなQAOAアンサッツを提案する。 これを実現するために、ターゲットグラフを変更して、$\alpha$-weighted edgeを追加し、$\alpha$-weighted edgeをチューニング可能なパラメータとして提供する。 この修正されたグラフは位相演算子を構成するために使用され、QAOAはより広い範囲のグラフの特徴をより小さな$p$で探索することができる。 我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。 また、16ノードまでのランダム正規グラフ上では、標準的なQAOAアンサッツに対して$p=1$と$p=2$に対してMax-Cut問題に対する近似比を大幅に改善する数値実験を行った。

関連論文リスト

• Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs [26.8902894372334]
  量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。 本稿では、加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。
  論文  参考訳（メタデータ） (2024-10-06T08:57:30Z)
• Improved Recursive QAOA for Solving MAX-CUT on Bipartite Graphs [4.364124102844566]
  両部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。 レベル1再帰QAOA(RQAOA)を用いて同じ問題を解く数値結果を通して示す。 本稿では,QAOAに最適化されたパラメータ構造を削減したRQAOAを提案する。
  論文  参考訳（メタデータ） (2024-08-23T16:35:47Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  ランダム正則グラフ上での最大カットと最大独立集合問題を考える。 高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。 両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
  論文  参考訳（メタデータ） (2024-06-20T18:00:02Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。 QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。 この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
  論文  参考訳（メタデータ） (2023-02-09T07:47:06Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• 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)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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