論文の概要: 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ハードグラフ問題に対する分解アルゴリズムの一般的な枠組みについて検討する。
我々のジェネリックアルゴリズムは、生成したサブプロブレムが量子アニーラーハードウェアに埋め込まれるまで、再帰的にインスタンスを分割することを可能にする。
本手法は, 最大斜めおよび最小頂点被覆問題に適用し, 再帰分解を高速化するいくつかのプルーニングおよび還元手法を提案する。
両アルゴリズムの性能は詳細なシミュレーション研究で評価される。
関連論文リスト
- Quantum Variational Algorithms for the Allocation of Resources in a
Cloud/Edge Architecture [1.1715858161748576]
クラウド/エッジアーキテクチャは、異種コンピューティングノードの複数のレイヤを編成する必要がある。
異なるノード上での計算の最適割り当てとスケジューリングは非常に難しい問題であり、NP困難である。
近い将来,変分量子アルゴリズムが古典的アルゴリズムの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (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) - Solving Subset Sum Problems using Quantum Inspired Optimization
Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
Hopfield Networksの勾配勾配勾配が、人工データと実データの両方の解を確実に見つける方法を示す。
本稿では,このアルゴリズムを断熱量子コンピュータに応用する方法を概説する。
論文 参考訳(メタデータ) (2022-10-28T12:22:15Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems [61.48763653120301]
クリティカルノード問題(Critical Node Problem, CNP)は、ネットワークから重要なノードの集合を見つけることを目的とした問題である。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳(メタデータ) (2021-12-03T14:23:05Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。