論文の概要: Embedding of Complete Graphs in Broken Chimera Graphs

• arxiv url: http://arxiv.org/abs/2012.12720v1
• Date: Wed, 23 Dec 2020 14:56:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-19 19:35:33.259459
• Title: Embedding of Complete Graphs in Broken Chimera Graphs
• Title（参考訳）: 崩壊キメラグラフにおける完全グラフの埋め込み
• Authors: Elisabeth Lobe, Lukas Sch\"urmann, Tobias Stollenwerk
• Abstract要約: D-Wave量子アニールを用いた実世界の最適化問題を解決するには、D-Waveハードウェアグラフに手元にその問題を埋め込む必要がある。 完全グラフを破れたキメラグラフに埋め込む問題に対する新しいアプローチを提案する。
• 参考スコア（独自算出の注目度）: 0.4640835690336653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In order to solve real world combinatorial optimization problems with a D-Wave quantum annealer it is necessary to embed the problem at hand into the D-Wave hardware graph, namely Chimera or Pegasus. Most hard real world problems exhibit a strong connectivity. For the worst case scenario of a complete graph, there exists an efficient solution for the embedding into the ideal Chimera graph. However, since real machines almost always have broken qubits it is necessary to find an embedding into the broken hardware graph. We present a new approach to the problem of embedding complete graphs into broken Chimera graphs. This problem can be formulated as an optimization problem, more precisely as a matching problem with additional linear constraints. Although being NP-hard in general it is fixed parameter tractable in the number of inaccessible vertices in the Chimera graph. We tested our exact approach on various instances of broken hardware graphs, both related to real hardware as well as randomly generated. For fixed runtime, we were able to embed larger complete graphs compared to previous, heuristic approaches. As an extension, we developed a fast heuristic algorithm which enables us to solve even larger instances. We compared the performance of our heuristic and exact approaches.
• Abstract（参考訳）: D-Wave量子アニールを用いた実世界の組合せ最適化問題を解決するためには、問題をD-Waveハードウェアグラフ、すなわちChimeraやPegasusに埋め込む必要がある。 ほとんどの難しい現実世界の問題は強い接続性を示している。 完全グラフの最悪の場合、理想キメラグラフへの埋め込みの効率的な解が存在する。 しかし、実際のマシンは常にキュービットが壊れているため、壊れたハードウェアグラフに埋め込みを見つける必要がある。 本稿では,破断したキメラグラフに完全グラフを埋め込む問題に対する新しいアプローチを提案する。 この問題は最適化問題、より正確には追加の線形制約を伴うマッチング問題として定式化することができる。 一般にNPハードであるが、キメラグラフの到達不能頂点の個数では固定パラメータを抽出できる。 故障したハードウェアグラフのさまざまなインスタンスに対して、実際のハードウェアとランダムに生成されたハードウェアの両方に関して、正確なアプローチを検証した。 固定ランタイムでは、従来のヒューリスティックなアプローチに比べて大きな完全なグラフを埋め込むことができました。 拡張として、我々はさらに大きなインスタンスを解くことができる高速ヒューリスティックアルゴリズムを開発した。 私たちはヒューリスティックで正確なアプローチのパフォーマンスを比較した。

関連論文リスト

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。 我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。 我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
  論文  参考訳（メタデータ） (2024-12-03T18:36:45Z)
• GCoder: Improving Large Language Model for Generalized Graph Problem Solving [38.9131866084555]
  大規模言語モデル(LLM)は強力な推論能力を示しており、グラフ計算のような複雑なタスクに適している。 本稿では,一般化グラフ問題における問題解決の強化を目的とした,コードベースのLLMであるGCoderを紹介する。 本手法では,多種多様なグラフ形式とアルゴリズムを特徴とする広範囲なトレーニングデータセットであるGraphWildを構築する。
  論文  参考訳（メタデータ） (2024-10-24T18:40:36Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  学習対応は、不均一な対応分布と低い不整合率で設定された初期対応から正しい対応を見つけることを目的としている。 最近の進歩は、通常、グラフニューラルネットワーク(GNN)を使用して単一のタイプのグラフを構築したり、グローバルなグラフに局所グラフをスタックしてタスクを完了させる。 本稿では,複数の補完グラフを効果的に組み合わせるためのMGNetを提案する。
  論文  参考訳（メタデータ） (2024-01-10T07:58:44Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
  最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。 提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。 我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-01T14:02:06Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete [0.0]
  本研究は,既存ハードウェアの両タイプにおいて,組込み問題の難しさを示すものである。 我々はいくつかの破れたキメラグラフを構築し、そこではハミルトニアンサイクルを見つけることは困難である。 キメラグラフとペガサスグラフの間の部分グラフ関係を利用することで、証明はさらにペガサスグラフにまで拡張される。
  論文  参考訳（メタデータ） (2021-10-15T19:23:33Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。 本研究では,フィルタグラフ距離近似を導入する。
  論文  参考訳（メタデータ） (2021-09-09T17:43:07Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。 本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。 最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T01:35:45Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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