Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem

• URL: http://arxiv.org/abs/2508.18887v1
• Date: Tue, 26 Aug 2025 10:03:56 GMT
• Title: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem
• Authors: Chiara Vercellino, M. Yassine Naghmouchi, Wesley Coelho, Giacomo Vitali, Alberto Scionti, Paolo Viviani, Olivier Terzo, Bartolomeo Montrucchio,
• Abstract summary: Quantum Classical Branch-and-Price (QCBP) is a hybrid quantum-classical algorithm for the Vertex Coloring problem on neutral-atom Quantum Processing Units (QPUs)
• Score: 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.

Related papers

• Quantum-accelerated conjugate gradient methods via spectral initialization [0.0]
  A fault-tolerant quantum algorithm is used exclusively to construct a spectrally informed initial guess for a classical conjugate gradient (CG) solver.<n>A central feature of QACG is a controllable decomposition of the condition number between the quantum and the classical solver.<n>Results illustrate a concrete pathway toward the scientific and industrial use of early-stage fault-tolerant quantum computing.
  arXiv  Detail & Related papers  (2026-02-10T11:51:42Z)
• A scalable quantum-enhanced greedy algorithm for maximum independent set problems [0.0]
  We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set problem on regular graphs.<n>We implement the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes.
  arXiv  Detail & Related papers  (2026-01-29T16:14:48Z)
• Quantum-Enhanced Neural Contextual Bandit Algorithms [50.880384999888044]
  This paper introduces the Quantum Neural Tangent Kernel-Upper Confidence Bound (QNTK-UCB) algorithm.<n>QNTK-UCB is a novel algorithm that leverages the Quantum Neural Tangent Kernel (QNTK) to address these limitations.
  arXiv  Detail & Related papers  (2026-01-06T09:58:14Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [60.996803677584424]
  Variational Quantum Circuits (VQCs) offer a novel pathway for quantum machine learning.<n>Their practical application is hindered by inherent limitations such as constrained linear expressivity, optimization challenges, and acute sensitivity to quantum hardware noise.<n>This work introduces VQC-MLPNet, a scalable and robust hybrid quantum-classical architecture designed to overcome these obstacles.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  We introduce a comprehensive benchmarking framework designed to evaluate quantum optimization techniques against well-established NP-hard problems.<n>Our framework focuses on key problem classes, including the Multi-Dimensional Knapsack Problem (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP), and Market Share Problem (MSP)
  arXiv  Detail & Related papers  (2025-03-15T13:02:22Z)
• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  We demonstrate in this work how quantums with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems.<n>A key feature of our algorithm is it not only from the best solution returned by the quantum but from all solutions below a certain cost threshold.
  arXiv  Detail & Related papers  (2024-12-20T08:27:23Z)
• A clustering aggregation algorithm on neutral-atoms and annealing quantum processors [0.44531072184246007]
  This work presents a hybrid quantum-classical algorithm to perform clustering aggregation.<n>It is designed for neutral-atoms quantum computers and quantum annealers.<n>Findings suggest promising potential for future advancements in hybrid quantum-classical pipelines.
  arXiv  Detail & Related papers  (2024-12-10T14:48:44Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors [25.18520278107402]
  Quantum processing unit (QPU) has to satisfy highly demanding quantity and quality requirements on its qubits. Quantum circuit cutting techniques cut and distribute a large quantum circuit into multiple smaller subcircuits feasible for less powerful QPUs. Our tool, called ScaleQC, addresses the bottlenecks by developing novel algorithmic techniques.
  arXiv  Detail & Related papers  (2022-07-03T01:44:31Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.