Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2401.06713 · IEEE International Parallel and Distributed Processing Symposium (IPDPS)

Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing

S M Ferdous, Reece Neff, Bo Peng, Salman Shuvo, Marco Minutoli, Sayak Mukherjee, Karol Kowalski, Michela Becchi, Mahantesh M. Halappanavar

Published May 27, 2024• 3 citations
arXivHTMLPDF

Abstract

A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm’s parameters considering these trade-offs. We provide a sequential and parallel implementation of the proposed algorithm.We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68× memory savings. On massive datasets, we demonstrate that GPU-accelerated Picasso can process inputs with 49.5× more Pauli strings (vertex set in our graph) and 2,478× more edges than state-of-the-art parallel approaches.

DOI
10.1109/ipdps57955.2024.00029

Related papers

Approximation Meets Quantum: A Parameterized Framework for Large-Scale Graph Coloring

Rahul Pitale, Kapil Tajane, Prashant Ahire +4 more

Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.

Asian Conference on Innovation in Technology (ASIANCON)•Aug 22, 2025•0 citations

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

Chiara Vercellino, Giacomo Vitali, Paolo Viviani +5 more

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.

quant-pharXiv:2605.03524•IEEE International Conference on Quantum Computing and Engineering (QCE)•May 6, 2026•8 citations

Efficient hybrid variational quantum algorithm for solving graph coloring problem

Dongmei Liu, Li, Jian, Cheng, Xiubo +3 more

In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the $k$-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.

arXiv:2504.21335•Apr 30, 2025•2 citations

Quantum Walk-Based Algorithms for Graph Partitioning

Jincheng Zhang

Graph partitioning is a fundamental problem in computer science with applications in diverse fields, including image processing, network analysis, and VLSI design. Traditional graph partitioning algorithms often face significant computational challenges when dealing with large graphs, leading to exponential scaling of execution time. This paper investigates the application of quantum walk algorithms to address this challenge. We propose a framework leveraging quantum walks to explore different graph partitioning configurations, guided by a cost function that quantifies the quality of each partition. The core idea is to use the inherent parallelism of quantum walks to efficiently sample the partition space. The algorithm's performance is evaluated theoretically, aiming to demonstrate a potential speedup compared to classical approaches. This work lays a foundation for further research into quantum graph partitioning algorithms and explores the possibilities of harnessing quantum computing for optimization problems.

•Aug 28, 2026•0 citations

A Constrained Graph Coloring Solver Based on Ising Machines

Soma Kawakami, Yosuke Mukasa, Siya Bao +5 more

Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

International Conference on Consumer Electronics•Jan 6, 2023•3 citations

GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

Advith Desu, Aryan Namboodiri, Anil Prabhakar

Abstract The security of RSA rests on the hardness of factoring a semiprime N = PQ. We present an end-to-end pipeline that turns this into an optimization problem: factorization is mapped to a sparse Ising model whose lowest-energy spin configuration encodes the bits of P and Q. We solve this model on a single NVIDIA GH200 GPU using a graph-colored simulated annealer designed around the sparsity of the underlying coupling matrix. To maximize efficiency, we use graph coloring to let multiple spins update in parallel without breaking the energy bookkeeping along with optimal assignment of per spin energy calculation on the threads in the GPU to maximize efficiency. The annealer rarely lands exactly on the ground state but consistently gets close, and a guided post-processing search: wheel-sieve brute force, or Coppersmith’s lattice method closes the residual distance. The full pipeline reliably factors 128-bit semiprimes on a single GPU host.

•Sep 14, 2026•0 citations
A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm’s parameters considering these trade-offs. We provide a sequential and parallel implementation of the proposed algorithm.We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68× memory savings. On massive datasets, we demonstrate that GPU-accelerated Picasso can process inputs with 49.5× more Pauli strings (vertex set in our graph) and 2,478× more edges than state-of-the-art parallel approaches.
Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.
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.
In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the kkk-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve kkk-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
Graph partitioning is a fundamental problem in computer science with applications in diverse fields, including image processing, network analysis, and VLSI design. Traditional graph partitioning algorithms often face significant computational challenges when dealing with large graphs, leading to exponential scaling of execution time. This paper investigates the application of quantum walk algorithms to address this challenge. We propose a framework leveraging quantum walks to explore different graph partitioning configurations, guided by a cost function that quantifies the quality of each partition. The core idea is to use the inherent parallelism of quantum walks to efficiently sample the partition space. The algorithm's performance is evaluated theoretically, aiming to demonstrate a potential speedup compared to classical approaches. This work lays a foundation for further research into quantum graph partitioning algorithms and explores the possibilities of harnessing quantum computing for optimization problems.
Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
Abstract The security of RSA rests on the hardness of factoring a semiprime N = PQ. We present an end-to-end pipeline that turns this into an optimization problem: factorization is mapped to a sparse Ising model whose lowest-energy spin configuration encodes the bits of P and Q. We solve this model on a single NVIDIA GH200 GPU using a graph-colored simulated annealer designed around the sparsity of the underlying coupling matrix. To maximize efficiency, we use graph coloring to let multiple spins update in parallel without breaking the energy bookkeeping along with optimal assignment of per spin energy calculation on the threads in the GPU to maximize efficiency. The annealer rarely lands exactly on the ground state but consistently gets close, and a guided post-processing search: wheel-sieve brute force, or Coppersmith’s lattice method closes the residual distance. The full pipeline reliably factors 128-bit semiprimes on a single GPU host.