論文の概要: Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

• arxiv url: http://arxiv.org/abs/2306.00494v1
• Date: Thu, 1 Jun 2023 09:44:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-02 17:12:15.133584
• Title: Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms
• Title（参考訳）: 変分量子アルゴリズムを用いた組合せ最適化問題を解くグラフ分解法
• Authors: Moises Ponce, Rebekah Herrman, Phillip C. Lotshaw, Sarah Powers, George Siopsis, Travis Humble, James Ostrowski
• Abstract要約: 我々はQAOA入力問題グラフをより小さな問題に分解するアルゴリズムを開発し、削減グラフ上でQAOAを用いてMaxCutを解く。 量子量子コンピュータH1-1上で1層QAOA回路を動作させることにより、10個の100頂点グラフに対する最適解を測定することができる。
• 参考スコア（独自算出の注目度）: 1.2622634782102324
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum--in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly $k$-regular graphs, as $k$-regular graphs on $n$ vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. While this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は多項式時間で複雑な組合せ最適化問題を解くことができる。 しかし、現在のノイズ量子デバイスは、ハードウェアの制約により大きな問題を解決できない。 本研究では,QAOAの入力問題グラフを小さな問題に分解し,削減グラフ上でQAOAを用いてMaxCutを解くアルゴリズムを開発した。 アルゴリズムは古典的あるいは量子的なサブルーチンを必要とするが、この作業では各グラフに2回アルゴリズムを実装している。 1つの実装は古典的な解法であるグロビをサブルーチンに使用し、もう1つはQAOAを使用する。 これらの問題をQAOAで解決する。 平均して、削減された問題は、元のMaxCutインスタンスよりも頂点の1/10程度しか必要としない。 さらに、元のMaxCut問題の平均近似比は0.75であり、分解されたグラフの近似比は、グロビとQAOAの両方で平均0.96である。 この分解により、量子化量子コンピュータH1-1上で1層QAOA回路を動作させ、各回路を500回だけサンプリングすることで、10個の100頂点グラフに対する最適解を測定できる。 このアプローチはスパース、特に$k$正則グラフに最も適しており、$n$頂点上の$k$正則グラフは多項式時間で最大$\frac{nk}{k+1}$頂点を持つグラフに分解することができる。 計算時間における潜在的なトレードオフにより、さらなる削減が得られる。 本稿では,MaxCut問題に対して分解法を適用するが,より一般的な組合せ最適化問題に適用できる。

関連論文リスト

• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
  パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。 我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
  論文  参考訳（メタデータ） (2024-08-17T03:34:17Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Combinatorial optimization with quantum imaginary time evolution [2.048226951354646]
  線形アンザッツは、幅広いPUBO問題に対して良い結果をもたらすことを示す。 我々は,Low Autocorrelation Binary Sequences (LABS) と重み付きMaxCut最適化問題の数値結果を得た。
  論文  参考訳（メタデータ） (2023-12-27T18:18:12Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• 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)
• Solving MaxCut with Quantum Imaginary Time Evolution [0.0]
  量子想像時間進化(QITE)に基づくMaxCut問題の解法を提案する。 10ステップの後に、平均解は最大MaxCut解の100%、99%、98%、97%であることが示される。
  論文  参考訳（メタデータ） (2022-01-28T16:24: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)
• 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)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。 我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
  論文  参考訳（メタデータ） (2020-05-18T14:23:09Z)

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

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