論文の概要: A Quantum Framework for K Coloring of Graphs

• arxiv url: http://arxiv.org/abs/2609.32348v1
• Date: Sat, 26 Sep 2026 08:09:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 17:32:27.288351
• Title: A Quantum Framework for K Coloring of Graphs
• Title（参考訳）: グラフのK色化のための量子フレームワーク
• Abstract要約: グラフカラー化は、スケジューリング、レジスタ割り当て、周波数割り当て、ネットワーク最適化などにおいてよく知られたNP完全問題である。 量子コンピューティングは、特定の問題インスタンスにおいてスーパーポリノミカルなスピードアップの可能性を秘めている。 我々は、$K$-coloringのためのソルバ量子フレームワークを提案した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for $K$-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using $O(NK)$ qubits as in \emph{SOTA}, we reduced the qubit requirements to $O(N \log_2 K)$, along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.
• Abstract（参考訳）: グラフカラー化は、スケジューリング、レジスタ割り当て、周波数割り当て、ネットワーク最適化などにおいてよく知られたNP完全問題である。 量子コンピューティングは、ある種の問題の場合において多項式や超多項式のスピードアップのポテンシャルを提供するが、実用的な量子グラフカラーリング法は、キュービットリソース、回路深さ、制約執行を慎重にバランスさせなければならない。 我々は、$K$-coloringのためのソルバ非依存の量子フレームワークを提案した。 量子近似最適化アルゴリズム \emph{(QAOA)} と \emph{Quantum Annealing} によって、Grover 探索とほぼ最適な色付けを利用するための、新しい符号化と効率的な制約実装とともに、量子近似最適化アルゴリズム \emph{(QAOA)} と \emph{Quantum Annealing} による。 我々は、emph{SOTA}のように$O(NK)$ qubitsを使用するのと異なり、Qubitの要求を$O(N \log_2 K)$に減らした。 さらに対称性に基づくグラフ削減を任意の前処理ステップとして組み込んで、量子実行前のインスタンスサイズをさらに削減する。

関連論文リスト

• BBQ-mIS: a parallel quantum algorithm for graph coloring problems [0.11242503819703255]
  本稿では,Rydberg 原子量子マシン上でのグラフカラー化問題を解くために,BBQ-mIS というハイブリッド量子古典アルゴリズムを提案する。 我々は、実量子ハードウェアをIBM Power9ベースのクラスタにエミュレートし、32コア/ノードと256GB/ノードを持ち、MBI強化ライブラリを利用してBBQ-mISアルゴリズムの並列性を実装した。
  論文  参考訳（メタデータ） (2026-05-05T08:59:53Z)
• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。 フィードバック修正とコンフリクト解決を統合した階層的なフレームワークを使用して、$k$-coloringを実現しています。 提案手法を用いて、地下鉄の交通ネットワークのスケジューリングを最適化し、高い公平性を実証する。
  論文  参考訳（メタデータ） (2025-04-30T05:45:15Z)
• Quantum Circuit Optimization by Graph Coloring [0.0]
  通勤操作からなる量子回路の深さ最適化は、グラフ理論の頂点色問題に対して再現可能である。 この減少は、どの色解決器も利用して通勤ゲートの回路最適化を行うアルゴリズムを直ちに導く。
  論文  参考訳（メタデータ） (2025-01-24T12:29:16Z)
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  本稿では,2つのスケジューリング問題に対して,ディジタル化された反断熱量子最適化(DCQO)アルゴリズムを提案する。 ジョブショップスケジューリング問題では,特定の制約下で複数のタスクを実行するロボットの最適なスケジュールを見つけることを目的としている。 旅行セールスパーソンの問題は、すべての都市をカバーし、最短の旅行距離と関連する経路を見つけることである。
  論文  参考訳（メタデータ） (2024-05-24T16:53:30Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。 Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。 評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
  論文  参考訳（メタデータ） (2024-04-30T23:55:03Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。 我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
  論文  参考訳（メタデータ） (2022-02-10T18:59:52Z)
• Graph Coloring with Quantum Annealing [0.0]
  そこで我々は,D-Wave 2X を独立セットサンプリングとして用いたグラフカラー化近似アルゴリズムを開発した。 ランダムに生成された小さなグラフインスタンスのセットは、テストセットとして役立ちます。 我々の性能分析は、ハイブリッド量子古典アルゴリズムにおける量子優位性に限界があることを示唆している。
  論文  参考訳（メタデータ） (2020-12-08T15:08:22Z)
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding [0.0]
  グラフ彩色問題に対する空間効率のよい量子最適化アルゴリズムを提案する。 我々の回路は標準的アプローチよりも深い。 現在利用可能な代替品を探索するために、量子アニール上でランダムなグラフ色付けの研究を行う。
  論文  参考訳（メタデータ） (2020-09-15T18:34:17Z)

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

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