Some interesting papers.
First, a paper by Andrew Childs and Wim van Dam, “Quantum algorithm for a generalized hidden shift problem”, quant-ph/0507190 which gives a very nice, new algorithm for, well, for what it says: hidden shift problems! Interestingly their new algorithm uses Lenstra’s classical integer programing algorithm to implement an entangled measurement on the quantum states they set up. I just started reading the paper this morning. Once I parse it, I may have more to post.
Another interesting paper, is “Rigorous location of phase transitions in hard optimization problems” which is, amazingly, a computer science article published in…Nature. If you read this paper and are a physicist, it will make you very proud:
Our results prove that the heuristic predictions of statistical physics in this context are essentially correct.
In other words…yeah the physicists are actually really good at guessing what approximations to make! The paper is nice as well, rigorously proving some nice properties of random instances of certain NP-complete problems.
Finally, I received in the mail yesterday “Probability Theory” by E.T. Jaynes. This book, in incomplete form, had been available on the web for many years. Following Jaynes’ death, G. Larry Bretthorst was able to collect some (but not all) of this material into “Probability Theory.” Unfortunately, Jaynes’ had intended to have two volumes, and it seems that the second volume was woefuly incomplete and so will not be published.
The Achlioptas et al. paper might have made you proud to be a physicist, but it made me proud to be a theoretical computer scientist. When reading Nature papers full of the sort of numerical simulations I used to do all the time as a 13-year-old, before I knew how to prove anything, I often wondered: “what would happen if someone sent Nature an actual theory paper with actual theorems in it?” Achlioptas et al. put that question to the test, in a paper as clear and concise as every theory paper ought to be.
Yeah it is a really nice paper. They are using it to advertise the new Nature Physics journal. Kind of funny.