BBQ-mIS: a parallel quantum algorithm for graph coloring problems

• URL: http://arxiv.org/abs/2605.03524v1
• Date: Tue, 05 May 2026 08:59:53 GMT
• Title: BBQ-mIS: a parallel quantum algorithm for graph coloring problems
• Abstract summary: We propose a hybrid quantum-classical algorithm, i.e., BBQ-mIS, to solve graph coloring problems on Rydberg atoms quantum machines.<n>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.
• Score: 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.

Related papers

• A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation [0.0]
  We present a quantum encoding requiring qubits that scale logarithmically with the number of colors and linearly with vertices.<n>We demonstrate robustness by solving constrained truck loading problems.
  arXiv  Detail & Related papers  (2026-08-09T13:15:12Z)
• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  This paper proposes a hybrid variational quantum algorithm to solve the $k$-coloring problem of graph vertices.<n>We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring.<n>We apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
  arXiv  Detail & Related papers  (2025-04-30T05:45:15Z)
• A quantum wire approach to weighted combinatorial graph optimisation problems [0.0]
  We present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms.<n>We embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture.
  arXiv  Detail & Related papers  (2025-03-21T13:00:51Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Parallel Token Swapping for Qubit Routing [2.280359339174839]
  We provide the first known constant factor approximation algorithms for the parallel token swapping problem on graph topologies that are commonly found in modern quantum computers.<n>We also study the so-called stretch factor of a natural lower bound to the problem, which has been shown to be useful when designing reconfigurations for the qubit routing problem.
  arXiv  Detail & Related papers  (2024-11-27T18:26:16Z)
• Graph Algorithms with Neutral Atom Quantum Processors [31.546387965618333]
  We review the advancements in quantum algorithms for graph problems running on neutral atom Quantum Processing Units (QPUs) We discuss recently introduced embedding and problem-solving techniques. We clarify ongoing advancements in hardware, with an emphasis on enhancing the scalability, controllability and repetition rate of neutral atom QPUs.
  arXiv  Detail & Related papers  (2024-03-18T16:30:42Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
  We propose a novel hybrid quantum-classical algorithm for graph-structured data, which we refer to as the Ego-graph based Quantum Graph Neural Network (egoQGNN) egoQGNN implements the GNN theoretical framework using the tensor product and unity matrix representation, which greatly reduces the number of model parameters required. The architecture is based on a novel mapping from real-world data to Hilbert space.
  arXiv  Detail & Related papers  (2022-01-13T16:35:45Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding [0.0]
  We introduce a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. To explore currently available alternatives, we perform a study of random graph coloring on a quantum annealer.
  arXiv  Detail & Related papers  (2020-09-15T18:34:17Z)

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.