{"id":154,"date":"2007-05-18T15:47:23","date_gmt":"2007-05-18T19:47:23","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=145"},"modified":"2007-05-18T15:47:23","modified_gmt":"2007-05-18T19:47:23","slug":"145","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2007\/05\/18\/145\/","title":{"rendered":"Quantum Computing and Learning from Blogs"},"content":{"rendered":"

\"ScottEver 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<\/a>), 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<\/a>” by Scott Aaronson<\/a>, 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<\/em> 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\u00d75), trying to determine the effect of quantum computing on OR seems like an interesting question.<\/p>\n

One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ<\/a>“, 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).<\/p>\n

Check out also his article “NP-Complete Problems and Physical Reality<\/a>“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.<\/p>\n

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:<\/p>\n

OK, on to the second breakfast link. Bill Gasarch has reviewed my blog<\/a> for SIGACT News<\/em> (scroll down to page 15), together with Lance Fortnow\u2019s and Luca Trevisan\u2019s. Favorite quotes:<\/p>\n

Lance is Walter Cronkite. Scott is Stephen Colbert.<\/p>\n

The name of the blog, \u2018Shtetl-Optimized\u2019 does not really say what it is about. With this in mind one can never say Scott has gone \u2018off topic\u2019 since its [sic] not clear what the topic should be.<\/p><\/blockquote>\n<\/blockquote>\n

Perhaps I am sticking to the topic too much!<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading “Quantum Computing and Learning from Blogs”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,46],"tags":[],"class_list":["post-154","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/154","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=154"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/154\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}