論文の概要: 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の時間的複雑さを指数関数から二次的に減少させる。

関連論文リスト

• 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)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• 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)
• 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)

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

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