No Satisfaction

There are some computational problems in computer science which are known as NP complete problems. One famous example is the traveling salesman problem, where a map is handed to you and you try to find the shortest continuous path that visits a particular set of N cities. (Strictly speaking the NP-complete version is determining whether there exists a path shorter than a certain length). There are quite a few problems in this computational complexity class, and it turns out that if you manage to solve one of them, you can essentially solve them all. It is not known, as you make the problem bigger, whether the difficulty of solving these problems grows polynomial with the size of the problem (ex, with the size of N above) or exponentially with the size of the problem. In fact, this question is viewed as so important that there is a million dollars waiting at the Clay mathematics institute for anyone who can prove either that it is polynomial or it is not.

A few years ago, a group of physicists at MIT proposed that a quantum computer might be able to solve such NP complete problems in polynomial time (In fact, this would not win them the million dollars by the precise definition of the challenge set out by the Clay institute, but it is still extremely interesting). Their scheme was to find pose an NP-complete problem such that it is essentially equivalent to finding the ground state (lowest energy state) of an appropriately designed quantum system. Then the way they want to actually find this ground state in practice would be to deform the parameters of the system smoothly until it becomes a simple quantum system where the ground state is already known – then initialize the quantum system in this known ground state – then adiabatically (slowly) deform the system back to the system we are interested in. Now according to the so-called adiabatic theorem of quantum mechanics, if a system is put in its ground state and the system is deformed sufficiently slowly, it will always remain in its ground state. So at the end of the process, we are in the ground state of the system we want, and we have our solution.

Well, unfortunately, there is a catch. The catch is the words “sufficiently slowly”. The time scale that determines what “sufficiently slowly” means is the lowest energy of the first excited state at any point along the path between the initial and final state of the system. If this first excited state happens to come down to be exponentially close to the ground state, then one needs to deform the system exponentially slowly to stay in the ground state and the process will take an exponentially long time.

Since the proposal of this scheme many (if not most) of the people in my community have assumed that this catch is precisely what ruins this idea completely. Nonetheless, the idea has been floating around for quite a while now and the issue still had not been nailed down very well. This week at the INSTANS conference in Amsterdam, Boris Altshuler gave a pretty solid looking proof that this “catch” does indeed happen and such a computer would take exponentially long to finish. To do this, he focused on the the so-called 3-satisfiability (or 3-satisfaction) problem, which is one of the famous NP-complete problems. And since all the NP-problems are essentially equivalent to each other, this seems to kill the idea at last.

[ For the experts (and very briefly) the issue really boils down to whether there is any gap opened up by anticrossings between multiple low energy solutions. But since for NP problems the different low energy solutions are extremely different from each other, there is exponentially low tunneling between them, hence no gap opens up. ]

So it seems that the quantum computer will not be getting any satisfaction this way. No no no. Hey hey hey. That’s what I say. It can’t get no…