New research brings claims of quantum computer maker into doubt

http://www.washingtonpost.com/national/health-science/new-research-brings-claims-of-quantum-computer-maker-into-doubt/2014/06/19/34999e92-f7dd-11e3-a3a5-42be35962a52_story.html?wprss=rss_homepage

Version 0 of 1.

Lockheed Martin bought the first one in 2011. Two years later, Google, NASA and the nonprofit Universities Space Research Association followed, pitching in together to launch a lab with their new $10 million-plus toy.

The machines from D-Wave Systems, the world’s only commercial quantum computer company, are clearly a hot-ticket item. But some of the company’s bold claims that the computer is thousands of times faster than a conventional PC have ruffled the feathers of academic quantum computing experts, who have been highly skeptical.

Now, new results released by the academic side may give weight to those doubts. An independent research group has found that the second-generation machine, D-Wave Two, shows no evidence of quantum speedup, a measure of how well a quantum computer is outperforming a conventional PC. The study was published online Thursday in the journal Science.

A quantum computer is any device that exploits quantum mechanics — the laws that govern the ultra-small — to run computations more efficiently. The idea of quantum computing was proposed by physicists in the 1980s, but the real boost in the field came from the discovery of Shor’s algorithm in the mid-1990s.

This algorithm can be used on a quantum computer to break the encryption used in most secure data transfer — for example, the kind used to encrypt your credit card information when you buy something online. A quantum computer with this particular capability — breaking broad encryption up to a million times faster than a classical machine — hasn’t been built yet, and it’ll be a decade or two longer before engineering catches up with theory.

Earlier this year, it was found in documents made public by former government contractor Edward Snowden that the National Security Agency is dumping millions of dollars into building its own quantum computer for encryption breaking.

The study published Thursday pitted Lockheed Martin’s D-Wave system against top-notch algorithms run on a conventional PC. The researchers used optimization problems — marketed as D-Wave’s specialty — which are similar to hunting for the lowest point of a vast landscape of hills and valleys.

In this case, the advantage supposedly comes from quantum tunneling, which allows burrowing through from one valley to another without having to travel tediously up and down every hill.

The team gradually ramped up the difficulty level of the problems and recorded how long it took for each system to solve them.

“When we just looked at the times — the boring question, basically — for some special problems, D-Wave was 10 times faster,” said study author and computational physicist Matthias Troyer of ETH Zurich. “For other problems, D-Wave was 100 times slower.”

But the bigger question of interest is how it will perform in the future, as the machine gets more and more upgrades. To answer this, researchers extrapolated for a greater number of quantum bits, or qubits, and looked for evidence of a performance boost known as quantum speedup.

Basically, it is a measure of how much faster a quantum computer can solve a problem as compared to a conventional one as the problems get harder. Quantum speedup will be detected if the quantumness of D-Wave Two allows it to outperform a PC as you scale up the machines and increase the number of qubits.

The team saw no traces of quantum speedup for D-Wave Two. Troyer emphasizes that there could be other types of problems that will show quantum speedup or perhaps some further fixes on the computer could help.

Jeremy Hilton, D-Wave’s vice president of processor development, said that the type of problem that Troyer used for benchmarking is one that you wouldn’t expect an advantage from adding quantumness.

“It’s important to consider multiple kinds of benchmarks,” Hilton said. “The problem type used [by Troyer] is really not the right problem type.”

The new findings are a far cry from previous test results, conducted by a consultant hired by D-Wave, which found that its machine was operating 3,600 times faster than a conventional algorithm. The results caused an initial wave of praise by the news media but was followed by a quick backlash of skepticism by quantum computing experts.

“People started to realize it was just a meaningless comparison,” said MIT theoretical computer scientist Scott Aaronson, who was not involved in the study. “When you make the comparison fair, the performance advantage for D-Wave essentially evaporates.”

He argues that the algorithms used by the consultant were far from ideal, in an effort to artificially hobble the PC and make D-Wave look more impressive.

That’s when Troyer stepped in and decided to set up a fair-comparison experiment with his optimized code. He had been conversing with people from D-Wave and in December 2012 shared his not-so-favorable findings with the company.

“They lost interest,” he said.

Hilton thinks that the backlash from academic naysayers is “unfortunate” and that D-Wave’s continued success can only help the quantum computing field gain more popularity and funding.

But experts remain unconvinced. Physicist Wim van Dam, who was not involved in the study, worries that D-Wave’s quick-and-dirty commercial approach — that may ultimately not work at all — could turn people off quantum computing for good.

“I worry that people will equate the two, D-Wave and quantum computing,” said van Dam, a professor at the University of California at Santa Barbara.

Aaronson concurs, although he notes that some of his academic colleagues agree with Hilton’s thoughts about D-Wave raising awareness of the field, despite some dubious claims.

The attitude of “ ‘Just shut up, and there’s money in it for all of us’ — I can understand it, but I can’t sympathize with it,” he said. “That’s a very dangerous game for academic scientists to be playing.”

Kim is a freelance science journalist based in Philadelphia.