論文の概要: Evaluation of QAOA based on the approximation ratio of individual samples

• arxiv url: http://arxiv.org/abs/2006.04831v2
• Date: Mon, 7 Dec 2020 20:03:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 06:47:56.045055
• Title: Evaluation of QAOA based on the approximation ratio of individual samples
• Title（参考訳）: 個別試料の近似比に基づくQAOAの評価
• Authors: Jason Larkin, Mat\'ias Jonsson, Daniel Justice, and Gian Giacomo Guerreschi
• Abstract要約: 我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors, it is one of the promising candidates likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, for exact, approximate and heuristic solution. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (quantum approximation optimization algorithm,qaoa) は、二変数最適化問題を解決するためのハイブリッド量子古典アルゴリズムである。 回路の深さが短く、系統的エラーに対する堅牢性が期待できるため、短期的量子デバイス上で動作可能な有望な候補の一つである。 我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、精度、近似、ヒューリスティックな解に対して、いくつかの古典的代替品と比較する。 解答器を比較する際、その性能は与えられた解の質を達成するのに要する計算時間によって特徴づけられる。 qaoaはサンプリングに基づくので、特定の品質以上のサンプルを観測する確率に基づいて、パフォーマンスメトリクスを利用する。 さらに,グラフの種類によってQAOA性能が著しく異なることを示す。 変動パラメータに適したオプティマイザを選択し、関数評価の回数を減らすことにより、QAOA性能は以前の推定よりも最大2桁向上する。 特に3次元正則ランダムグラフの場合、この設定は古典的代替品のパフォーマンスギャップを減少させる。 進化するQAOA計算複雑性理論のガイダンスにより、多数の問題インスタンスと古典的な3つのモダリティ(正確性、近似性、ヒューリスティック性)を組み込んだ量子優位性探索のためのフレームワークを利用する。

関連論文リスト

• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。 The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。 最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
  論文  参考訳（メタデータ） (2024-06-25T09:02:31Z)
• A hybrid quantum-classical approach to warm-starting optimization [0.0]
  ポートフォリオ最適化の観点から,標準QAOAとウォームスタートQAOAのパフォーマンスを比較した。 この結果が,従来の問題に先行する純粋に古典的な前処理によって再現されるか,あるいは超えられることを示し,その後に標準的なQAOAが続く。
  論文  参考訳（メタデータ） (2023-09-25T08:53:54Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• The QAOA with Few Measurements [4.713817702376467]
  近似量子最適化アルゴリズム (QAOA) はもともと最適化問題の解法として開発された。 完全な記述型ベンチマーク技術は、多くの量子ビットに対してしばしば高価である。 中性原子量子コンピュータのような実験的な量子コンピューティングプラットフォームは、繰り返し速度が遅い。
  論文  参考訳（メタデータ） (2022-05-13T18:42:20Z)
• 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)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。 我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
  論文  参考訳（メタデータ） (2021-08-11T15:44:16Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。 量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
  論文  参考訳（メタデータ） (2021-07-11T10:56:24Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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