December 10, 2015 weblog
Google's researchers explore quantum annealing advantages
Since 2013, Google and NASA have worked on code designed for a quantum machine bought from D-Wave. Google Research Blog said Tuesday that Quantum AI lab researchers report in a new paper that has yet to be peer-reviewed that the machine can perform quantum computing operations.
The machine beat—resoundingly—a conventional computer in tests, said Tom Simonite in MIT Technology Review.
Puiu said the paper was published online by Google but has yet to pass peer-review.
"What is the Computational Value of Finite Range Tunneling?" is on the arXiv and authors are Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis and Hartmut Neven.
The D-Wave machine is capable of performing a limited set of tasks; it's not a universal quantum computer, according to ZME Science. The machine can run code 100 million times faster than a conventional single-core processor, he said, but only for specific problems.
"Google and NASA announced that the D-Wave computer can actually walk the talk for some highly specialized workloads known as annealing," he said in ZME Science. "In a face to face stand-off, the researchers used simulated annealing on a conventional processor, and quantum annealing on the D-Wave machine. For this particular workload, the D-Wave computer was able to solve the problem 100 million times faster."
Simonite said the machine "really can use quantum physics to work through a type of math that's crucial to artificial intelligence much faster than a conventional computer."
Simonite said that D-Wave's chips are controversial among quantum physicists; researchers have been unable to prove conclusively that the devices can tap into quantum physics to beat out conventional computers. Nonetheless, "For a specific, carefully crafted proof-of-concept problem we achieve a 100-million-fold speed-up," said Neven, one of the co-authors of the paper, in MIT Technology Review.
Neven, Director of Engineering, provided some background for the news; he also wrote about the work on the Google Research Blog on Tuesday.
"During the last two years, the Google Quantum AI team has made progress in understanding the physics governing quantum annealers. We recently applied these new insights to construct proof-of-principle optimization problems and programmed these into the D-Wave 2X quantum annealer that Google operates jointly with NASA."
What they hoped to demonstrate: quantum annealing, wrote Neven, can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes.
Simonite talked about what quantum annealer means. The computer installed at the Ames center in Mountain View operates on data using a superconducting chip called a quantum annealer and the annealer is hard-coded with an algorithm suited to optimization problems, common in machine-learning and artificial-intelligence software.
Jacob Aron in New Scientist explained it further:
"D-Wave's computer is a specialized device called a quantum annealer, which works by exploring an energy landscape of hills and valleys that corresponds to the problem it is trying to solve. The goal is to reach the lowest point on this landscape, which corresponds to the best solution. A property called quantum tunneling allows the D-Wave to traverse this landscape more quickly by "tunneling" through the hills, thus theoretically letting it reach an answer faster."
Neven wrote in the blog: "We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 108 times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 108."
In the bigger picture, Simonite remarked that "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." He quoted Rupak Biswas, director of exploration technology at NASA's Ames Research Center. "It is a truly disruptive technology that could change how we do everything," said Biswas.
In that context, it is understandable that the paper on arXiv will draw not only interest but conversation. New Scientist's headline on Wednesday was "Experts doubt Google's claim about its quantum computer's speed."
"This is certainly the most impressive demonstration so far of the D-Wave machine's capabilities," said Scott Aaronson at MIT. "And yet, it remains totally unclear whether you can get to what I'd consider 'true quantum speedup' using D-Wave's architecture." Aaronson, the author of Quantum Computing Since Democritus, wrote in his own blog, "while there's been genuine, interesting progress, it remains uncertain whether D-Wave's approach will lead to speedups over the best known classical algorithms, let alone to speedups over the best known classical algorithms that are also asymptotic or also of practical importance."
2. What is the Computational Value of Finite Range Tunneling? arXiv:1512.02206 [quant-ph] arxiv.org/abs/1512.02206
Quantum annealing (QA) has been proposed as a quantum enhanced optimization heuristic exploiting tunneling. Here, we demonstrate how finite range tunneling can provide considerable computational advantage. For a crafted problem designed to have tall and narrow energy barriers separating local minima, the D-Wave 2X quantum annealer achieves significant runtime advantages relative to Simulated Annealing (SA). For instances with 945 variables this results in a time-to-99%-success-probability that is ∼108 times faster than SA running on a single processor core. We also compared physical QA with Quantum Monte Carlo (QMC), an algorithm that emulates quantum tunneling on classical processors. We observe a substantial constant overhead against physical QA: D-Wave 2X runs up to ∼108 times faster than an optimized implementation of QMC on a single core. To investigate whether finite range tunneling will also confer an advantage for problems of practical interest, we conduct numerical studies on binary optimization problems that cannot yet be represented on quantum hardware. For random instances of the number partitioning problem, we find numerically that QMC, as well as other algorithms designed to simulate QA, scale better than SA and better than the best known classical algorithms for this problem. We discuss the implications of these findings for the design of next generation quantum annealers.
© 2015 Tech Xplore