Ramsey numbers and adiabatic quantum computing

Details Ramsey numbers and adiabatic quantum computing Ramsey numbers and adiabatic quantum computing

2011-03-07

arxiv.org/abs/1103.1345v3

Phys. Rev. Lett. 108, 010501 (2012)

Physics

Quantum Physics

4 pages, 1 table, no figures, published version

Scientific paper

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. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for $5\leq s\leq 7$. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class QMA.

Affiliated with

Also associated with

No associations

Rating

Ramsey numbers and adiabatic quantum computing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ramsey numbers and adiabatic quantum computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ramsey numbers and adiabatic quantum computing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-607726