3Q: Scott Aaronson on Google’s New Quantum-Computing Paper

In 2010, a Canadian company called D-Wave announced that it had begun production of what it called the world’s first commercial quantum computer, which was based on theoretical work done at MIT. Quantum computers promise to solve some problems significantly faster than classical computers — and in at least one case, exponentially faster. In 2013, a consortium including Google and NASA bought one of D-Wave’s machines.

Over the years, critics have argued that it’s unclear whether the D-Wave machine is actually harnessing quantum phenomena to perform its calculations, and if it is, whether it offers any advantages over classical computers. But this week, a group of Google researchers released a paper claiming that in their experiments, a quantum algorithm running on their D-Wave machine was 100 million times faster than a comparable classical algorithm.

Scott Aaronson, an associate professor of electrical engineering and computer science at MIT, has been following the D-Wave story for years. MIT News asked him to help make sense of the Google researchers’ new paper.

Q: The Google researchers’ paper focused on two algorithms: simulated annealing and quantum annealing. What are they?

A: Simulated annealing is one of the premier optimization methods that’s used today. It was invented in the early 1980s by direct analogy with what happens when people anneal metals, which is a 7,000-year-old technology. You heat the metal up, the atoms are all jiggling around randomly, and as you slowly cool it down, the atoms are more and more likely to go somewhere that will decrease the total energy.

In the case of an algorithm, you have a whole bunch of bits that start flipping between 1 and 0 willy-nilly, regardless of what that does to the solution quality. And then as you lower the “temperature,” a bit becomes more and more unwilling to flip in a way that would make the solution worse, until at the end, when the temperature is zero, a bit will only go to the value that keeps the solution going straight downhill — toward better solutions.

The main problem with simulated annealing, or for that matter with any other local-search method, is that you can get stuck in local optima. If you’re trying to reach the lowest point in some energy landscape, you can get stuck in a crevice that is locally the best, but you don’t realize that there’s a much lower valley somewhere else, if you would only go up and search. Simulated annealing tries to deal with that already: When the temperature is high, then you’re willing to move up the hill sometimes. But if there’s a really tall hill, even if it’s a very, very narrow hill — just imagine it’s a big spike sticking out of the ground — it could take you an exponential amount of time until you happen to flip so many bits that you happen to get over that spike.

In quantum mechanics, we know that particles can tunnel through barriers. (This is the language that the physicists use, which is a little bit misleading.) There’s an important 2002 paper by Farhi, Goldstone, and Gutmann, all of whom are here at MIT, and what they showed is that if your barrier really is a tall thin spike, then quantum annealing can give you an exponential speedup over classical simulated annealing. Classical annealing is going to get stuck at the base of that spike for exponential time, and quantum annealing is going to tunnel over it and get down to the global minimum in polynomial time.

Page 1 of 3

• Next Page >