**Quantum Computer Passes Math Test, But Doesn’t Answer the Big Question**By Adam Mann10.02.1312:34 PMBy Adam Mann10.02.1312:34 PM

D-Wave Systems’ second-generation quantum computing device. Courtesy D-Wave Systems

Is the world’s first commercial quantum computer the real deal or not? No one is quite sure.

The most recent experiment adding fodder to this debate used the quantum computer made by the Canadian company D-Wave Systems to determine hard-to-calculate solutions in a mathematical field known as Ramsey theory. Despite the machine’s success, many scientists are still skeptical of this quantum computer’s legitimacy.

“At the moment, it’s not clear to my eyes that D-Wave device is what we would call a quantum computer,” said computer scientist Wim van Dam from the University of California, Santa Barbara, who was not involved in the recent work.

Quantum computers harness the weird quirks of the subatomic world to run algorithms at extremely quick speeds and solve problems that stymie our current electronic devices. That’s because classical computers rely on transistors that hold memory in the form of zeros and ones. A quantum computer, by contrast, uses subatomic particles (called qubits) that can be a one, a zero, or a simultaneous superposition of these two states.

Since the early 2000s, researchers have been able to build rudimentary quantum computers but it wasn’t until 2011 that D-Wave announced a commercial product with a 128-qubit processor. If it were truly a quantum computer, it would be leaps and bounds ahead of any other product, but the company’s statements have been met with raised eyebrows from the computer science community. Still, D-Wave sold its first products to companies such as Lockheed Martin while their second-generation device was bought up by Google and NASA.

The latest experiment used the D-Wave machine to find solutions to optimization problems in what is known as Ramsey theory, after British mathematician Frank Ramsey. This field deals with situations in which a certain kind of order appears within a disordered system.

A well-known problem called the “party problem” asks what the minimum number of guests you would need to invite to a gathering to ensure that a small subset is made of people who all know each other and another who all don’t. Solutions to this problem are given in what’s known as Ramsey numbers. Calculating the minimum number of guests to ensure groups of three strangers and three friends is fairly easy (the answer is six). But increasing the number of people makes the solution increasingly hard to calculate, with most Ramsey numbers being beyond the capability of our current computers.

D-Wave’s device was able to implement an algorithm to calculate Ramsey numbers for different configurations, though none that weren’t already known from previous work. The findings appeared Sept. 25 in Physical Review Letters.

While noting that the D-Wave experiment’s calculations were correct, the authors of a commentary piece in the same issue wrote that “many more tests would be needed to conclude that the logical elements are functioning as qubits and that the device is a real quantum computer.”

Graeme Smith and John Smolin from IBM’s Watson Research Center, the authors of the commentary, question just how coherent the qubits of D-Wave’s computer are. Coherence refers to how long the particles are able to remain in a state of superposition (where they are both zero and one simultaneously), which is notoriously tricky to maintain. Even small amounts of noise can cause the qubits’ quantum mechanical wavefunction to collapse, turning them into classical objects that don’t work like a true quantum computer.

But the algorithms used to calculate these Ramsey numbers “don’t need as much coherence as a full-blown quantum computer,” said physicist Frank Gaitan of the University of Maryland, who worked on the D-Wave experiment.

Gaitan adds that D-Wave’s machine is not necessarily a universal quantum computer, which could run any algorithm given to it. Instead, it is designed to be particularly good at solving optimization problems, such as those in Ramsey theory, and the evidence from his research shows that the device “uses some kind of quantum effect that solves some kind of problems.”

Even then, there is still some question as to whether D-Wave’s system is truly a quantum computer. Van Dam noted that Ramsey number problems aren’t a good choice for proving anything about quantum computers. That’s because “it’s a really easy problem,” he said.

He gave an analogy. Imagine a company says they built a self-driving car and then placed it on top of a hill. They start the car and it rolls to the bottom of the hill. You could say the car drove itself down or you could say it was carried downhill by gravity, and it might be hard to determine which one it is.

Gaitan hopes that future work will help clear up these problems. The current generation of D-Wave’s system can’t calculate any unknown Ramsey numbers. But their third-gen device, expected to come out in 2015, should have 2048 qubits, which would be enough to figure out new Ramsey numbers that are beyond the capability of current computers.

http://www.wired.com/wiredscience/2013/10/quantum-computer-ramsey/