by Chris Lee - July 1 2013, 9:00pm
Wikimedia Commons
Quantum optimizer manufacturer D-Wave Systems has been gaining a lot of traction recently. They've sold systems to Lockheed Martin and Google, and started producing results showing that their system can solve problems that are getting closer to having real-life applications. All in all, they have come a long way since the first hype-filled announcement.
Over time, my skepticism has waxed and waned. Although I didn't really trust their demonstrations, D-Wave's papers, which usually made more limited claims, seemed pretty solid. Now, there is a new data point to add to the list, with a paper claiming to show that the D-Wave machine cannot be doing classical simulated annealing.
Once again in English, please
Annealing is a process where you carefully and slowly allow a physical system to relax. As it's relaxing, it will carefully arrange itself so that it has the lowest possible amount of energy, called the ground state.
An example of this is a set of magnets. Each magnet can arrange itself so that it is either pointing up or down. At high temperatures (in other words, way above the ground state), each magnet arranges itself randomly, either pointing up or down. And, because the energy difference between the two states is small, they flip up and down in response to tiny changes in the local magnetic field (caused by neighboring magnets flipping).
As the magnets are cooled down, the rate of flipping slows down; however, as that occurs, the influence of the direction of the neighboring magnets becomes more substantial. In this case, where the only magnetic field is due to the magnets themselves, they start to pair up to minimize their total joint energy and reduce the total magnetic field to zero. That is, each magnet tries to minimize its energy with respect to its surroundings.
This process, called annealing, can also be simulated using a computer, and is a pretty nice way to solve some very complicated problems. But simulated annealing is, in principle, no faster than any other classical mechanism for calculating solutions to problems—although it may be more convenient to implement and optimize, and be faster in practice.
The relevance to D-Wave?
D-Wave's computer pretty much does this. They use superconducting loops to generate tiny individual magnets where the orientation depends on the direction in which the current circulates. These tiny magnets are coupled to each other so that their orientations influence each other.
To solve a problem with this bunch of magnets, however, you need to rewrite the problem so that its solution is the magnets' lowest energy state. To get there, the magnet's orientations are initialized in a well understood way, and the system is placed in the ground state for that configuration. Slowly, the environment around the magnets and coupling among them is modified so that it resembles the problem. If that is done correctly, the magnets may change their orientations, but never leave the ground state. By reading out their final orientations, you obtain the solution to the problem you wanted.
If this happens to be a classical process—which we just discussed above—then this is no faster than a classical computer. However, if the magnetics are behaving in a quantum manner, then it might be a quantum computer and could be faster.
So, is it quantum or not?
According to a recent paper in Nature Communications, the D-Wave device is not doing classical simulated annealing. Which, unfortunately, means exactly that. It tells us what it isn't, but doesn't tell us what it is.
To go into this a little more deeply, the researchers analyzed how the coupling between the magnets created a ground state. The layout of the hardware consists of four inner magnets arranged in a diamond (so each magnet is coupled directly to two others). Each of these is coupled to one additional magnet, but those are not coupled to each other. This configuration appears to be set up such that the four inner magnets always have the same orientation, while the outer magnets are free to arrange themselves as they see fit.
This results in a rather strange set of 17 possible ground states, most of which can be reached in steps of single flips of magnets. Except for the last, which requires that all four inner magnets flip at the same time.
In a classical simulation, the set of magnets can sample many different states. But, if by chance it happens to flip into this last ground state, it becomes trapped there. Furthermore, once it is there, the outer magnets become trapped in a single state too, because all other configurations have higher energy. Of course, once in this isolated state, it can also get out by flipping all four inner magnets, but the isolation and lack of noise (the outer magnets can't flip either) mean that it is, in some sense, less likely to flip out of the state than into it.
In the quantum description of these events, this doesn't happen. After setting up the ground state, we start trying to move to the solution state (by varying the environment). As soon as we do that, the ground state splits up, and the isolated state where things get stuck raises up in energy, away from the ground state. Since everything is kept in the ground state, it is no surprise that we find that the probability of entering the isolated state reduces sharply.
But, notice that this is different from the classical case. In the classical case, there was no way to break up the ground state. In other words, the energetic descriptions of the classical and quantum ground states are not the same, and it is no surprise that they give two different results.
Why the difference?
At heart, this difference was inevitable. When you get right down to it, we live in a quantum world, and if you are careful enough, that will shine through. In some ways, this shows how sloppy our thinking about the whole thing is. When we think of simulated annealing, or anything else like this, we imagine a purely classical or a purely quantum system. In reality, things are a lot more messy, with some aspects remaining classical and others showing their quantum nature.
What these results show is that we can't treat the D-Wave optimizer as a purely classical device. But, whether that actually means anything in practice is very hard to tell. One of the things that I admire about this, though, is the way the research output is slowly piling up, with much of the evidence being positive for D-Wave. It is the best way to answer critics, both professional and amateur: keep generating evidence and data.
No comments:
Post a Comment