論文の概要: Advancing stable set problem solutions through quantum annealers
- arxiv url: http://arxiv.org/abs/2308.13041v1
- Date: Wed, 23 Aug 2023 07:18:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-28 16:01:19.624268
- Title: Advancing stable set problem solutions through quantum annealers
- Title(参考訳): 量子アニールによる安定セット問題解の促進
- Authors: Janez Povh and Dunja Pucher
- Abstract要約: グラフにおける安定セット問題の解法としてD波量子解法の性能を評価する。
ハイブリットソルバは良い結果が得られるのに対し、Quantum Processing Unitソルバは全体的には控えめなパフォーマンスを示している。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We assess the performance of D-wave quantum solvers for solving the stable
set problem in a graph, one of the most studied NP-hard problems. We perform
computations on some instances from the literature with up to 125 vertices and
compare the quality of the obtained solutions with known optimum solutions. It
turns out that the hybrid solver gives very good results, while the Quantum
Processing Unit solver shows rather modest performance overall.
- Abstract(参考訳): 最も研究されているNPハード問題の1つであるグラフにおける安定セット問題の解法としてD波量子解法の性能を評価する。
我々は、最大125頂点の文献からいくつかのインスタンス上で計算を行い、得られた解の質を既知の最適解と比較する。
ハイブリッドソルバは、非常に優れた結果を与えるが、量子処理ユニットソルバは全体としては控えめなパフォーマンスを示している。
関連論文リスト
- Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳(メタデータ) (2023-11-16T09:19:01Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum
Computing [99.34965725525188]
AQC(Adiabatic quantum computing)は、NP-hard最適化問題に対する有望な量子コンピューティング手法である。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
論文 参考訳(メタデータ) (2023-10-18T17:59:45Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Divide-and-conquer embedding for QUBO quantum annealing [0.0]
組込み問題に焦点をあてたアプローチは、桁違いに性能を向上できることを示す。
以上の結果から,組込み問題に焦点をあてたアプローチにより,桁違いの性能向上が期待できることがわかった。
論文 参考訳(メタデータ) (2022-11-03T23:22:06Z) - On the hardness of quadratic unconstrained binary optimization problems [0.0]
厳密な列挙法を用いて、21変数未満の2次非制約二元最適化問題の解を特徴づける。
また、D-Wave Advantage 5.1量子アニールを用いて実験を行い、最大170変量2次最適化問題を解く。
論文 参考訳(メタデータ) (2022-06-23T13:29:59Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing [0.5156484100374059]
量子異方体は, 実用的な最適化問題の解法として利用できることを示す。
量子異方体の性能を、最も洗練された数学的最適化解法の一つと比較する。
結果: 20チームで問題が発生した場合、QAは0.05秒で正確なソリューションを決定できた。
論文 参考訳(メタデータ) (2021-10-14T09:08:09Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳(メタデータ) (2021-01-19T17:51:02Z) - Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem [0.0]
D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem。
断熱的量子最適化では、knapsackの最適充填に対応する解が得られない。
論文 参考訳(メタデータ) (2020-08-17T16:29:34Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。