Qudit-inspired optimization for graph coloring

Abstract

We introduce a quantum-inspired algorithm for graph coloring problems (GCPs) that utilizes qudits in a product state, with each qudit representing a node in the graph and parameterized by d-dimensional spherical coordinates. We propose and benchmark two optimization strategies: qudit gradient descent, initiating qudits in random states and employing gradient descent to minimize a cost function, and qudit local quantum annealing, which adapts the local quantum annealing method to optimize an adiabatic transition from a tractable initial function to a problem-specific cost function. Our approaches are benchmarked against established solutions for standard GCPs, showing that our methods not only rival but frequently surpass the performance of recent state-of-the-art algorithms in terms of solution quality and computational efficiency. The adaptability of our algorithm and its high-quality solutions, achieved with minimal computational resources, point to an advancement in the field of quantum-inspired optimization, with potential applications extending to a broad spectrum of optimization problems.

12 pages, 7 figures

References in corpus (15)

• Ising formulations of many NP problems
• Barren plateaus in quantum neural network training landscapes
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Perspectives of quantum annealing: Methods and implementations
• Qudits and high-dimensional quantum computing
• A universal qudit quantum processor with trapped ions
• Phase Transitions in the Coloring of Random Graphs
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Annealing by simulating the coherent Ising machine
• Quantum Phase Estimation with Time-Frequency Qudits in a Single Photon
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Quantum approximate optimization algorithm for qudit systems
• Natural evolution strategies and variational Monte Carlo
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems

Cited by in corpus (3)

• Entanglement-assisted variational algorithm for discrete optimization problems
• Single photonic qutrit in a collective Rydberg polariton
• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians