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

    Activity Overview
    6 month trend
    246Downloads
    6 month trend
    281Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record