\texttt{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 Halappanavar

Abstract

Picasso is a novel, memory-efficient parallel algorithm designed to solve massive graph coloring problems arising in quantum chemistry simulations. By employing "palette sparsification" and on-the-fly edge construction, Picasso can process graphs with over a trillion edges on a single commodity GPU. This approach achieves up to 68x memory savings and handles datasets nearly 50 times larger than current state-of-the-art tools while maintaining high coloring quality.

Introduction

In the field of quantum computing, simulating molecular Hamiltonians is a critical task. These Hamiltonians are typically represented as a large sum of "Pauli strings"—operators acting on qubits. To execute these simulations efficiently on near-term hardware, researchers must group these strings into the smallest possible set of "unitaries" that can be measured simultaneously.

Mathematically, this challenge is framed as a clique partitioning problem, which is equivalent to graph coloring on a complement graph. However, these graphs are exceptionally dense (often ~50% density) and scale rapidly ($O(N^4)$ to $O(N^8)$) with the number of basis functions. For complex molecules, the resulting graphs can contain trillions of edges, far exceeding the RAM of even high-end GPUs and CPUs.

Visualizing the transformation from Pauli strings to a colored conflict graph.

Methods

Picasso introduces a randomized, iterative approach with theoretical sublinear space guarantees. Its architecture is built on three primary pillars:

  1. Palette Sparsification: Rather than having every vertex consider every possible color, each vertex is assigned a small, random "palette" of candidate colors. This significantly reduces the number of potential conflicts that must be tracked in memory.
  2. Iterative Coloring: The algorithm attempts to color as many vertices as possible in a single pass. Vertices that remain uncolored due to conflicts are carried over to subsequent iterations with new palettes.
  3. On-the-fly Edge Construction: To bypass the memory bottleneck of storing trillion-edge graphs, Picasso uses a bit-encoding scheme for Pauli strings. By utilizing bitwise AND and popcount operations, the algorithm determines edge existence dynamically during the coloring process.
  4. ML-Driven Parameter Tuning: A Random Forest regressor is used to predict optimal values for palette size ($P$) and list size ($\alpha$), balancing coloring quality against computational resource usage.

Datasets and Scalability

The algorithm was evaluated using graphs derived from various molecular systems ($H_4, H_6, H_8, H_{10}$) across different spatial configurations and basis sets. These datasets range from small benchmarks to massive workloads previously considered impossible to process on a single node.

Molecular datasets and their corresponding graph scales.

As shown in the dataset summary, the largest instances involve over 2 million vertices and 1.1 trillion edges. Traditional adjacency list representations would be catastrophic for memory at this scale, necessitating Picasso's "compute-on-demand" approach.

Key Results

Picasso demonstrates unprecedented scalability and efficiency:

  • Massive Scale: It successfully colored a 1.1 trillion-edge graph in under 15 minutes using a single 40GB NVIDIA A100 GPU. Competing parallel colorers like Kokkos-EB or ECL-GC typically crashed on much smaller inputs.
  • Memory Gains: Picasso achieved up to 68x memory savings compared to the standard sequential library ColPack. It handled inputs with nearly 50x more vertices and over 2,400x more edges than existing GPU methods.
  • Performance: The GPU-accelerated version provided a ~16x speedup over its CPU-only counterpart, with specific steps like conflict graph construction seeing up to 60x acceleration.
  • Quality: In its "aggressive" optimization mode, the coloring quality remained within 5-10% of the best-known sequential heuristics, a negligible trade-off for the ability to process previously intractable datasets.

Conclusion

Picasso represents a significant leap in single-node processing for quantum chemistry. By proving that sublinear space algorithms are practically viable for dense graphs, the authors have opened new doors for simulating larger molecular systems. Future work will focus on extending Picasso to distributed multi-GPU environments to tackle "quadrillion-edge" problems and generalizing the palette-based approach to other domains like bioinformatics.

Summary updated

BibTeX
@inproceedings{ferdous2024texttt,
  author = {S. M. Ferdous and Reece Neff and Bo Peng and Salman Shuvo and Marco Minutoli and Sayak Mukherjee and Karol Kowalski and Michela Becchi and Mahantesh Halappanavar},
  title = {{\textbackslash\{\}texttt\{Picasso\}: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing}},
  booktitle = {IPDPS},
  year = {2024},
  doi = {10.1109/ipdps57955.2024.00029},
}
Figure