Sep 27, 2013
Source:http://physicsworld.com/cws/article/news/2013/sep/27/has-a-quantum-computer-solved-the-party-problem
D-Wave's quantum party planner
A quantum computer made by the Canadian company D-Wave Systems has been used to solve a famous puzzle in mathematics known as the party problem – according to a team of physicists in Canada and the US that has done the work. D-Wave describes the result as one of the most significant achievements for its devices to date, but some physicists are being party poopers by remaining unconvinced there is anything to boast about.
Unlike classical computers, which store bits of information in definite values of 0 or 1, quantum computers store information in quantum bits (qubits) that exist as a fuzzy superposition of both. This mixed-up nature of quantum computing extends beyond individual qubits: multiple qubits can be entangled so that they work in unison. As a result, quantum computers should be able to solve certain problems – such as factorizing large numbers – much faster than their classical counterparts.
In principle, there are several ways that quantum computers can work. A more conventional approach is to perform a calculation by operating on the qubits one step at a time, so that in the final step the answer is encoded in the qubit states. Another way is called adiabatic quantum computing and involves letting all the qubits slowly evolve in carefully controlled conditions so that the problem is described by their web of interactions. Adiabatic quantum computing should still give the desired result in the final qubit states. However, when compared with more conventional approaches, it is less susceptible to external influences such as stray heat, which can destroy a quantum calculation.
Success and scepticism
Since 2004 D-Wave has been trying to build commercial adiabatic quantum computers with qubits made from superconducting rings. Founded in 1999 and based in the Vancouver suburb of Burnaby, the firm has published many results that it says provide evidence that its technology is capable of performing quantum calculations. D-Wave has supplied two of its computers to high-profile corporations, with one going to a consortium led by Google and the other going to the defence contractor Lockheed Martin. But despite this apparent success, there is still a significant amount of scepticism within the academic quantum-computing community about the company's claims.
D-Wave's latest results concern a well-known puzzle in mathematics about drawing up a guest list for a party. The party's organizer wants to invite the minimum number of people such that there is a group of m guests that know one another or another group of n guests that do not know one another. The British mathematician Frank Ramsey was the first to prove that there is always a minimum number of guests, R(m,n), satisfying the criteria, although calculating this can be tricky as the guest list grows. Showing that R(3,3) is equal to six is straightforward, but the number for R(5,5) is currently unknown and the number for R(6,6) is supposedly beyond any realistically achievable classical computation.
This latest work was done by William Macready and colleagues at D-Wave, together with mathematician Lane Clark at Southern Illinois University and physicist Frank Gaitan at the Laboratory for Physical Sciences in Maryland. The team claims to have used a D-Wave adiabatic quantum computer to determine the numbers for R(3,3) and R(m,2), with m ranging from four to eight. Although these numbers were already known, the researchers claim that their quantum algorithm, which relied on 84 qubits, had a much greater chance of finding them than a classical algorithm in the same time period. "To the best of our knowledge," the researchers write, "this is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm."
Mountains or molehills?
However, other researchers contacted by physicsworld.com were not convinced that D-Wave's computer had achieved anything remarkable. Mathematician Greg Kuperberg at the University of California, Davis, in the US says that adiabatic computing is a generic strategy and "could be great or lousy" depending on how it is implemented. The results are "beyond easy" with any traditional strategy, he says. "The paper talks of mountains, and then climbs a few molehills," he adds.
Colin Williams, director of business development and strategic partnerships at D-Wave, says there is "no question" of whether his company's devices are quantum computers. He points to recent tests on a D-Wave computer at the University of Southern California in Los Angeles, US, which suggested that the device did indeed have a quantum nature. "If people would read our papers, they would see there is no doubt whatsoever," he says.
One way D-Wave could convince sceptics is to make a discovery of an as-yet-unknown Ramsey number. According to Williams, the possibility of such a discovery may open up with a D-Wave computer containing 2048 qubits that is due to be released in 2015.
The research is published in Physical Review Letters.
Hamish Johnston, editor of physicsworld.com, visited D-Wave and interviewed its founder Geordie Rose. You can hear parts of that interview in the podcast "Quantum computing: Challenges, triumphs and applications", which also includes contributions from several leading academics who work on quantum computers.