論文の概要: Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit
- arxiv url: http://arxiv.org/abs/2110.10685v1
- Date: Wed, 20 Oct 2021 17:58:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-10 23:51:51.864679
- Title: Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit
- Title（参考訳）: 無限大極限からのMAX-CUTの量子近似最適化アルゴリズムの予測パラメータ
- Authors: Sami Boulebnane and Ashley Montanaro
- Abstract要約: 推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
- 参考スコア（独自算出の注目度）: 0.05076419064097732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization is regarded as a potentially promising application
of near and long-term quantum computers. The best-known heuristic quantum
algorithm for combinatorial optimization on gate-based devices, the Quantum
Approximate Optimization Algorithm (QAOA), has been the subject of many
theoretical and empirical studies. Unfortunately, its application to specific
combinatorial optimization problems poses several difficulties: among these,
few performance guarantees are known, and the variational nature of the
algorithm makes it necessary to classically optimize a number of parameters. In
this work, we partially address these issues for a specific combinatorial
optimization problem: diluted spin models, with MAX-CUT as a notable special
case. Specifically, generalizing the analysis of the Sherrington-Kirkpatrick
model by Farhi et al., we establish an explicit algorithm to evaluate the
performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected
degree $d$ for an arbitrary constant number of layers $p$ and as the problem
size tends to infinity. This analysis yields an explicit mapping between QAOA
parameters for MAX-CUT on Erdos-Renyi graphs of expected degree $d$, in the
limit $d \to \infty$, and the Sherrington-Kirkpatrick model, and gives good
QAOA variational parameters for MAX-CUT applied to Erdos-Renyi graphs. We then
partially generalize the latter analysis to graphs with a degree distribution
rather than a single degree $d$, and finally to diluted spin-models with
$D$-body interactions ($D \geq 3$). We validate our results with numerical
experiments suggesting they may have a larger reach than rigorously
established; among other things, our algorithms provided good initial, if not
nearly optimal, variational parameters for very small problem instances where
the infinite-size limit assumption is clearly violated.
- Abstract（参考訳）: 組合せ最適化は、近長期の量子コンピュータの潜在的に有望な応用と見なされている。
ゲート型デバイスにおける組合せ最適化のための最もよく知られたヒューリスティック量子アルゴリズム、量子近似最適化アルゴリズム(qaoa)は、多くの理論および経験的研究の対象となっている。
残念なことに、特定の組合せ最適化問題へのその適用にはいくつかの困難が伴う。そのうち、性能保証はほとんど知られておらず、アルゴリズムの変動特性は、古典的に多くのパラメータを最適化する必要がある。
本研究では,これらの問題を,特殊ケースとしてMAX-CUTを用いた希釈スピンモデルという,特定の組合せ最適化問題に対して部分的に解決する。
具体的には、Farhiらによるシェリントン・カークパトリックモデルの解析を一般化し、期待次数$d$のランダムエルドス・レーニグラフに適用されたMAX-CUT上のQAOAの性能を評価するための明示的なアルゴリズムを確立する。
この解析により、予想次数$d$のエルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的な写像が得られ、エルドス・レーニグラフに適用されたMAX-CUTのQAOA変動パラメータが与えられる。
次に、後者の分析を1次$d$ではなく次数分布のグラフに部分的に一般化し、最終的にD$ボディ相互作用を持つ希釈スピンモデル(D \geq 3$)に一般化する。
提案アルゴリズムは,無限大の極限仮定が明確に破られるような非常に小さな問題の場合に対して,最適ではないとしても,最適な初期値,変分パラメータを提供する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - 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 Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Similarity-Based Parameter Transferability in the Quantum Approximate
Optimization Algorithm [2.985148456817082]
特定の値に関する最適なQAOAパラメータのクラスタリングを示す。
異なるQAOAインスタンス間のパラメータの転送性がうまく説明できる。
近似比が等しい大きなアクセプタグラフに対して、最適ドナーグラフQAOAパラメータをほぼ最適パラメータとして使用できることを示す。
論文 参考訳（メタデータ） (2023-07-11T16:35:49Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
論文 参考訳（メタデータ） (2022-04-21T17:40:39Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Parameters Fixing Strategy for Quantum Approximate Optimization
Algorithm [0.0]
そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。
我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
論文 参考訳（メタデータ） (2021-08-11T15:44:16Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。