論文の概要: Decomposition algorithms for solving NP-hard problems on a quantum annealer

• arxiv url: http://arxiv.org/abs/2009.06726v1
• Date: Thu, 10 Sep 2020 15:59:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-03 00:29:36.809644
• Title: Decomposition algorithms for solving NP-hard problems on a quantum annealer
• Title（参考訳）: 量子アニール上でのNP-ハード問題を解く分解アルゴリズム
• Authors: Elijah Pelofske, Georg Hahn, Hristo Djidjev
• Abstract要約: NPハード問題は、計算化学、生化学、コンピュータネットワークセキュリティに応用されている。 Adaabatic quantum annealers can search the optimum value of such NP-hard optimization problem, because the problem can be embedded on their hardware。 本稿ではNP-hardグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp's 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. The framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.
• Abstract（参考訳）: 最大傾きや最小頂点被覆問題のようなNPハード問題、21個のNPハード問題の2つは、計算化学、生化学、コンピュータネットワークセキュリティにいくつかの応用がある。 断熱量子アニーラは、その問題をハードウェアに埋め込むことができるため、そのようなnpハード最適化問題の最適値を求めることができる。 しかし、アニーラーのハードウェア接続構造に一定の制限があるため、これはしばしば不可能である。 本稿では,頂点の最適集合を特定することを目的としたNPハードグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。 我々のジェネリックアルゴリズムは、生成したサブプロブレムが量子アニーラーハードウェアに埋め込まれるまで、再帰的にインスタンスを分割することを可能にする。 本手法は, 最大斜めおよび最小頂点被覆問題に適用し, 再帰分解を高速化するいくつかのプルーニングおよび還元手法を提案する。 両アルゴリズムの性能は詳細なシミュレーション研究で評価される。

関連論文リスト

• 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)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。 特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。 シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
  論文  参考訳（メタデータ） (2024-01-25T17:37:40Z)
• Quantum Algorithm for Maximum Biclique Problem [11.96554895748371]
  頂点の最大数で双斜線を同定することは、多くの応用分野に相当な意味を持つ。 本稿では,時間的複雑性O*(2(n/2))を持つ基底破れアルゴリズムqMBSを提案する。 最大二進問題と最大二進問題に適した2つの変種を詳述する。
  論文  参考訳（メタデータ） (2023-09-08T04:43:05Z)
• Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
  古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。 NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
  論文  参考訳（メタデータ） (2023-05-26T05:31:25Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。 提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。 タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
  論文  参考訳（メタデータ） (2021-06-24T16:39:31Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  本研究は4つの重要なNPハード問題に対するアンエンベディング手法について述べる。 我々の手法は単純であり、解決される問題の構造的特性を生かしている。
  論文  参考訳（メタデータ） (2020-09-10T17:49:43Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。 問題のどの点も引き付けないアルゴリズムが存在することを示す。 ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
  論文  参考訳（メタデータ） (2020-06-16T10:49:27Z)

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

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