Manchester Metropolitan University logo
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.

    Item Type: Article
    Peer-reviewed: Yes
    Date Deposited: 03 Mar 2017 09:38
    Publisher: Public library of Science
    Additional Information: This is an Open Access article published in PLoS One, published by Public Library of Science, copyright The Author(s).
    Divisions:
    Subject terms: Science & Technology, Multidisciplinary Sciences, Science & Technology - Other Topics, MULTIDISCIPLINARY SCIENCES, PHASE-TRANSITIONS, ALGORITHM, OPTIMIZATION, Monte Carlo Method, Temperature, Algorithms, Quantum Theory, Color, Models, Theoretical, Computer Graphics, Computer Simulation, Algorithms, Color, Computer Graphics, Computer Simulation, Models, Theoretical, Monte Carlo Method, Quantum Theory, Temperature, Algorithms, Color, Computer Graphics, Computer Simulation, Models, Theoretical, Monte Carlo Method, Quantum Theory, Temperature, MD Multidisciplinary, General Science & Technology
    URI: https://e-space.mmu.ac.uk/id/eprint/618085
    DOI: https://doi.org/10.1371/journal.pone.0050060
    ISSN 1932-6203

    Impact and Reach

    Statistics

    DownloadsShow export options
    Activity Overview
    6 month trend
    268Downloads
    6 month trend
    294Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record