論文の概要: Dealing with locality in QAOA

• arxiv url: http://arxiv.org/abs/2606.14447v2
• Date: Mon, 15 Jun 2026 09:02:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 13:45:31.307768
• Title: Dealing with locality in QAOA
• Title（参考訳）: QAOAにおける地域対応
• Authors: Mithilesh Kumar, Yusuf Tahir,
• Abstract要約: 高サイズMaxCutインスタンス上の浅度QAOAは、局所性ボトルネックに直面している。 我々は、実効的な相互作用グラフの直径を崩壊させるために、正確な有限深度サポートを使用します。 ベンチマークでは(ma-QAOA性能とは違って)直径が小さくなれば効果的にサイズインとなることを示す。
• 参考スコア（独自算出の注目度）: 0.7161783472741748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shallow-depth QAOA on sparse, high-diameter MaxCut instances faces a locality bottleneck: at depth \(p\), local observables can depend only on a bounded neighborhood of the circuit interaction graph. We propose a transport-augmented QAOA that keeps the MaxCut cost Hamiltonian unchanged but enriches the mixer with optimized, unweighted shortcut couplings (scheduled \(XX+YY\)) to collapse the effective interaction-graph diameter. Using exact finite-depth support recursions, we relate optimal shortcut placement to bounded-diameter graph augmentation, and show in benchmarks that (unlike ma-QAOA) performance becomes effectively size-invariant once the diameter is reduced. For bipartite families (base diameter 4), reducing the interaction path to \(d=1\) raises the ensemble-averaged approximation ratio from 0.7378 (ma-QAOA) to 0.9767 at \(p=1\) (\(σ=0.0251\), nine system sizes); on random trees (base diameter 10), at \(p=2\) it improves from 0.9226 to 0.9997 (\(σ=0.0001\)).
• Abstract（参考訳）: スパース上の浅度QAOAは、高径のMaxCutインスタンスは、局所的なボトルネックに直面している: 深さ \(p\) では、局所観測可能は、回路相互作用グラフの有界近傍にのみ依存することができる。 我々は,MaxCut のコストを一定に抑えながら,最適化されたショートカットカップリング (スケジューリング \(XX+YY\)) でミキサーを強化し,効果的な相互作用グラフの直径を分解する輸送拡張 QAOA を提案する。 正確な有限深度サポート再帰を用いて、最適ショートカット配置と境界径グラフ拡大を関連付けるとともに、(ma-QAOAと異なり)性能が直径を小さくすると効果的にサイズ不変となることを示すベンチマークで示す。 バイパルタイト系(ベース直径4)では、相互作用経路を \(d=1\) に還元すると、アンサンブル平均近似比が 0.7378 (ma-QAOA) から 0.9767 (p=1\) (\(σ=0.0251\,9系サイズ) となり、ランダムツリー(ベース直径10)では 0.9226 から 0.9997 (\(σ=0.0001\) に改善される。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
  無限大極限におけるランダム正則グラフ上の最大カットと最大独立集合問題を考える。 我々は、QAOAが達成したエネルギー密度を、最高$d=100$で計算する。 グラフの次数が増加するにつれて,QAOAが大きな問題サイズに対して達成した近似比が向上することを示す。
  論文  参考訳（メタデータ） (2024-06-20T18:00:02Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut [2.8087801395910525]
  与えられたQAOA深度に対して、QAOAパラメータの1つの「典型的」ベクトルを、重み付きMaxCutインスタンスに転送することに成功した。 この移動は、近似比がわずか2.0ポイントの中央値の減少につながる。
  論文  参考訳（メタデータ） (2022-01-27T19:54:00Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  幾何学的中央値 (textGm) は、未破損データのロバストな推定を達成するための統計学における古典的な方法である。 本稿では,テキストscGmを一度に選択した座標ブロックにのみ適用することにより,スムーズな非テキスト問題に対して0.5の分解点を保持することができることを示す。
  論文  参考訳（メタデータ） (2021-06-16T15:55:50Z)
• 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)

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

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