Arxiv – Experimental determination of Ramsey numbers with quantum annealing (16 pages)

In an interview that I had with CTO Geordie Rose, he mentioned that published papers lag the actual work by about 2 years. Currently, Dwave Systems is working on their prototype 512 qubit chips which will be commercially available later in 2012.

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. It has found applications in mathematics, theoretical computer science, information theory, and classical error correcting codes. Ramsey numbers mark the threshold at which order first appears and are notoriously difficult to calculate due to their explosive rate of growth. Recently, a quantum algorithm has been proposed that calculates the two-color Ramsey numbers R(m, n). Here we present results of an experimental implementation of this algorithm based on quantum annealing and show that it correctly determines the Ramsey numbers R(3, 3) and R(m, 2) for 4 less than or equal to m less than or equal to 8. The R(8, 2) computation used

84 qubits of which 28 were computational qubits.This computation is the largest experimental implementation of a scientifically meaningful quantum algorithm that has been done to date.

*a) Layout of qubits and couplers. The chip architecture is a 4 × 4 array of unit cells, with each unit cell containing 8 qubits. Within a unit cell, each of the 4 qubits in the left-hand partition (LHP) connects to all 4 qubits in the right-hand partition (RHP), and vice versa. A qubit in the LHP (RHP) also connects to the corresponding qubit in the LHP (RHP) of the units cells above and below (to the left and right of) it. Qubits are labeled from 1 to 128, and edges between qubits represent couplers with programmable coupling strengths. Grey qubits indicate usable qubits, while white qubits indicate qubits that could not be calibrated to operating tolerances and were not used. All experiments were done on a chip with 106 usable qubits. (b) R(8, 2) embedding for qubit connectivity. Embedding used to compute R(8, 2) that produced the needed qubit couplings. In low energy states like-colored qubits have the same Bloch vector and constitute a single effective qubit. This allows an indirect coupling of qubits that are not directly coupled in hardware.*

MIT Technology Review has coverage

The most extensive quantum computation in history took just 270 milliseconds, say quantum physicists.

Their task was to calculate various so-called ‘two-colour Ramsey numbers’, exotic mathematical entities that are intimately connected with the emergence of order in disordered systems.

The famous example used to explain Ramsey numbers is the party problem which can be stated like this: how many people do you need to invite to a party to ensure that a subset of them, denoted ‘m’, will know each other and another subset of them, denoted ‘n’, will not know each other and so be forced to mingle. The required number, R(m,n), is a two colour Ramsey number.

These numbers are notoriously difficult to calculate. The mathematician Paul Erdos once said that if an alien species threatened to destroy the human race unless we could tell them the R(5,5) Ramsey number, our best bet would be to put humankind’s best minds to work on the problem, since we should have a chance of getting it.

But if the aliens asked for R(6,6), our best bet would be to launch an immediate all-out strike against the aliens since the calculation would be too difficult to contemplate.

The task is essentially a counting problem. The guests at the party can be thought of as nodes on a graph and their connections (or the absence of them) as edges. Calculating Ramsey numbers is really a question of counting the permutation of connections for a given number of guests.

But even for a small number of guests the permutations can be nhuge. For example, R(5,5) is still unknown, even today, although mathematicians think it lies between 43 and 49.

With the threat of alien extermination ringing in their ears, Bian and co have calculated R(3,3) and R(m,2) where m = 4, 5, 6, 7 and 8.

*If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks*