BBQ-mIS: a parallel quantum algorithm for graph coloring problems
arXiv:2605.03524 · doi:10.1109/QCE57702.2023.10198
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.
References in corpus (17)
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Sequential minimal optimization for quantum-classical hybrid algorithms
- A Tutorial on Formulating and Using QUBO Models
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Hybrid quantum-classical algorithms for approximate graph coloring
- Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
- Constrained quantum annealing of graph coloring
- Pulse based Variational Quantum Optimal Control for hybrid quantum computing
- Aquila: QuEra's 256-qubit neutral-atom quantum computer
- Application of Graph Coloring to Biological Networks
- Disorder-assisted graph coloring on quantum annealers
- Planning for Compilation of a Quantum Algorithm for Graph Coloring
- Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems