Via Richard Lipton, news that HP research scientist Vinay Deolalikar has put online a 102 page draft of a paper purporting to prove that P is not equal to NP. (Follow the link to Deolalikar's page, and the paper is the first one linked under "Selected Publications".) It is being taken seriously by serious people (like Lipton)--- in the sense that they are trying to understand it and understand whether or not it is correct. The length, of course, increases the likelihood of a so-far unspotted error. Lipton thinks Deolalikar's use of finite model theory is an interesting and promising twist. I have only just downloaded the paper, and am not a complexity theory expert, but what leaps out at me from the abstract is that it involves graphical models for sets of interacting random variables, an area that interests me. Not that surprising, I guess, as lots of difficult problems---as well as ones that are easy but perhaps not obviously so, because of structure described by a graphical model of the dependencies between variables---are naturally described in graphical terms, and the relation between graphical models and complexity is a well-studied---though mostly relatively recently studied---topic. I can no longer find the link to the online draft of Marc Mezard and Andrea Montanari's book on the subject (and its relations to physics and coding theory), perhaps because it's been published. [Correction: it's still online here. Thanks to commenter Kristal Cantwell for the link.] One key notion in such models is conditional independence---independence of two subsets of the random variables in question, when conditioned on a third set. A really nice paper on a quantum notion of conditional independence, relating it to the equality conditions for the strong subadditivity inequality for quantum entropy, is by Hayden, Jozsa, Petz, and Winter. Matt Leifer and David Poulin, and others, have described quantum graphical models.
You can bet that if Deolalikar's proof looks good, a slew of people will be applying the research strategy I like to call the "quantization functor" to it.
For those for whom P and NP are not their bread and butter, to give you an idea of how big this would be: I just goofed by telling my wife that if this pans out, it will be one of the most important results of twentieth century mathematics. Well, it would have been if done in the twentieth century. But I'll say more: although we're only 10 years in, I think it will be one of the most important results of twenty-first century mathematics. I haven't said what it really means but that's what Wikipedia is for.
I should point out that Scott Aaronson is dubious, though not based on close perusal of the proof. He has pledged to personally supplement the million dollars the Clay Mathematics Institute will pay Deolalikar if the proof is correct, with two hundred grand of his own.
"I can no longer find the link to the online draft of Marc Mezard and Andrea Montanari’s book"
There are links to six parts of an earlier draft _Information, Physics and Computation_ at http://www.stanford.edu/~montanar/BOOK/book.html.
I just downloaded them so the links seem to work.
I was also pretty excited to see that almost everything used in the paper is something I have spent time trying to generalize to the quantum case (with varying degrees of success). It will be interesting to look at quantum generalizations once the experts have determined what can actually be proved using the methods in Deolalikar's paper. However, I'm not necessarily the best person to actually do this, as I tend to get bogged down in the conceptual foundations of any subject I work on and I'll end up being obsessed with getting the neatest quantum analogs rather than cooking up some results quickly. Someone like Matt Hastings will probably beat me to it as he has a pretty good background for this.
For quantum conditional independence and quantum graphical models, I think we have the correct definitions, although the current state of knowledge about them lags far behind their classical counterparts. Essentially, in the quantum case one has to deal with monogamy, i.e. the conditional state of B, given A places restrictions on the possible conditional states that can be assigned to C given AB, whereas in the classical case conditional states may be assigned freely. I know this is not the usual definition of monogamy, but I think this is the best way of thinking about it. Essentially, this gives you a kind of frustration in the quantum case even for Hamiltonians that are not frustrated classically and it is the source of the relative hardness of solving quantum statistical physics problems compared to their classical counterparts. It also makes it hard to prove proper analogs of things like the Hammersley-Clifford theorem, which is used in Deolalikar's paper. Note, we proved one direction of this theorem for one definition of quantum conditional probability in the paper with David Poulin, but that's probably not good enough for this purpose.
The other main idea used in Deolalikar's paper is the finite model theory approach to characterizing complexity classes. I don't think we currently have very good quantum analogs of this stuff. One could probably cook something up by using the local Hamiltonian problem as the generalization of satisfiability, but personally I would prefer something that was founded in some sort of formal logic. This obsession of mine may not be important for generalizing Deolalikar's stuff, as I am not sure how important the logical interpretation of these result are, but it is the place where I am most likely to get bogged down. However, it does give me a renewed motivation to look at various logics in the context of quantum computation again.
Matt, I'm intrigued by your statement that "Essentially, this gives you a kind of frustration in the quantum case even for Hamiltonians that are not frustrated classically". I'm going to be lazy, and possibly reveal abysmal ignorance of basic matters, by asking you to be more precise about what you mean by the quantum case for a Hamiltonian that is not frustrated classically. I would guess that if we just take a classical spin-system Hamiltonian and let the up and down states of its spins correspond to, say,
up and down in the Z direction for quantum spins, we just get the same ground state as classically (but in the tensor-product-of-Z-eigenstates basis). If that's right, then what I just described must not be what you mean by a quantum version of a classical Hamiltonian. I'd really like to understand this because your point about frustration seems important.