e-space
Manchester Metropolitan University's Research Repository

Optimization by quantum annealing for the graph colouring problem

Titiloye, Olawale (2013) Optimization by quantum annealing for the graph colouring problem. Doctoral thesis (PhD), Manchester Metropolitan University.

Full text not available from this repository.

Abstract

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.

Impact and Reach

Statistics

Downloads
Activity Overview
0Downloads
76Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item