Fetching the paper…

Reading the bibliography…

Ramsey numbers and adiabatic quantum computing · Around

2011

Ramsey numbers and adiabatic quantum computing

Gaitan, Frank, Clark, Lane

Original
PDF
Post on X

Understand

The graph-theoretic Ramsey numbers are notoriously difficult to calculate.

In fact, for the two-color Ramsey numbers $R(m,n)$ with $m,n\geq 3$, only nine are currently known.
We present a quantum algorithm for the computation of the Ramsey numbers $R(m,n)$.
We show how the computation of $R(m,n)$ can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution.

Built on

A. W. Goodman, Amer. Math. Monthly 66
1959
Earlier work this paper cites.
J. Paris, L. Harrington, in Handbook of Mathematical Logic
1977
Earlier work this paper cites.
H. Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory
1981
Earlier work this paper cites.
J. Ketonen and R. Solovay, Ann. Math. 113
1981
Earlier work this paper cites.
R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey Theory
1990
Earlier work this paper cites.
L. H. Clark, J. Graph Theory 16
1992
Earlier work this paper cites.
J. Spencer, Ten Lectures on the Probabilistic Method
1994
Earlier work this paper cites.

Similar

J. Nes̆etr̆il, in Handbook of Combinatorics
1995
Cited alongside, same era.
B. Bollobás, Modern Graph Theory
1998
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, 2000, available at arXiv.org:quant-ph/0001106v1
2000
Cited alongside, same era.
A. Y. Kitaev, A. H. Shen, M. N. Vyalyi, Classical and Quantum Computation
2000
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, D. Preda, Science 292
2001
Cited alongside, same era.
M. Steffen, W. van Dam, T. Hogg, G. Breyta, I. Chuang, Phys. Rev. Lett. 90
2003
Cited alongside, same era.

Then

F. Gaitan, Int. J. Quantum Info. 4
2006
Later among the works it cites.
J. Kempe, A. Kitaev, O. Regev, SIAM J. Comput. 35
2006
Later among the works it cites.
R. Oliveira, B. M. Terhal, Quant. Info. Comp. 8
2008
Later among the works it cites.
S. P. Jordan, E. Farhi, Phys. Rev. A 77
2008
Later among the works it cites.
X. Peng et al., Phys. Rev. Lett. 101
2008
Later among the works it cites.
F. Gaitan, Complexity 14
2009
Later among the works it cites.
R. Harris et al., Phys. Rev. B 82
2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

V. Rosta, Electronic J. Combinatorics

2004

Cited alongside, same era.