論文の概要: Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
- arxiv url: http://arxiv.org/abs/2110.08325v1
- Date: Fri, 15 Oct 2021 19:23:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 09:51:15.677370
- Title: Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
- Title（参考訳）: 臭素キメラとペガサスグラフの微小埋め込みはNP完全である
- Authors: Elisabeth Lobe, Annette Lutz
- Abstract要約: 本研究は,既存ハードウェアの両タイプにおいて,組込み問題の難しさを示すものである。
我々はいくつかの破れたキメラグラフを構築し、そこではハミルトニアンサイクルを見つけることは困難である。
キメラグラフとペガサスグラフの間の部分グラフ関係を利用することで、証明はさらにペガサスグラフにまで拡張される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The embedding is an essential step when calculating on the D-Wave machine. In
this work we show the hardness of the embedding problem for both types of
existing hardware, represented by the Chimera and the Pegasus graphs,
containing unavailable qubits. We construct certain broken Chimera graphs,
where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem
is a special case of the embedding problem, this proves the general complexity
result for the Chimera graphs. By exploiting the subgraph relation between the
Chimera and the Pegasus graphs, the proof is then further extended to the
Pegasus graphs.
- Abstract（参考訳）: 埋め込みはD-Waveマシン上での計算において重要なステップである。
本研究では,キメラグラフとペガサスグラフで表される,使用不能な量子ビットを含む2種類の既存ハードウェアの組込み問題の難しさを示す。
ある種の破れたキメラグラフを構築するが、ハミルトニアンサイクルを見つけるのは難しい。
ハミルトニアンサイクル問題は埋め込み問題の特別な場合であるため、これはキメラグラフの一般的な複雑さの結果を証明する。
キメラグラフとペガサスグラフの間の部分グラフ関係を利用することで、証明はさらにペガサスグラフにまで拡張される。
関連論文リスト
- All the World's a (Hyper)Graph: A Data Drama [55.144729234861316]
Hyperbardはシェイクスピアの戯曲からの多様なデータ表現のデータセットである。
私たちの表現は、単一のシーンで文字の共起をキャプチャする単純なグラフから、複雑な通信設定を符号化するハイパーグラフまで様々です。
データソースへのオマージュとして、科学もまた芸術であると主張するため、私たちはすべてのポイントを遊びの形で提示します。
論文 参考訳（メタデータ） (2022-06-16T14:51:28Z) - What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。
様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
論文 参考訳（メタデータ） (2022-05-27T14:36:55Z) - Partition and Code: learning how to compress graphs [50.29024357495154]
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
論文 参考訳（メタデータ） (2021-07-05T11:41:16Z) - Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer [0.0]
本稿では,グラフ分割におけるNP完全問題の解法として,量子アニールを用いる方法を示す。
この問題を2次非拘束バイナリ最適化として定式化し、D波アドバンテージ量子アニール上で実行する。
論文 参考訳（メタデータ） (2021-04-18T16:15:00Z) - Graph state representation of the toric code [0.0]
トーリック符号グラフは、星グラフ(グリーンベルガー=ホルン=ゼーリンガー状態の符号化)とハーフグラフの2種類の部分グラフからなる。
その結果, トポロジ的順序の調査と新しいトポロジ的誤り訂正符号の開発のためのグラフ理論の枠組みが得られた。
論文 参考訳（メタデータ） (2021-03-23T02:27:07Z) - Embedding of Complete Graphs in Broken Chimera Graphs [0.4640835690336653]
D-Wave量子アニールを用いた実世界の最適化問題を解決するには、D-Waveハードウェアグラフに手元にその問題を埋め込む必要がある。
完全グラフを破れたキメラグラフに埋め込む問題に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2020-12-23T14:56:46Z) - Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
本稿では,graphonと呼ばれる非パラメトリックグラフモデルを学ぶための新しい原理的手法を提案する。
提案手法は, 従来の最先端手法の欠点を克服し, 合成データと実データの両方でそれを上回る。
論文 参考訳（メタデータ） (2020-12-10T13:04:29Z) - Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted
Z-graded graphs [62.997667081978825]
グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。
位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
論文 参考訳（メタデータ） (2020-08-11T17:58:13Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。
完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。
この仮説を支持する数値シミュレーションをいくつか提示する。
論文 参考訳（メタデータ） (2020-02-26T00:10:38Z) - What do QAOA energies reveal about graphs? [2.0305676256390934]
グラフ構造に対するQAOAエネルギーの依存を利用して、ランダムにあるいは司法的に選択されたパラメータをグラフについて学習する。
我々の発見の多くは、様々な制約の下で$U(G)$と解釈できる。
論文 参考訳（メタデータ） (2019-12-27T18:37:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。