e-space
Manchester Metropolitan University's Research Repository

Parameter tuning patterns for random graph coloring with quantum annealing.

Titiloye, O and Crispin, A (2012) Parameter tuning patterns for random graph coloring with quantum annealing. PLoS One, 7 (11). ISSN 1932-6203

[img]
Preview

Available under License Creative Commons Attribution.

Download (333kB) | Preview

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.

Impact and Reach

Statistics

Downloads
Activity Overview
109Downloads
177Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

Edit Item Edit Item