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

PLoS ONE

Parameter Tuning Patterns for Random Graph Coloring with Quantum Annealing

Olawale Titiloye, Alan J. Crispin

Published Nov 14, 2012• 23 citations
Publisher

Abstract

Quantum annealing is a combinatorial optimization technique inspired by quantum mechanics. Here we show that a spin model for the k-coloring of large dense random graphs can be field tuned so that its acceptance ratio diverges during Monte Carlo quantum annealing, until a ground state is reached. We also find that simulations exhibiting such a diverging acceptance ratio are generally more effective than those tuned to the more conventional pattern of a declining and/or stagnating acceptance ratio. This observation facilitates the discovery of solutions to several well-known benchmark k-coloring instances, some of which have been open for almost two decades.

DOI
10.1371/journal.pone.0050060

Related papers

Optimization by quantum annealing for the graph colouring problem

Olawale Titiloye

Quantum annealing is the quantum equivalent of the well known classical simulated annealing algorithm for combinatorial optimization problems. Despite the appeal of the approach, quantum annealing algorithms competitive with the state of the art for specific problems hardly exist in the literature. Graph colouring is a difficult problem of practical significance that can be formulated as combinatorial optimization. By introducing a symmetry-breaking problem representation, and finding fast incremental techniques to calculate energy changes, a competitive graph colouring algorithm based on quantum annealing is derived. This algorithm is further enhanced by tuning simplification techniques; replica spacing techniques to increase robustness; and a messaging protocol, which enables quantum annealing to efficiently take advantage of multiprocessor environments. Additionally, observations of some patterns in the tuning for random graphs led to a more effective algorithm able to find new upper bounds for several widely-used benchmark graphs, some of which had resisted improvement in the last two decades.

•May 27, 2026•0 citations

Qudit-inspired optimization for graph coloring

David Jansen, Timothy Heightman, Luke Mortimer +2 more

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.

arXiv:2406.00792•Physical Review Applied•Dec 2, 2024•8 citations

Approximation Meets Quantum: A Parameterized Framework for Large-Scale Graph Coloring

Rahul Pitale, Kapil Tajane, Prashant Ahire +4 more

Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.

Asian Conference on Innovation in Technology (ASIANCON)•Aug 22, 2025•0 citations

Optimization by quantum annealing: Lessons from hard satisfiability problems

Demian A. Battaglia, Giuseppe E. Santoro, Erio Tosatti

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

arXiv:cond-mat/0502468•Physical Review E•Jun 29, 2005•107 citations

Reverse Quantum Annealing Assisted by Forward Annealing

Manpreet Singh Jattana

Quantum annealers conventionally use forward annealing to generate heuristic solutions. Reverse annealing can potentially generate better solutions but necessitates an appropriate initial state. Ways to find such states are generally unknown or highly problem dependent, offer limited success, and severely restrict the scope of reverse annealing. We use a general method that improves the overall solution quality and quantity by feeding reverse annealing with low-quality solutions obtained from forward annealing. An experimental demonstration of solving the graph coloring problem using the D-Wave quantum annealers shows that our method is able to convert invalid solutions obtained from forward annealing to at least one valid solution obtained after assisted reverse annealing for 57% of 459 random Erdos–Rényi graphs. Our method significantly outperforms random initial states, obtains more unique solutions on average, and widens the applicability of reverse annealing. Although the average number of valid solutions obtained drops exponentially with the problem size, a scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach of conventional forward annealing using reverse annealing.

arXiv:2408.13603•Quantum Reports•Aug 23, 2024•3 citations

Performance of quantum annealing inspired algorithms for combinatorial optimization problems

Qingguo Zeng, Xiaopeng Cui, Bowen Liu +3 more

Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.

Communications Physics•Jul 19, 2024•27 citations
Quantum annealing is a combinatorial optimization technique inspired by quantum mechanics. Here we show that a spin model for the k-coloring of large dense random graphs can be field tuned so that its acceptance ratio diverges during Monte Carlo quantum annealing, until a ground state is reached. We also find that simulations exhibiting such a diverging acceptance ratio are generally more effective than those tuned to the more conventional pattern of a declining and/or stagnating acceptance ratio. This observation facilitates the discovery of solutions to several well-known benchmark k-coloring instances, some of which have been open for almost two decades.
Quantum annealing is the quantum equivalent of the well known classical simulated annealing algorithm for combinatorial optimization problems. Despite the appeal of the approach, quantum annealing algorithms competitive with the state of the art for specific problems hardly exist in the literature. Graph colouring is a difficult problem of practical significance that can be formulated as combinatorial optimization. By introducing a symmetry-breaking problem representation, and finding fast incremental techniques to calculate energy changes, a competitive graph colouring algorithm based on quantum annealing is derived. This algorithm is further enhanced by tuning simplification techniques; replica spacing techniques to increase robustness; and a messaging protocol, which enables quantum annealing to efficiently take advantage of multiprocessor environments. Additionally, observations of some patterns in the tuning for random graphs led to a more effective algorithm able to find new upper bounds for several widely-used benchmark graphs, some of which had resisted improvement in the last two decades.
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 ddd-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.
Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
Quantum annealers conventionally use forward annealing to generate heuristic solutions. Reverse annealing can potentially generate better solutions but necessitates an appropriate initial state. Ways to find such states are generally unknown or highly problem dependent, offer limited success, and severely restrict the scope of reverse annealing. We use a general method that improves the overall solution quality and quantity by feeding reverse annealing with low-quality solutions obtained from forward annealing. An experimental demonstration of solving the graph coloring problem using the D-Wave quantum annealers shows that our method is able to convert invalid solutions obtained from forward annealing to at least one valid solution obtained after assisted reverse annealing for 57% of 459 random Erdos–Rényi graphs. Our method significantly outperforms random initial states, obtains more unique solutions on average, and widens the applicability of reverse annealing. Although the average number of valid solutions obtained drops exponentially with the problem size, a scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach of conventional forward annealing using reverse annealing.
Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.