論文の概要: BBQ-mIS: a parallel quantum algorithm for graph coloring problems
- arxiv url: http://arxiv.org/abs/2605.03524v1
- Date: Tue, 05 May 2026 08:59:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-06 19:35:43.860014
- Title: BBQ-mIS: a parallel quantum algorithm for graph coloring problems
- Title（参考訳）: BBQ-mIS : グラフ色問題に対する並列量子アルゴリズム
- Authors: Chiara Vercellino, Giacomo Vitali, Paolo Viviani, Edoardo Giusto, Alberto Scionti, Andrea Scarabosio, Olivier Terzo, Bartolomeo Montrucchio,
- Abstract要約: 本稿では,Rydberg 原子量子マシン上でのグラフカラー化問題を解くために,BBQ-mIS というハイブリッド量子古典アルゴリズムを提案する。
我々は、実量子ハードウェアをIBM Power9ベースのクラスタにエミュレートし、32コア/ノードと256GB/ノードを持ち、MBI強化ライブラリを利用してBBQ-mISアルゴリズムの並列性を実装した。
- 参考スコア（独自算出の注目度）: 0.11242503819703255
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Among the limitations of current quantum machines, the qubits count represents one of the most critical challenges for porting reasonably large computational problems, such as those coming from real-world applications, to the scale of the quantum hardware. In this regard, one possibility is to decompose the problems at hand and exploit parallelism over multiple size-limited quantum resources. To this purpose, we designed a hybrid quantum-classical algorithm, i.e., BBQ-mIS, to solve graph coloring problems on Rydberg atoms quantum machines. The BBQ-mIS algorithm combines the natural representation of Maximum Independent Set (MIS) problems onto the machine Hamiltonian with a Branch&Bound (BB) approach to identify a proper graph coloring. In the proposed solution, the graph representation emerges from qubit interactions (qubits represent vertexes of the graph), and the coloring is then retrieved by iteratively assigning one color to a maximal set of independent vertexes of the graph, still minimizing the number of colors with the Branch&Bound approach. We emulated real quantum hardware onto an IBM Power9-based cluster, with 32 cores/node and 256 GB/node, and exploited an MPI-enhanced library to implement the parallelism for the BBQ-mIS algorithm. Considering this use case, we also identify some technical requirements and challenges for an effective HPC-QC integration. The results show that our problem decomposition is effective in terms of graph coloring solutions quality, and provide a reference for applying this methodology to other quantum technologies or applications.
- Abstract（参考訳）: 現在の量子マシンの限界の中で、量子ビット数は、現実のアプリケーションから来るような、合理的に大きな計算問題を量子ハードウェアのスケールに移植する上で最も重要な課題の1つである。
この点において、手元にある問題を分解し、複数のサイズ制限された量子資源上で並列性を利用する可能性が考えられる。
この目的のために、Rydberg原子量子マシン上のグラフカラー化問題を解くために、BBQ-mISというハイブリッド量子古典アルゴリズムを設計した。
BBQ-mISアルゴリズムは、マシン・ハミルトニアンへの最大独立集合(MIS)問題の自然な表現と、適切なグラフの着色を識別するためのブランチ・アンド・バウンド(BB)アプローチを組み合わせたものである。
提案手法では、グラフ表現は、クォービット相互作用(グラフの頂点を表すキュービット)から出現し、その色付けは、グラフの独立頂点の最大集合に1色を反復的に割り当て、ブランチ&バウンドアプローチで色数を最小化する。
我々は、実量子ハードウェアをIBM Power9ベースのクラスタにエミュレートし、32コア/ノードと256GB/ノードを持ち、MBI強化ライブラリを利用してBBQ-mISアルゴリズムの並列性を実装した。
このユースケースを考慮すると、有効なHPC-QC統合のための技術的要件と課題も特定できる。
以上の結果から,問題分解はグラフカラー化ソリューションの品質の観点からも有効であり,他の量子技術やアプリケーションに適用するための参考となる。
関連論文リスト
- Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。
フィードバック修正とコンフリクト解決を統合した階層的なフレームワークを使用して、$k$-coloringを実現しています。
提案手法を用いて、地下鉄の交通ネットワークのスケジューリングを最適化し、高い公平性を実証する。
論文 参考訳（メタデータ） (2025-04-30T05:45:15Z) - A quantum wire approach to weighted combinatorial graph optimisation problems [0.0]
本稿では,Rydberg-blockaded 原子の連鎖に基づく効率的な符号化方式を実験的に提案する。
中性原子アーキテクチャに最大重み付き独立集合(MWIS)と2次非制約二元最適化(QUBO)問題を埋め込む。
論文 参考訳（メタデータ） (2025-03-21T13:00:51Z) - Parallel Token Swapping for Qubit Routing [2.280359339174839]
現代の量子コンピュータでよく見られるグラフトポロジ上の並列トークンスワップ問題に対する最初の定数係数近似アルゴリズムを提供する。
また、量子ビットルーティング問題に対する再構成を設計する際に有用であることが示されている自然下界のいわゆる伸張係数についても検討した。
論文 参考訳（メタデータ） (2024-11-27T18:26:16Z) - Graph Algorithms with Neutral Atom Quantum Processors [31.546387965618333]
我々は中性原子量子処理ユニット(QPU)上で動作するグラフ問題に対する量子アルゴリズムの進歩を概観する。
最近導入された埋め込みと問題解決技術について論じる。
我々は、中性原子QPUのスケーラビリティ、制御可能性、繰り返し率の向上に重点を置いて、ハードウェアの継続的な進歩を明らかにした。
論文 参考訳（メタデータ） (2024-03-18T16:30:42Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。
本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。
今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
論文 参考訳（メタデータ） (2022-02-19T02:56:47Z) - Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
グラフ構造化データのための新しいハイブリッド量子古典アルゴリズムを提案し、これをEgo-graph based Quantum Graph Neural Network (egoQGNN)と呼ぶ。
egoQGNNはテンソル積とユニティ行列表現を用いてGNN理論フレームワークを実装し、必要なモデルパラメータの数を大幅に削減する。
このアーキテクチャは、現実世界のデータからヒルベルト空間への新しいマッピングに基づいている。
論文 参考訳（メタデータ） (2022-01-13T16:35:45Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Quantum Optimization for the Graph Coloring Problem with Space-Efficient
Embedding [0.0]
グラフ彩色問題に対する空間効率のよい量子最適化アルゴリズムを提案する。
我々の回路は標準的アプローチよりも深い。
現在利用可能な代替品を探索するために、量子アニール上でランダムなグラフ色付けの研究を行う。
論文 参考訳（メタデータ） (2020-09-15T18:34:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。