Efficient hybrid variational quantum algorithm for solving graph coloring problem

• URL: http://arxiv.org/abs/2504.21335v1
• Date: Wed, 30 Apr 2025 05:45:15 GMT
• Title: Efficient hybrid variational quantum algorithm for solving graph coloring problem
• Authors: Dongmei Liu, Jian Li, Xiubo Cheng, Shibing Zhang, Yan Chang, Lili Yan,
• Abstract summary: 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.
• Score: 4.4739537033766705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• 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)
• Quantum Circuit Optimization by Graph Coloring [0.0]
  Depth optimization of a quantum circuit consisting of commuting operations is shown to be reducible to the vertex coloring problem in graph theory. The reduction immediately leads to an algorithm for circuit optimization of commuting gates utilizing any coloring solver.
  arXiv  Detail & Related papers  (2025-01-24T12:29:16Z)
• 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)
• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions.
  arXiv  Detail & Related papers  (2024-08-02T18:02:51Z)
• Qudit-inspired optimization for graph coloring [0.0]
  We introduce a quantum-inspired algorithm for graph coloring problems (GCPs)<n>We use qudits in a product state, with each qudit representing a node in the graph and parameterized by d-dimensional spherical coordinates.<n>We benchmark two optimization strategies: qudit gradient descent, initiating qudits in random states and employing gradient descent to minimize a cost function.
  arXiv  Detail & Related papers  (2024-06-02T16:19:55Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  We show how graph neural networks can be used to solve the canonical graph coloring problem. We frame graph coloring as a multi-class node classification problem and utilize an unsupervised training strategy.
  arXiv  Detail & Related papers  (2022-02-03T14:24:12Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.