Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
arXiv:2504.08598 · doi:10.1088/2058-9565/ae3b6d
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 . 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.
18 pages, 10 figures
References in corpus (54)
- Quantum information with Rydberg atoms
- Probing many-body dynamics on a 51-atom quantum simulator
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Dipole Blockade and Quantum Information Processing in Mesoscopic Atomic Ensembles
- Adiabatic Quantum Computing
- Fast quantum gates for neutral atoms
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Observation of Rydberg blockade between two atoms
- Observation of collective excitation of two individual atoms in the Rydberg blockade regime
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Annealing and Analog Quantum Computation
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Experimental realization of a symmetry protected topological phase of interacting bosons with Rydberg atoms
- Quantum Kibble-Zurek mechanism and critical dynamics on a programmable Rydberg simulator
- High-fidelity parallel entangling gates on a neutral atom quantum computer
- Perspectives of quantum annealing: Methods and implementations
- Quantum computing with neutral atoms
- ARC: An open-source library for calculating properties of alkali Rydberg atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Controlling many-body dynamics with driven quantum scars in Rydberg atom arrays
- Rydberg atom quantum technologies
- Quantum simulation and computing with Rydberg-interacting qubits
- Barren Plateaus in Variational Quantum Computing
- Coloring random graphs
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Hybrid quantum-classical algorithms for approximate graph coloring
- Parallel low-loss measurement of multiple atomic qubits
- Mid-circuit measurements on a single species neutral alkali atom quantum processor
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Dispersive optical systems for scalable Raman driving of hyperfine qubits
- Quantum simulation of Ising spins on Platonic graphs
- Qubit-efficient encoding schemes for binary optimisation problems
- Rydberg blockade based parity quantum optimization
- Randomized Benchmarking using Non-Destructive Readout in a 2D Atom Array
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
- Quantum approximate optimization algorithm for qudit systems
- The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
- Practical Integer-to-Binary Mapping for Quantum Annealers
- Constrained quantum annealing of graph coloring
- Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
- Schedule path optimization for quantum annealing and adiabatic quantum computing
- Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
- Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
- Quantum pricing-based column-generation framework for hard combinatorial problems
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
- Rydberg-atom graphs for quadratic unconstrained binary optimization problems
- A Rydberg-atom approach to the integer factorization problem
- BBQ-mIS: a parallel quantum algorithm for graph coloring problems
- Integer Programming Using A Single Atom