論文の概要: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem

• arxiv url: http://arxiv.org/abs/2508.18887v1
• Date: Tue, 26 Aug 2025 10:03:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-27 17:42:38.794226
• Title: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem
• Title（参考訳）: 垂直色問題に対するハイブリッド量子-古典分枝・価格法
• Authors: Chiara Vercellino, M. Yassine Naghmouchi, Wesley Coelho, Giacomo Vitali, Alberto Scionti, Paolo Viviani, Olivier Terzo, Bartolomeo Montrucchio,
• Abstract要約: 量子古典ブランチ・アンド・プライス(Quantum Classical Branch-and-Price、QCBP)は、中性原子量子処理ユニット(QPU)上の頂点色問題に対するハイブリッド量子古典アルゴリズムである。
• 参考スコア（独自算出の注目度）: 0.11242503819703255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces Quantum Classical Branch-and-Price (QCBP), a hybrid quantum-classical algorithm for the Vertex Coloring problem on neutral-atom Quantum Processing Units (QPUs). QCBP embeds quantum computation within the classical Branch-and-Price (BP) framework to address three bottlenecks in classical BP algorithms: the computational cost of Pricing Subproblems (PSPs), branching efficiency, and the quality of primal heuristics. It uses quantum-assisted Column Generation (CG) based on Quantum Adiabatic Algorithms (QAA) to sample high-quality maximum-weight independent sets (MWIS), reducing the need to repeatedly solve NP-hard PSPs. The adapted branching strategy leverages quantum-generated independent sets to explore fewer nodes, tighten lower bounds, and converge faster. A classical primal heuristic rapidly builds feasible solutions from quantum-generated sets, avoiding unnecessary quantum calls or additional Integer Linear Programming (ILP) solves. Compared with our prior Hybrid Column Generation (HCG) and Branch-and-Bound through maximal Independent Set (BBQ-mIS), QCBP improves both quantum-resource utilization and solution quality. Extensive experiments show QCBP significantly outperforms HCG and BBQ-mIS, reaching optimality on $\approx 98\%$ of benchmark instances. Preliminary validation on real neutral-atom hardware indicates robustness to quantum noise and hardware constraints, supporting practical applicability and scalability to larger graph instances. QCBP emerges as a viable hybrid method for combinatorial optimization with promising scalability on near-term quantum hardware.
• Abstract（参考訳）: 本稿では、中性原子量子処理ユニット(QPU)上での頂点色問題に対するハイブリッド量子古典的アルゴリズムである量子古典分枝行列(QCBP)を紹介する。 QCBPは古典的なブランチ・アンド・プライス(BP)フレームワークに量子計算を組み込んで、古典的なBPアルゴリズムの3つのボトルネックに対処する。 量子断熱アルゴリズム(QAA)に基づく量子補助カラム生成(CG)を用いて、高品質の最大重み付き独立集合(MWIS)をサンプリングし、NPハードPSPを繰り返す必要を減らした。 適応された分岐戦略は、量子生成独立集合を利用してより少ないノードを探索し、より低い境界を締め付け、より早く収束させる。 古典的原始ヒューリスティックは、不要な量子呼び出しや追加の整数線形計画法(ILP)を回避して、量子生成集合から実現可能な解を迅速に構築する。 従来のHybrid Column Generation (HCG) や Branch-and-Bound を最大独立集合 (BBQ-mIS) で比較すると,QCBP は量子リソース利用とソリューション品質の両方を改善している。 大規模な実験により、QCBPはHCGとBBQ-mISを大きく上回り、ベンチマークインスタンスの$98\%で最適な結果を得た。 実際の中性原子ハードウェアに対する予備的な検証は、量子ノイズやハードウェアの制約に対する堅牢性を示し、より大きなグラフインスタンスへの実用的な適用性とスケーラビリティをサポートする。 QCBPは、短期量子ハードウェア上で有望なスケーラビリティを備えた組合せ最適化のための実行可能なハイブリッド手法として出現する。

関連論文リスト

• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [60.996803677584424]
  変分量子回路(VQC)は、量子機械学習のための新しい経路を提供する。 それらの実用的応用は、制約付き線形表現性、最適化課題、量子ハードウェアノイズに対する鋭敏感といった固有の制限によって妨げられている。 この研究は、これらの障害を克服するために設計されたスケーラブルで堅牢なハイブリッド量子古典アーキテクチャであるVQC-MLPNetを導入している。
  論文  参考訳（メタデータ） (2025-06-12T01:38:15Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。 本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
  論文  参考訳（メタデータ） (2025-03-15T13:02:22Z)
• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。 我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
  論文  参考訳（メタデータ） (2024-12-20T08:27:23Z)
• A clustering aggregation algorithm on neutral-atoms and annealing quantum processors [0.44531072184246007]
  本研究では、クラスタリングアグリゲーションを実行するためのハイブリッド量子古典アルゴリズムを提案する。 中立原子の量子コンピュータと量子アニールのために設計された。 発見は、ハイブリッド量子古典パイプラインの将来的な発展の可能性を示唆している。
  論文  参考訳（メタデータ） (2024-12-10T14:48:44Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる 本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。 その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
  論文  参考訳（メタデータ） (2022-09-01T17:08:41Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。 本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。 古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
  論文  参考訳（メタデータ） (2022-08-29T15:24:03Z)
• ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors [25.18520278107402]
  量子処理ユニット(QPU)は、その量子ビットの要求量と品質の要求を満たす必要がある。 量子回路切断技術は、より強力なQPUを実現するために、大きな量子回路を複数の小さなサブ回路に切断して分散する。 われわれのツールはScaleQCと呼ばれ、新しいアルゴリズム技術を開発することでボトルネックに対処する。
  論文  参考訳（メタデータ） (2022-07-03T01:44:31Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。 QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。 数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
  論文  参考訳（メタデータ） (2020-10-20T12:06:27Z)

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

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