Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.00792 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929631626526720 |
|---|---|
| author | Jansen, David Heightman, Timothy Mortimer, Luke Perito, Ignacio Acín, Antonio |
| author_facet | Jansen, David Heightman, Timothy Mortimer, Luke Perito, Ignacio Acín, Antonio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00792 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Qudit-inspired optimization for graph coloring Jansen, David Heightman, Timothy Mortimer, Luke Perito, Ignacio Acín, Antonio Quantum Physics 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. |
| title | Qudit-inspired optimization for graph coloring |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2406.00792 |