論文の概要: Recursive Quantum Approximate Optimization Algorithm for the MAX-CUT
problem on Complete graphs
- arxiv url: http://arxiv.org/abs/2211.15832v1
- Date: Mon, 28 Nov 2022 23:51:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-17 14:42:48.936160
- Title: Recursive Quantum Approximate Optimization Algorithm for the MAX-CUT
problem on Complete graphs
- Title（参考訳）: 完全グラフ上のマックスカット問題に対する再帰的量子近似最適化アルゴリズム
- Authors: Eunok Bae and Soojoon Lee
- Abstract要約: 量子近似最適化アルゴリズムは、MAX-CUT問題のような最適化問題を近似的に解くために設計されたハイブリッド量子古典的変分アルゴリズムである。
近い将来の量子応用の可能性にもかかわらず、量子近似最適化アルゴリズムはMAX-CUT問題を解くための制限があることが知られている。
- 参考スコア（独自算出の注目度）: 1.90365714903665
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum approximate optimization algorithms are hybrid quantum-classical
variational algorithms designed to approximately solve combinatorial
optimization problems such as the MAX-CUT problem. In spite of its potential
for near-term quantum applications, it has been known that quantum approximate
optimization algorithms have limitations for certain instances to solve the
MAX-CUT problem, at any constant level $p$. Recently, the recursive quantum
approximate optimization algorithm, which is a non-local version of quantum
approximate optimization algorithm, has been proposed to overcome these
limitations. However, it has been shown by mostly numerical evidences that the
recursive quantum approximate optimization algorithm outperforms the original
quantum approximate optimization algorithm for specific instances. In this
work, we analytically prove that the recursive quantum approximate optimization
algorithm is more competitive than the original one to solve the MAX-CUT
problem for complete graphs with respect to the approximation ratio.
- Abstract（参考訳）: 量子近似最適化アルゴリズムは、MAX-CUT問題のような組合せ最適化問題を解くために設計されたハイブリッド量子古典的変分アルゴリズムである。
近い将来の量子応用の可能性にもかかわらず、量子近似最適化アルゴリズムは、任意の定数レベル $p$ において、マックスカット問題を解くための特定のインスタンスに制限があることが知られている。
近年、量子近似最適化アルゴリズムの非局所バージョンである再帰的量子近似最適化アルゴリズムが、これらの制限を克服するために提案されている。
しかし、再帰的量子近似最適化アルゴリズムは、特定のインスタンスに対する元の量子近似最適化アルゴリズムよりも優れているという、主に数値的な証拠によって示されている。
本研究では、再帰的量子近似最適化アルゴリズムが、近似比に関する完全グラフに対するMAX-CUT問題を解くために、元のアルゴリズムよりも競争力があることを解析的に証明する。
関連論文リスト
- 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) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
論文 参考訳（メタデータ） (2022-11-08T02:12:49Z) - Stochastic optimization algorithms for quantum applications [0.0]
本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。
全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
論文 参考訳（メタデータ） (2022-03-11T16:17:05Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quantum optimisation via maximally amplified states [0.0]
本稿では,短期量子コンピューティングの制限回路深度文脈における最適化のための新しい量子アルゴリズムを提案する。
最大増幅最適化アルゴリズム(MAOA)は、他の短期量子アルゴリズムよりもかなり優れている。
論文 参考訳（メタデータ） (2021-11-01T09:43:53Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳（メタデータ） (2020-11-10T22:17:50Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。