Ever since I heard about quantum computing (it arose in the 1970s, but most of the really visible stuff started in the mid 1980s, see the Wiki timeline), I have been skeptical. This skepticism arose from a view that quantum computers could solve NP-complete problems in polynomial time. I was randomly wandering the blogosphere when I can across “Shtetl-Optimized” by Scott Aaronson, with the subtitle “Quantum computers are not known to be able to solve NP-complete problems in polynomial time”. Well, perhaps everyone else knew that, but it was somewhat annoying that something I knew for two decades was dead wrong. While practical quantum computers still seem some time away (it seems the state of the art is factoring 15=3×5), trying to determine the effect of quantum computing on OR seems like an interesting question.
One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ“, where he lists some of the questions he was asked in his job search (he is a postdoc at my alma mater, the University of Waterloo’s Department of Combinatorics and Optimization). I’ve interviewed for a job or two in the couple years this blog has been going, but I have not been bold enough to talk about it. Scott uses the entry as a very quick survey of what he believes in, and the interviewers don’t come across like idiots (I guess I would have asked about half the questions myself).
Check out also his article “NP-Complete Problems and Physical Reality“published a couple of years ago in the SIGACT News complexity column. Having lived through an era when NP-completeness results were being churned out by the boatload with only a few providing real insight and advance (kinda like approximation results these days), I have not advanced very much beyond what I knew ten years ago, but Scott’s writing make this look pretty interesting again.
Finally, I am jealous of Scott’s ability to write well enough and intriguingly enough to generate dozens of comments on each of his posts. He points to the following review of his blog:
OK, on to the second breakfast link. Bill Gasarch has reviewed my blog for SIGACT News (scroll down to page 15), together with Lance Fortnow’s and Luca Trevisan’s. Favorite quotes:
Lance is Walter Cronkite. Scott is Stephen Colbert.
The name of the blog, ‘Shtetl-Optimized’ does not really say what it is about. With this in mind one can never say Scott has gone ‘off topic’ since its [sic] not clear what the topic should be.
Perhaps I am sticking to the topic too much!