So I’ve written an article about the above question for PBS’s website—a sort of tl;dr version of my 2005 survey paper NP-Complete Problems and Physical Reality, but updated with new material about the simulation of quantum field theories and about AdS/CFT. Go over there, read the article (it’s free), then come back here to talk about it if you like. Thanks so much to Kate Becker for commissioning the article.
In other news, there’s a profile of me at MIT News (called “The Complexonaut”) that some people might find amusing.
Oh, and anyone who thinks the main reason to care about quantum computing is that, if our civilization ever manages to surmount the profound scientific and technological obstacles to building a scalable quantum computer, then that little padlock icon on your web browser would no longer represent ironclad security? Ha ha. Yeah, it turns out that, besides factoring integers, you can also break OpenSSL by (for example) exploiting a memory bug in C. The main reason to care about quantum computing is, and has always been, science.