Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909753000591360 |
|---|---|
| author | Vercellino, Chiara Naghmouchi, M. Yassine Coelho, Wesley Vitali, Giacomo Scionti, Alberto Viviani, Paolo Terzo, Olivier Montrucchio, Bartolomeo |
| author_facet | Vercellino, Chiara Naghmouchi, M. Yassine Coelho, Wesley Vitali, Giacomo Scionti, Alberto Viviani, Paolo Terzo, Olivier Montrucchio, Bartolomeo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18887 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem Vercellino, Chiara Naghmouchi, M. Yassine Coelho, Wesley Vitali, Giacomo Scionti, Alberto Viviani, Paolo Terzo, Olivier Montrucchio, Bartolomeo Quantum Physics 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. |
| title | Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.18887 |