論文の概要: Large-scale Quantum Approximate Optimization via Divide-and-Conquer
- arxiv url: http://arxiv.org/abs/2102.13288v1
- Date: Fri, 26 Feb 2021 03:10:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-09 20:48:35.860368
- Title: Large-scale Quantum Approximate Optimization via Divide-and-Conquer
- Title(参考訳): 分数行列による大規模量子近似最適化
- Authors: Junde Li, Mahabubul Alam, Swaroop Ghosh
- Abstract要約: グラフ最大カット問題(MaxCut)の課題に対処するため,Divide-and-Conquer QAOA(DC-QAOA)を提案する。
DC-QAOAは97.14%の近似比(20.32%)を達成する
また、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
- 参考スコア(独自算出の注目度): 8.733794945008562
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a promising hybrid
quantum-classical algorithm for solving combinatorial optimization problems.
However, it cannot overcome qubit limitation for large-scale problems.
Furthermore, the execution time of QAOA scales exponentially with the problem
size. We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the above
challenges for graph maximum cut (MaxCut) problem. The algorithm works by
recursively partitioning a larger graph into smaller ones whose MaxCut
solutions are obtained with small-size NISQ computers. The overall solution is
retrieved from the sub-solutions by applying the combination policy of quantum
state reconstruction. Multiple partitioning and reconstruction methods are
proposed/ compared. DC-QAOA achieves 97.14% approximation ratio (20.32% higher
than classical counterpart), and 94.79% expectation value (15.80% higher than
quantum annealing). DC-QAOA also reduces the time complexity of conventional
QAOA from exponential to quadratic.
- Abstract(参考訳): 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題を解決するための有望なハイブリッド量子古典アルゴリズムである。
しかし、大規模な問題に対する量子ビット制限を克服することはできない。
さらに、QAOAの実行時間は問題サイズと指数関数的にスケールする。
本稿では、グラフ最大カット問題(最大カット問題)に対する上記の課題に対処するために、分割・分割qaoa(dc-qaoa)を提案する。
このアルゴリズムは、大きなグラフを、小さなサイズのNISQコンピュータで得られるMaxCutソリューションの小さなグラフに再帰的に分割することで機能する。
全体の解は、量子状態再構成の組み合わせポリシーを適用することにより、サブソリューションから取得される。
複数の分割法と再構成法が提案/比較されている。
DC-QAOAは97.14%の近似比(20.32%)、94.79%の期待値(15.80%)を達成している。
DC-QAOAはまた、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
関連論文リスト
- QAOA with fewer qubits: a coupling framework to solve larger-scale
Max-Cut problem [6.783232060611114]
より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。
古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。
われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
論文 参考訳(メタデータ) (2023-07-28T02:06:42Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳(メタデータ) (2021-02-12T23:12:09Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳(メタデータ) (2020-11-10T22:17:50Z) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳(メタデータ) (2020-05-20T18:00:01Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。