Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Machine Intelligence

Mapping graph coloring to quantum annealing

CARLA VANESSA DA SILVA, Ana Aguiar, Priscila M. V. Lima, Inês Dutra

Published Nov 16, 2020• 22 citations
Publisher
DOI
10.1007/s42484-020-00028-4

Related papers

Quantum annealing of the graph coloring problem

Olawale Titiloye, Alan J. Crispin

Discrete Optimization•Jan 8, 2011•109 citations

Graph Coloring with a Distributed Hybrid Quantum Annealing Algorithm

Olawale Titiloye, Alan J. Crispin

Lecture notes in computer science•Jan 1, 2011•28 citations

Performance of quantum annealing under different Ising mappings and graph embeddings

Bryan O’Gorman, Eleanor Gilbert Rieffel, Davide Venturelli +1 more

Bulletin of the American Physical Society•Mar 4, 2014•0 citations

Efficient Hybridization of Quantum Annealing and Ant Colony Optimization for Coloring DIMACS Graph Instances

Arnab Kole, Anindya Jyoti Pal

Journal of Heuristics•Aug 2, 2025•3 citations

Localization in the Constrained Quantum Annealing of Graph Coloring

Kazue Kudo

Constrained quantum annealing (CQA) is a quantum annealing approach that is designed so that constraints are satisfied without penalty terms. There is an analogy between the model for the CQA of graph coloring and a set of disordered spin chains. In the model for the CQA of graph coloring, disorder corresponds to the fluctuation of effective local fields that increase in a CQA process. Numerical simulations of effective fields and entanglement demonstrate how localization appears in the CQA. Some notable features appear in the concurrence, which is a measure of entanglement, plotted as a function of the fluctuation of effective fields.

arXiv:1902.07888•Journal of the Physical Society of Japan•May 8, 2020•6 citations

Constrained quantum annealing of graph coloring

Kazue Kudo

We investigate a quantum annealing approach based on real-time quantum dynamics for graph coloring. In this approach, a driving Hamiltonian is chosen so that constraints are naturally satisfied without penalty terms and the dimension of the Hilbert space is considerably reduced. The total Hamiltonian, which consists of driving and problem Hamiltonians, resembles a disordered quantum spin chain. The ground state of the problem Hamiltonian for graph coloring is degenerate. This degeneracy is advantageous and is characteristic of this approach. Real-time quantum simulations in a small system demonstrate interesting results and provide some insight into quantum annealing.

arXiv:1806.05782•Physical Review A•Aug 1, 2018•31 citations
Constrained quantum annealing (CQA) is a quantum annealing approach that is designed so that constraints are satisfied without penalty terms. There is an analogy between the model for the CQA of graph coloring and a set of disordered spin chains. In the model for the CQA of graph coloring, disorder corresponds to the fluctuation of effective local fields that increase in a CQA process. Numerical simulations of effective fields and entanglement demonstrate how localization appears in the CQA. Some notable features appear in the concurrence, which is a measure of entanglement, plotted as a function of the fluctuation of effective fields.
We investigate a quantum annealing approach based on real-time quantum dynamics for graph coloring. In this approach, a driving Hamiltonian is chosen so that constraints are naturally satisfied without penalty terms and the dimension of the Hilbert space is considerably reduced. The total Hamiltonian, which consists of driving and problem Hamiltonians, resembles a disordered quantum spin chain. The ground state of the problem Hamiltonian for graph coloring is degenerate. This degeneracy is advantageous and is characteristic of this approach. Real-time quantum simulations in a small system demonstrate interesting results and provide some insight into quantum annealing.