Fugu-MT 論文翻訳(概要): Strategies for running the QAOA at hundreds of qubits

論文の概要: Strategies for running the QAOA at hundreds of qubits

arxiv url: http://arxiv.org/abs/2410.03015v1
Date: Thu, 3 Oct 2024 21:53:43 GMT
ステータス: 処理完了
システム内更新日: 2024-11-03 04:25:56.118595
Title: Strategies for running the QAOA at hundreds of qubits
Title（参考訳）: 数百量子ビットでのQAOA実行戦略
Authors: Brandon Augustino, Madelyn Cain, Edward Farhi, Swati Gupta, Sam Gutmann, Daniel Ranard, Eugene Tang, Katherine Van Kirk,
Abstract要約: 量子近似最適化アルゴリズム(QAOA)の実行に必要な計算量を削減するための戦略を検討する。インスタンスに依存しない"ツリー"パラメータを事前に選択した標準QAOAについて検討する。何百もの頂点を持つランダムな3つの正則グラフに対して、ウォームスタートQAOAの深さ$p gtrsim 3$のカットは標準GWアルゴリズムに匹敵する。
参考スコア（独自算出の注目度）: 3.2518947654884016
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, following Wurtz et al. [Phys.Rev A 104:052419], we consider the standard QAOA with instance-independent "tree" parameters chosen in advance. These tree parameters are chosen to optimize the MaxCut expectation for large girth graphs. We provide extensive numerical evidence supporting the performance guarantee for tree parameters conjectured in [Phys.Rev A 103:042612] and see that the approximation ratios obtained with tree parameters are typically well beyond the conjectured lower bounds, often comparable to performing a full optimization. This suggests that in practice, the QAOA can achieve near-optimal performance without the need for parameter optimization. Next, we modify the warm-start QAOA of Tate et al. [Quantum 7:1121]. The starting state for the QAOA is now an optimized product state associated with a solution of the Goemans-Williamson (GW) algorithm. Surprisingly, the tree parameters continue to perform well for the warm-start QAOA. We find that for random 3-regular graphs with hundreds of vertices, the expected cut obtained by the warm-start QAOA at depth $p \gtrsim 3$ is comparable to that of the standard GW algorithm. Our numerics on random instances do not provide general performance guarantees but do provide substantial evidence that there exists a regime of instance sizes in which the QAOA finds good solutions at low depth without the need for parameter optimization. For each instance studied, we classically compute the expected size of the QAOA distribution of cuts; producing the actual cuts requires running on a quantum computer.
Abstract（参考訳）: 本稿では,量子近似最適化アルゴリズム(QAOA)の実行に必要な計算量を削減するための戦略を検討する。まず、Wurtz et al [Phys.Rev A 104:052419] に従って、インスタンスに依存しない「ツリー」パラメータを事前に選択した標準QAOAを考える。これらの木パラメータは、大きなガースグラフに対するMaxCut期待を最適化するために選択される。我々は[Phys.Rev A 103:042612] で予想される木パラメータのパフォーマンス保証を裏付ける広範な数値的な証拠を提供し、木パラメータから得られる近似比が予想される下界をはるかに超え、しばしば完全な最適化に匹敵するものであることを確かめる。これは、QAOAがパラメータ最適化を必要とせずに、ほぼ最適性能を実現できることを示唆している。次に、テイトら [Quantum 7:1121] のウォームスタート QAOA を変更する。 QAOAの開始状態は現在、ゲーマン・ウィリアムソン(GW)アルゴリズムの解に付随する最適化された製品状態である。驚くべきことに、ツリーパラメータは、ウォームスタートQAOAに対して、引き続き良好に機能します。何百もの頂点を持つランダムな3つの正則グラフに対して、ウォームスタートQAOAの深さ$p \gtrsim 3$のカットは標準GWアルゴリズムに匹敵する。我々のランダムなインスタンス上の数値は、一般的な性能保証を提供していないが、QAOAがパラメータ最適化を必要とせずに、低い深さで良い解を見出すような、インスタンスのサイズの体系が存在するという実質的な証拠を提供する。研究された各インスタンスについて、古典的にはカットのQAOA分布の予測サイズを計算し、実際のカットを生成するには量子コンピュータで実行する必要がある。

関連論文リスト

Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文参考訳（メタデータ） (2024-06-20T18:00:02Z)
Parameter Setting in Quantum Approximate Optimization of Weighted Problems [10.396104620517171]
本研究では,重み付き問題の一般的なクラスに適用したQAOAのパラメータ設定を開発する。まず、重み付けされたMaxCut問題に適用した深さ$p=1$のQAOAに対する最適パラメータを、重み付けの異なる仮定の下で導出する。第二に、$pgeq 1$ の場合、重み付き MaxCut の QAOA エネルギーランドスケープが、パラメータの単純な再スケーリングの下での未重み付きケースにアプローチすることを証明します。第三に、重み付きMaxCutの解析結果から着想を得た一般的な再スケーリング手法を提案し、その効果を実証する。
論文参考訳（メタデータ） (2023-05-24T14:37:33Z)
Quantum Approximate Optimization Algorithm Parameter Prediction Using a Convolutional Neural Network [0.0]
我々は、深度$p+1$QAOAのパラメータから深度$p+1$QAOAのパラメータを予測する畳み込みニューラルネットワークを構築している。 Max-Cut に対する平均近似比 92735$ 800$ ErdHos-R'enyi を得る。
論文参考訳（メタデータ） (2022-11-17T13:20:58Z)
Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文参考訳（メタデータ） (2022-03-01T19:47:16Z)
Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。問題の大きさと問題グラフの次数で指数関数的に増大する。これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文参考訳（メタデータ） (2022-01-06T21:02:30Z)
STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文参考訳（メタデータ） (2021-11-01T15:43:36Z)
Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
論文参考訳（メタデータ） (2021-08-11T15:44:16Z)
Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems [1.8732539895890135]
単一層(p=1$)量子近似最適化アルゴリズム(QAOA)によって生成されるエネルギー-観測値のランドスケープについて報告する。景観は我々が導いた解析式を用いて得られる。数千量子ビットの量子コンピュータ上で実行される場合、単層QAOAがどの程度うまく機能するかを推定する。
論文参考訳（メタデータ） (2020-12-07T02:23:37Z)
Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文参考訳（メタデータ） (2020-11-26T18:22:21Z)
Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文参考訳（メタデータ） (2020-08-29T14:58:26Z)
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)

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

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