Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array

• URL: http://arxiv.org/abs/2504.08598v1
• Date: Fri, 11 Apr 2025 14:55:35 GMT
• Title: Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Authors: Toonyawat Angkhanawin, Aydin Deger, Jonathan D. Pritchard, C. Stuart Adams,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neutral atom arrays have emerged as a versatile candidate for the embedding of hard classical optimization problems. Prior work has focused on mapping problems onto finding the maximum independent set of weighted or unweighted unit disk graphs. In this paper we introduce a new approach to solving natively-embedded vertex graph coloring problems by performing coherent annealing with Rydberg-qudit atoms, where different same-parity Rydberg levels represent a distinct label or color. We demonstrate the ability to robustly find optimal graph colorings for chromatic numbers up to the number of distinct Rydberg states used, in our case $k=3$. We analyze the impact of both the long-range potential tails and residual inter-state interactions, proposing encoding strategies that suppress errors in the resulting ground states. We discuss the experimental feasibility of this approach and propose extensions to solve higher chromatic number problems, providing a route towards direct solution of a wide range of real-world integer optimization problems using near-term neutral atom hardware.

Related papers

• 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. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring. 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)
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms [4.619601221994331]
  We study the problem of a maximum-weight independent set of unit-disk graphs using Rydberg excitation. We consider driving the quantum system of interacting atoms to the many-body ground state using a non-linear quasi-adiabatic profile for sweeping the Rydberg detuning. We also investigate the quantum phases of matter realizing commensurate and incommensurate phases in one- and two-dimensional spatial arrangements of the atomic array.
  arXiv  Detail & Related papers  (2024-05-16T04:23:17Z)
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts [0.0]
  We present demonstrations of solving maximum weighted independent set problems on a Rydberg atom array.<n>We verify the ability to prepare weighted graphs in 1D and 2D arrays.
  arXiv  Detail & Related papers  (2024-04-03T11:42:38Z)
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems [0.3562485774739681]
  We present an experimental demonstration of how the quadratic unconstrained binary optimization problem can be effectively addressed using Rydbergatom graphs. The Rydberg-atom graphs are configurations of neutral atoms into mathematical graphs facilitated by programmable optical tweezers.
  arXiv  Detail & Related papers  (2023-09-26T11:22:38Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  We propose a novel graph deep model with a non-gradient decision layer for graph mining. The proposed model has achieved state-of-the-art performance compared to the current models.
  arXiv  Detail & Related papers  (2022-07-18T04:34:08Z)
• 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)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• 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)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)

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.