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

arXiv:1806.05782 · Physical Review A

Constrained quantum annealing of graph coloring

Kazue Kudo

Published Aug 1, 2018• 31 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.98.022301

Related papers

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

Driver Hamiltonians for constrained optimization in quantum annealing

Itay Hen, M. S. Sarandy

One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.

arXiv:1602.07942•Physical Review A•Jun 13, 2016•59 citations

Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding

Zsolt Tabi, Kareem H. El-Safty, Zsofia Kallus +4 more

Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we also perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.

arXiv:2009.07314•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•68 citations

Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring

Lutfiana Sausan, Hyunsoo Lee

Quantum computing holds significant promise for solving NP-hard combinatorial problems by leveraging quantum properties such as superposition, entanglement, and interference. In this study, we apply Grover’s algorithm to a constrained scheduling problem modeled as a graph coloring task with an added complexity: ensuring that the total processing time of all jobs assigned to a machine does not exceed its capacity. This additional constraint increases the problem’s difficulty beyond traditional graph coloring. Our proposed quantum framework demonstrates the ability to generate valid schedules that satisfy both coloring and capacity constraint, highlighting the practical potential of quantum computing for addressing complex scheduling challenges.

Journal of Korean Institute of Industrial Engineers•Dec 15, 2025•0 citations

Quantum Annealing for Combinatorial Optimization with Time-Dependent Constraints

Jincheng Zhang

This paper investigates the application of quantum annealing to combinatorial optimization problems characterized by time-dependent constraints. Current quantum annealing algorithms often face limitations when dealing with such scenarios, necessitating adaptive approaches. We propose a novel quantum annealing algorithm incorporating a dynamic constraint solver. This solver allows the system to continuously monitor and adjust its solution trajectory based on the evolving nature of the constraints. The core mechanism involves encoding the problem into an appropriate Hamiltonian and utilizing the quantum annealing process to minimize the energy. We aim to broaden the applicability of quantum annealing beyond static constraint problems, offering a more robust solution for a wider range of real-world applications. The theoretical framework is presented, highlighting the key components and their interactions. We explore the potential advantages and challenges of this dynamic approach.

•Aug 29, 2026•0 citations

Disorder-assisted graph coloring on quantum annealers

Andrzej Więckowski, Sebastian Deffner, Bartłomiej Gardas

We are at the verge of a new era, which will be dominated by noisy intermediate-scale quantum devices. Prototypical examples for these new technologies are present-day quantum annealers. In the present work, we investigate to what extent static disorder generated by an external source of noise does not have to be detrimental, but can actually assist quantum annealers in achieving better performance. In particular, we analyze the graph coloring problem that can be solved on a sparse topology (i.e., chimera graph) via suitable embedding. We show that specifically tailored disorder can enhance the fidelity of the annealing process and thus increase the overall performance of the annealer.

arXiv:1903.07056•Physical Review A•Dec 3, 2019•11 citations
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.
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.
One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.
Current quantum computing devices have different strengths and weaknesses depending on their architectures. This means that flexible approaches to circuit design are necessary. We address this task by introducing a novel space-efficient quantum optimization algorithm for the graph coloring problem. Our circuits are deeper than the ones of the standard approach. However, the number of required qubits is exponentially reduced in the number of colors. We present extensive numerical simulations demonstrating the performance of our approach. Furthermore, to explore currently available alternatives, we also perform a study of random graph coloring on a quantum annealer to test the limiting factors of that approach, too.
Quantum computing holds significant promise for solving NP-hard combinatorial problems by leveraging quantum properties such as superposition, entanglement, and interference. In this study, we apply Grover’s algorithm to a constrained scheduling problem modeled as a graph coloring task with an added complexity: ensuring that the total processing time of all jobs assigned to a machine does not exceed its capacity. This additional constraint increases the problem’s difficulty beyond traditional graph coloring. Our proposed quantum framework demonstrates the ability to generate valid schedules that satisfy both coloring and capacity constraint, highlighting the practical potential of quantum computing for addressing complex scheduling challenges.
This paper investigates the application of quantum annealing to combinatorial optimization problems characterized by time-dependent constraints. Current quantum annealing algorithms often face limitations when dealing with such scenarios, necessitating adaptive approaches. We propose a novel quantum annealing algorithm incorporating a dynamic constraint solver. This solver allows the system to continuously monitor and adjust its solution trajectory based on the evolving nature of the constraints. The core mechanism involves encoding the problem into an appropriate Hamiltonian and utilizing the quantum annealing process to minimize the energy. We aim to broaden the applicability of quantum annealing beyond static constraint problems, offering a more robust solution for a wider range of real-world applications. The theoretical framework is presented, highlighting the key components and their interactions. We explore the potential advantages and challenges of this dynamic approach.
We are at the verge of a new era, which will be dominated by noisy intermediate-scale quantum devices. Prototypical examples for these new technologies are present-day quantum annealers. In the present work, we investigate to what extent static disorder generated by an external source of noise does not have to be detrimental, but can actually assist quantum annealers in achieving better performance. In particular, we analyze the graph coloring problem that can be solved on a sparse topology (i.e., chimera graph) via suitable embedding. We show that specifically tailored disorder can enhance the fidelity of the annealing process and thus increase the overall performance of the annealer.