論文の概要: Withdrawn: A Measurement-based Algorithm for Graph Colouring
- arxiv url: http://arxiv.org/abs/2111.14390v3
- Date: Thu, 3 Mar 2022 07:20:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 09:52:16.519664
- Title: Withdrawn: A Measurement-based Algorithm for Graph Colouring
- Title（参考訳）: Withdrawn: グラフカラー化のための計測ベースのアルゴリズム
- Authors: Michael Epping and Tobias Stollenwerk
- Abstract要約: この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。
グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
- 参考スコア（独自算出の注目度）: 0.5482532589225553
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In a previous version of this document we misinterpreted the runtime of a
part of the described algorithm. Indeed, the runtime is not better than the
Grover-Algorithm. We therefor withdraw this work.
We present a novel algorithmic approach to find a proper vertex colouring of
a graph with $d$ colours, if it exists. We associate a $d$-dimensional quantum
system with each vertex and the initial state is a mixture of all possible
colourings, from which we obtain a random proper colouring of the graph by
measurements. The non-deterministic nature of the quantum measurement is
tackled by a reset operation, which can revert the effect of unwanted
projections. As in the classical case, we find that the runtime scales
exponentially with the number of vertices. However, we provide numerical
evidence that the average runtime of the problem-specific part of the algorithm
scales polynomially in the number of edges.
- Abstract（参考訳）: この文書の前バージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。
実際、ランタイムはGrover-Algorithmほど良くない。
私たちはこの仕事を撤回する。
我々は、もし存在すれば、$d$カラーのグラフの適切な頂点カラー化を見つけるための、新しいアルゴリズム的アプローチを提案する。
我々は、$d$次元の量子系を各頂点に関連付け、初期状態はすべての可能な色付けの混合であり、そこから測定によってグラフのランダムな適切な色付けを得る。
量子測定の非決定論的性質は、不要な射影の効果を反転できるリセット演算によって取り組まれる。
古典的な場合と同様に、ランタイムは頂点の数で指数関数的にスケールする。
しかし, 問題固有部分の平均実行時間は, エッジ数で多項式的にスケールすることを示す数値的な証拠を提供する。
関連論文リスト
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。
量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。
このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文 参考訳（メタデータ） (2024-07-01T06:09:19Z) - Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。
本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。
提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
論文 参考訳（メタデータ） (2022-09-19T14:37:35Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Evolutionary Algorithm for Graph Coloring Problem [0.0]
グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。
本稿では、色数の理論上界、すなわち最大外度+1から始める。
進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
論文 参考訳（メタデータ） (2021-11-17T12:16:57Z) - A Grover search-based algorithm for the list coloring problem [1.332560004325655]
本稿では,Grover 探索に基づく量子アルゴリズムを提案する。
我々のアルゴリズムは、制限された特定のケースでは古典的な場合に比べて複雑性が低いが、自然に考慮されたリストやグラフが任意である場合の徹底的な探索を改善する。
論文 参考訳（メタデータ） (2021-08-20T08:41:22Z) - 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) - Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
動的グラフからのグラフエッジのストリームを前提に、オンライン形式でエッジやサブグラフに異常スコアを割り当てるにはどうすればよいのか?
本手法は,高密度部分グラフ探索を取り入れた最初のストリーミング手法であり,一定時間におけるグラフ異常を検出する。
論文 参考訳（メタデータ） (2021-06-08T16:10:36Z) - Time Complexity Analysis of Randomized Search Heuristics for the Dynamic
Graph Coloring Problem [15.45783225341009]
エッジを現在のグラフに追加する動的設定について検討する。
次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
論文 参考訳（メタデータ） (2021-05-26T13:00:31Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。
我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
論文 参考訳（メタデータ） (2020-03-13T20:03:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。