January 12, 2012 weblog
Researchers conduct experimental implementation of quantum algorithm
In the research at D-Wave, those involved worked to run a just recently discovered quantum algorithm on an actual quantum computer; in this case, to solve for a two-color Ramsey number, R(m,2), where m= 4, 5, 6, 7 and 8, also known as the “Party Problem” because it’s use can be explained by posing a problem experienced by many party planners, i.e. how to invite the minimum number of guests where one group knows a certain number of others, and another group doesn’t, forcing just the right amount of mingling. Because increasing the number of different kinds of guests increases the difficulty of finding the answer, modern computers aren’t able to find R(5,5) much less anything higher. This is why researchers have turned to quantum computing, because instead of simply crunching through and counting all the possible permutations, such computers should conceivably be able to take advantage of a bit of quantum mechanics that allows superconducting circuits to recognize a 1 or 0 state as current traveling in opposite directions or even when both states exist at the same time.
Quantum algorithms take advantage of such facilities and allow for the execution of “instructions” far faster than conventional computers ever could. In the demonstration by the D-Wave team, the computer solved for a R(8,2) Ramsey number in just 270 milliseconds using 84 qubits, though just 28 of them were used in actual computation as the rest were delegated to correcting errors. Also, for those that are curious, the answer is 8.
While the fact that the team at D-Wave has managed to build and run an actual quantum computer is clearly impressive, less impressive is the fact that other than computing Ramsey numbers, the computers haven’t been found to be of much use for more practical applications. Others however, seem to think D-Wave is on to something as some big corporate names have partnered with them, and the company has even sold some of their quantum computers at $10 million a crack.
With such technology, as with many bright ideas in the past, nobody really knows whether computers of the future will all be ultra-speedy and highly efficient quantum computers, or simply faster versions of technology currently in use. We’ll all just have to wait and see how things unfold.
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 $4leq mleq 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.
via Arxiv Blog
© 2011 PhysOrg.com