論文の概要: Efficient hybrid variational quantum algorithm for solving graph coloring problem
- arxiv url: http://arxiv.org/abs/2504.21335v1
- Date: Wed, 30 Apr 2025 05:45:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-09 22:20:38.701449
- Title: Efficient hybrid variational quantum algorithm for solving graph coloring problem
- Title（参考訳）: グラフ彩色問題の解法のための効率的なハイブリッド変分量子アルゴリズム
- Authors: Dongmei Liu, Jian Li, Xiubo Cheng, Shibing Zhang, Yan Chang, Lili Yan,
- Abstract要約: 本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。
フィードバック修正とコンフリクト解決を統合した階層的なフレームワークを使用して、$k$-coloringを実現しています。
提案手法を用いて、地下鉄の交通ネットワークのスケジューリングを最適化し、高い公平性を実証する。
- 参考スコア（独自算出の注目度）: 4.4739537033766705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the $k$-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
- Abstract（参考訳）: ノイズ中間スケール量子(NISQ)コンピューティングの時代、利用可能な量子リソースは限られている。
多くのNPハード問題は、古典的および量子計算のハイブリッド手法を用いて効率的に扱うことができる。
本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。
古典と量子のハイブリッドアルゴリズムは、主に階層的な手法によってグラフを複数の部分グラフに分割する。
Quantum Approximate Optimization Algorithm (QAOA) はサブグラフ内の色を決定するために使用され、古典的なグリーディアルゴリズムは相互作用グラフの色を見つけるために使用される。
相互作用グラフに固定色を適用し、サブグラフ内の衝突色を補正するためのフィードバックを提供する。
元のグラフへのマージプロセスは、発生した競合を解決するために反復的に最適化される。
フィードバック補正とコンフリクト解決を統合した階層的フレームワークを用いて任意のグラフ頂点の$k$-coloringを実現する。
実験により,コンフリクト進化の急速な収束と反復最適化により,古典的アルゴリズムが色数に近似できることを示す。
最後に,提案手法を適用して,地下鉄交通網のスケジューリングを最適化し,高い公平性を示す。
関連論文リスト
- Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array [0.0]
本稿では,ネイティブ組込みグラフ着色問題の解法を提案する。
色数に対する最適なグラフ色付けを、Rydberg状態の異なる数まで確実に見つける能力を示す。
本稿では,本手法の実験的実現可能性について論じ,高い色数問題を解くための拡張法を提案する。
論文 参考訳（メタデータ） (2025-04-11T14:55:35Z) - Quantum Circuit Optimization by Graph Coloring [0.0]
通勤操作からなる量子回路の深さ最適化は、グラフ理論の頂点色問題に対して再現可能である。
この減少は、どの色解決器も利用して通勤ゲートの回路最適化を行うアルゴリズムを直ちに導く。
論文 参考訳（メタデータ） (2025-01-24T12:29:16Z) - A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。
完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。
ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文 参考訳（メタデータ） (2025-01-02T05:06:16Z) - Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。
本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
論文 参考訳（メタデータ） (2024-08-02T18:02:51Z) - Qudit-inspired optimization for graph coloring [0.0]
グラフ色問題(GCP)に対する量子インスピレーションアルゴリズムを提案する。
我々は、グラフ内のノードを表現し、d次元球面座標でパラメータ化した各キューディットを積状態に使用する。
我々は,2つの最適化戦略をベンチマークする: 傾き勾配降下, ランダム状態の立方体開始, コスト関数の最小化のために勾配勾配勾配を用いる。
論文 参考訳（メタデータ） (2024-06-02T16:19:55Z) - Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。
マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
論文 参考訳（メタデータ） (2022-02-03T14:24:12Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。
与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。
実験の結果,本手法は著しい改善をもたらすことがわかった。
論文 参考訳（メタデータ） (2021-03-30T17:36:40Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。
解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
論文 参考訳（メタデータ） (2020-10-21T20:04:22Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。