Quantum computers are in danger of losing their lustre. These machines exploit the strange rules of quantum mechanics to carry out calculations that are vastly more powerful than anything that conventional computers can do.

Or so we’re told. Quantum computers in one form or another have been carrying out calculations for more than a decade. But far from putting conventional computers to shame, these devices have yet to outperform the calculating abilities of a primary school child.

Ten years ago, physicists used a quantum computer to factorise the number 15 using seven quantum bits or qubits. The result received great acclaim. Last year, they beat this record by factorising the number 143 using four qubits. Hardly a meteoric improvement.

But this dismal state of affairs may be finally changing with the announcement today of a calculation involving 84 qubits carried out by Zhengbing Bian at D-Wave Systems, a quantum computer manufacturer based in Vancouver, Canada, and a few mates.

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.

Their quantum computer uses qubits in the form of superconducting circuits in which 1s and 0s correspond to the currents travelling in opposite directions and the laws of quantum mechanics allow both states to exist simultaneously. So a single circuit can represent both a 0 and 1 at the same time.

What’s useful in this calculation is that whenever a solution occurs, it is the result of increasing the number of guests by one. So in R(3,3), parties with 1, 2, 3, 4, and 5 guests produce a null result. However, the dynamics of the problem change dramatically when their are 6 guests and this is straightforward to spot with the appropriate quantum algorithm.

Bian and co say the calculation for R(8,2) used 84 qubits, of which 28 were used in the computation and the rest for error correction. It took just 270 milliseconds. The result is 8 (as has been known for many years by conventional methods).

That’s an impressive result. Bian and co say “The R(8, 2) computation…to the best of our knowledge is the largest experimental implementation of a scientifically meaningful quantum algorithm.”

It’s also a vindication of kind for D-Wave Systems, the company that built this computer and markets a 128-qubit computer for $10 million.

The company’s approach to computing, known as adiabatic quantum computing, has been heavily criticised. Various physicists have said that the theory behind the machine is flawed and that the company has shown little evidence of the kind of improvement expected over classical computers.

Nevertheless, various companies have partnered with D-Wave Systems to further develop the approach, including Google and Lockheed Martin.

So it’ll be interesting to see whether this result quells the storm or fuels it.

Ref: arxiv.org/abs/1201.1842: Experimental Determination Of Ramsey Numbers With Quantum Annealing

Correction: this post was edited on 11 January to correct a typo in the formula for the calculated Ramsey numbers. Thanks ryuuguu