A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation

• URL: http://arxiv.org/abs/2608.08694v1
• Date: Sun, 09 Aug 2026 13:15:12 GMT
• Title: A Resource-Efficient Quantum Framework for Graph Coloring and Chromatic Number Estimation
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many industrial optimization tasks can be modeled as graph coloring, where adjacent vertices must have different colors. This NP-hard problem is challenging for large graphs. We present a quantum encoding requiring qubits that scale logarithmically with the number of colors and linearly with vertices. Using adiabatic evolution with a novel mixer Hamiltonian and vertex terms, we compute the chromatic number and demonstrate robustness by solving constrained truck loading problems.

Related papers

• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design.<n>We propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs.<n>We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy.
  arXiv  Detail & Related papers  (2026-07-08T10:15:17Z)
• BBQ-mIS: a parallel quantum algorithm for graph coloring problems [0.11242503819703255]
  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.
  arXiv  Detail & Related papers  (2026-05-05T08:59:53Z)
• 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)
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array [0.0]
  We introduce a new approach to solving native-embedded graph coloring problems.<n>We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used.<n>We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems.
  arXiv  Detail & Related papers  (2025-04-11T14:55:35Z)
• Deep Prompt Tuning for Graph Transformers [55.2480439325792]
  Fine-tuning is resource-intensive and requires storing multiple copies of large models. We propose a novel approach called deep graph prompt tuning as an alternative to fine-tuning. By freezing the pre-trained parameters and only updating the added tokens, our approach reduces the number of free parameters and eliminates the need for multiple model copies.
  arXiv  Detail & Related papers  (2023-09-18T20:12:17Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• 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)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1. In the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation.
  arXiv  Detail & Related papers  (2021-11-17T12:16:57Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• 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)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.