Friday, December 11, 2015

So You Think Your Computer Is Fast? Update on Google, D-Wave and the Quantum Computer

Following up on Tuesday's "Google says it has now proven that D-Wave’s quantum computer really works (GOOG)".
From MIT's Technology Review:

Google Says It Has Proved Its Controversial Quantum Computer Really Works
Inside this box is a superconducting chip, cooled to within a fraction of a degree of 
absolute zero, that might put new power behind artificial-intelligence software.
Researchers from Google’s AI Lab say a controversial quantum machine that it and NASA have been testing since 2013 resoundingly beat a conventional computer in a series of tests.  

Google says it has proof that a controversial machine it bought in 2013 really can use quantum physics to work through a type of math that’s crucial to artificial intelligence much faster than a conventional computer.

Governments and leading computing companies such as Microsoft, IBM, and Google are trying to develop what are called quantum computers because using the weirdness of quantum mechanics to represent data should unlock immense data-crunching powers. Computing giants believe quantum computers could make their artificial-intelligence software much more powerful and unlock scientific leaps in areas like materials science. NASA hopes quantum computers could help schedule rocket launches and simulate future missions and spacecraft. “It is a truly disruptive technology that could change how we do everything,” said Rupak Biswas, director of exploration technology at NASA’s Ames Research Center in Mountain View, California.

Biswas spoke at a media briefing at the research center about the agency’s work with Google on a machine the search giant bought in 2013 from Canadian startup D-Wave systems, which is marketed as “the world’s first commercial quantum computer.” The computer is installed at NASA’s Ames Research Center in Mountain View, California, and operates on data using a superconducting chip called a quantum annealer. A quantum annealer is hard-coded with an algorithm suited to what are called “optimization problems,” which are common in machine-learning and artificial-intelligence software.

However, D-Wave’s chips are controversial among quantum physicists. Researchers inside and outside the company have been unable to conclusively prove that the devices can tap into quantum physics to beat out conventional computers.

Hartmut Neven, leader of Google’s Quantum AI Lab in Los Angeles, said today that his researchers have delivered some firm proof of that. They set up a series of races between the D-Wave computer installed at NASA against a conventional computer with a single processor. “For a specific, carefully crafted proof-of-concept problem we achieve a 100-million-fold speed-up,” said Neven.
Google posted a research paper describing its results online last night, but it has not been formally peer-reviewed. Neven said that journal publications would be forthcoming.

Google’s results are striking—but even if verified, they would only represent partial vindication for D-Wave. The computer that lost in the contest with the quantum machine was running code that had it solve the problem at hand using an algorithm similar to the one baked into the D-Wave chip. An alternative algorithm is known that could have let the conventional computer be more competitive, or even win, by exploiting what Neven called a “bug” in D-Wave’s design. Neven said the test his group staged is still important because that shortcut won’t be available to regular computers when they compete with future quantum annealers capable of working on larger amounts of data.

Matthias Troyer, a physics professor at the Swiss Federal Institute of Technology, Zurich, said making that come true is crucial if chips like D-Wave’s are to become useful. “It will be important to explore if there are problems where quantum annealing has advantages over even the best classical algorithms, and to find if there are classes of application problems where such advantages can be realized,” he said, in a statement with two colleagues. 

Last year Troyer’s group published a high-profile study of an earlier D-Wave chip that concluded it didn’t offer advantages over conventional machines. That question has now been partially resolved, they say. “Google’s results indeed show a huge advantage on these carefully chosen instances.”...MORE
HT: Victor Niederhoffer's Daily Speculation's who asks:
How will this change the trading business?
Good question. 
It means nothing at the moment, it's only annealing, but this is a big step.

Here's the Google paper at arXive:

What is the Computational Value of Finite Range Tunneling?