論文の概要: Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing
- arxiv url: http://arxiv.org/abs/2311.04405v1
- Date: Wed, 8 Nov 2023 00:16:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-09 17:31:55.361836
- Title: Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing
- Title(参考訳): 量子アニーリングを用いたラムゼー数の境界計算に向けて
- Authors: Joel E. Pion and Susan M. Mniszewski
- Abstract要約: 単色三角形問題とラムゼー数問題を考える。
量子ハードウェア上では、2次非制約バイナリ最適化(QUBO)形式への変換が必要である。
我々は、D波アドバンテージ量子アニール上での動作における実装、制限、および結果について議論する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum annealing is a powerful tool for solving and approximating
combinatorial optimization problems such as graph partitioning, community
detection, centrality, routing problems, and more. In this paper we explore the
use of quantum annealing as a tool for use in exploring combinatorial
mathematics research problems. We consider the monochromatic triangle problem
and the Ramsey number problem, both examples of graph coloring. Conversion to
quadratic unconstrained binary optimization (QUBO) form is required to run on
quantum hardware. While the monochromatic triangle problem is quadratic by
nature, the Ramsey number problem requires the use of order reduction methods
for a quadratic formulation. We discuss implementations, limitations, and
results when running on the D-Wave Advantage quantum annealer.
- Abstract(参考訳): 量子アニールは、グラフ分割、コミュニティ検出、集中性、ルーティング問題など、組合せ最適化問題の解決と近似のための強力なツールである。
本稿では,組合せ数学研究問題の解法としての量子アニールの利用について検討する。
我々は,単色三角形問題とラムゼー数問題について考察する。
量子ハードウェア上では、2次非制約バイナリ最適化(QUBO)形式への変換が必要である。
単色三角形問題は自然に二次的であるが、ラムゼー数問題は二次的な定式化に順序還元法を用いる必要がある。
d-wave advantage quantum annealer上で実行する場合の実装、制限、結果について議論する。
関連論文リスト
- An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。
QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。
論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
論文 参考訳(メタデータ) (2024-09-09T11:29:46Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-11T04:40:05Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳(メタデータ) (2023-11-16T09:19:01Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳(メタデータ) (2023-06-07T12:19:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Search Algorithm for Binary Constant Weight Codes [3.3555130013686014]
バイナリ定数重み付け符号は、幅広いアプリケーションを持つエラー訂正符号の一種である。
本稿では,バイナリ定数重み付き符号に対する量子探索アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-09T01:57:11Z) - 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) - 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) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。