Generalized Ramsey numbers through adiabatic quantum optimization

Ramsey theory is an active research area in combinatorics whose central theme is the emergence of order in large disordered structures, with Ramsey numbers marking the threshold at which this order first appears. For generalized Ramsey numbers r ( G ,  H ), the emergent order is characterized by gra...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2016-09, Vol.15 (9), p.3519-3542
Main Authors: Ranjbar, Mani, Macready, William G., Clark, Lane, Gaitan, Frank
Format: Article
Language:English
Subjects:
Adiabatic flow
Combinatorial analysis
Data Structures and Information Theory
Mathematical Physics
Optimization
Physics
Physics and Astronomy
Quantum Computing
Quantum Information Technology
Quantum Physics
Spintronics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Ramsey theory is an active research area in combinatorics whose central theme is the emergence of order in large disordered structures, with Ramsey numbers marking the threshold at which this order first appears. For generalized Ramsey numbers r ( G ,  H ), the emergent order is characterized by graphs G and H . In this paper we: (i) present a quantum algorithm for computing generalized Ramsey numbers by reformulating the computation as a combinatorial optimization problem which is solved using adiabatic quantum optimization; and (ii) determine the Ramsey numbers r ( T m , T n ) for trees of order m , n = 6 , 7 , 8 , most of which were previously unknown.
ISSN:1570-0755
1573-1332
DOI:10.1007/s11128-016-1363-3