No Satisfaction Redux

A few weeks ago I blogged about hearing the talk by Boris Altshuler purporting to show that the adiabatic quantum computing scheme for solving the 3-sat problem is not going to work.

To review: 3-sat is a particularly simple case of NP complete problem (such as traveling salesman) where it is not known if a solution can be found in polynomial time or not. Showing that NP problems can be solved in polynomial time (or showing the converse) is perhaps the most important outstanding theoretical computer science question. The adiabatic quantum approach purports to have an approach for finding such a solution in polynomial time.

The essence of the scheme is to construct a Hamiltonian H_P whose ground state is the solution to the problem. Initialize the system in a a known ground state of a known simple Hamiltonian H_I . Then adiabatically vary the Hamiltonian

H = t H_P + (1-t) H_I


As t goes from zero to one, the adiabatic theorem keeps the system in the ground state so long as the gap does not close. So the issue boils down to how big is the gap. Most people (including Altshuler) think that the gap gets exponentially small which means that the scheme takes exponentially long to run (which is then uninteresting).

Last week at Aspen I heard an informal talk by Eddie Farhi, one of the proponents of adiabatic quantum computing, on the same subject. Although Altshuler’s talk was pretty compelling, Farhi made a few notable points.

(1) To a computer scientist, the 3-sat problem is “solved” in polynomial time if you have an algorithm that ALWAYS finds a solution to the problem in polynomial time. However, it is still interesting (although not equivalent) if you have an algorithm that typically finds a solution in polynomial time. This is a bit less stringent of a requirement.

(2) Numerics simulating the adiabatic quantum approach to solving the 3-sat problem (for up to 100 bits or so) seem to indicate that it will work after all (that the gap is not exponentially small). These numerics have been done by people like Peter Young, who is certainly no slouch. One can always argue that when you look at more bits the algorithm will suddenly fail, but apparently there is no indication of this as of yet.

(3) Finally, it was pointed out that even if generically you have an exponentially small gap, you still have the freedom to construct an arbitrary

H = t H_P + (1-t) H_I + H_{extra}(t)


And if any H_{extra} can be thought up that generically keeps the gap large, then you have a good solution.

My gut feeling is that despite this evidence to the contrary, in the end, this is not likely to provide a polynomial solution to NP complete problem. I even think it is unlikely to typically find a solution.

Apparently Alexei Kitaev, who is officially a genius by the McArthur foundation, apparently stated that he thought the gap HAD to be exponentially small based on the reasoning “otherwise the algorithm would work”.