論文の概要: Edge coloring lattice graphs

• arxiv url: http://arxiv.org/abs/2402.08752v1
• Date: Tue, 13 Feb 2024 19:38:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-15 17:55:25.974044
• Title: Edge coloring lattice graphs
• Title（参考訳）: エッジ着色格子グラフ
• Authors: Joris Kattem\"olle
• Abstract要約: 格子グラフのパッチの適切なエッジ色付けに必要な条件を翻訳により証明する。 この条件は、無限格子グラフの極小または極小の辺色付けを見つける方法の基礎となる。 我々の研究は、量子シミュレーション、量子最適化、量子状態検証といった分野において、最小深度量子回路を提供することによって、直接的な応用を見出した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop the theory of the edge coloring of infinite lattice graphs, proving a necessary and sufficient condition for a proper edge coloring of a patch of a lattice graph to induce a proper edge coloring of the entire lattice graph by translation. This condition forms the cornerstone of a method that finds nearly minimal or minimal edge colorings of infinite lattice graphs. In case a nearly minimal edge coloring is requested, the running time is $O(\mu^2 D^4)$, where $\mu$ is the number of edges in one cell (or `basis graph') of the lattice graph and $D$ is the maximum distance between two cells so that there is an edge from within one cell to the other. In case a minimal edge coloring is requested, we lack an upper bound on the running time, which we find need not pose a limitation in practice; we use the method to minimal edge color the meshes of all $k$-uniform tilings of the plane for $k\leq 6$, while utilizing modest computational resources. We find that all these lattice graphs are Vizing class~I. Relating edge colorings to quantum circuits, our work finds direct application by offering minimal-depth quantum circuits in the areas of quantum simulation, quantum optimization, and quantum state verification.
• Abstract（参考訳）: 無限格子グラフのエッジカラー化の理論を開発し、格子グラフのパッチの適切なエッジカラー化に必要な十分条件を証明し、変換により格子グラフ全体の適切なエッジカラー化を誘導する。 この条件は無限格子グラフのほとんど最小または最小の辺彩色を見つける方法の基礎となる。 ほぼ最小限のエッジカラー化が要求される場合、実行時間は$o(\mu^2 d^4)$であり、ここで$\mu$は格子グラフの1つのセル(または‘basis graph’)内のエッジの数であり、$d$は2つのセル間の最大距離であり、一方のセルから他方へのエッジが存在する。 最小のエッジカラー化が要求される場合、実行時間の上限が不足するので、実際には制限は必要ありません。我々はこの方法を使用して、控えめな計算リソースを利用して、プレーンの全$k$-uniform tilingのメッシュを$k\leq 6$で最小化します。 これらのグラフはすべて Vizing class~I である。 エッジカラーリングを量子回路に関連づけて,量子シミュレーション,量子最適化,量子状態検証といった分野において,極端に詳細な量子回路を提供することにより,直接的応用を見出す。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
  本研究では,非プライベートなストリーミングアルゴリズムと静的グラフアルゴリズムによるスペーシング手法を新たに活用する。 エッジ微分プライベートアルゴリズムは、グラフ内のエッジの数に関して、サブ線形空間を使用する。 完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• Local random quantum circuits form approximate designs on arbitrary architectures [0.1977825609388727]
  エッジが許容される2$-qudit相互作用を決定する任意の連結グラフ上のランダム量子回路(RQC)を考える。 有界次数と高さを持つグラフ上のRQCは、$O(mathrmpoly(k))$ gates の後、$k$-designs となる。 我々は、RQCが回路サイズで近似設計を生成するグラフのより大きなクラスを同定する。
  論文  参考訳（メタデータ） (2023-10-30T08:48:14Z)
• Planted Bipartite Graph Detection [13.95780443241133]
  ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。 k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
  論文  参考訳（メタデータ） (2023-02-07T18:18:17Z)
• The Packing Chromatic Number of the Infinite Square Grid is 15 [5.863264019032882]
  Packing $k$-coloringは、グラフの標準概念である$k$-coloringのバリエーションである。 約2桁のオーダーで最もよく知られた方法を改善することにより、無限正方格子のパッキング数を証明した。
  論文  参考訳（メタデータ） (2023-01-23T23:27:41Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。 本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
  論文  参考訳（メタデータ） (2021-12-08T08:23:37Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  この文書の以前のバージョンでは、記述されたアルゴリズムの一部のランタイムを誤って解釈した。 グラフが存在すれば$d$カラーの適切な色付けを見つけるための新しいアルゴリズム的アプローチを提案する。
  論文  参考訳（メタデータ） (2021-11-29T09:17:34Z)
• Optimizing Ansatz Design in QAOA for Max-cut [0.9126120966154119]
  CNOTは現代の量子コンピュータの主要なエラー源の1つである。 本稿では,回路内のCNOTゲート数を削減するための2つのハードウェア独立手法を提案する。
  論文  参考訳（メタデータ） (2021-06-05T06:43:48Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
  本稿では,graphonと呼ばれる非パラメトリックグラフモデルを学ぶための新しい原理的手法を提案する。 提案手法は, 従来の最先端手法の欠点を克服し, 合成データと実データの両方でそれを上回る。
  論文  参考訳（メタデータ） (2020-12-10T13:04:29Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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