Abstract | ||
---|---|---|
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 (, ), the emergent order is characterized by graphs and . 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 for trees of order , most of which were previously unknown. |
Year | DOI | Venue |
---|---|---|
2016 | https://doi.org/10.1007/s11128-016-1363-3 | Quantum Information Processing |
Keywords | Field | DocType |
Adiabatic quantum algorithms,Generalized Ramsey numbers,Tree Ramsey numbers,Ramsey theory,Combinatorial optimization,05C55,05D10,68Q12,81P68,90C27 | Adiabatic process,Ramsey theory,Discrete mathematics,Quantum,Graph,Quantum mechanics,Combinatorial optimization,Ramsey's theorem,Quantum algorithm,Computation,Physics | Journal |
Volume | Issue | ISSN |
15 | 9 | Quantum Inf. Process. 15, 3519 (2016) |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mani Ranjbar | 1 | 153 | 10.40 |
William G. Macready | 2 | 161 | 39.07 |
Lane H. Clark | 3 | 43 | 9.39 |
Frank Gaitan | 4 | 9 | 3.38 |