Scott Aaronson and Lance Fortnow discuss What should physicists know about computational complexity?
I’m thinking that this deserves a rejoiner, “What should a computer scientist know about computational complexity?” I mean, how silly have these computer scientists been…they’ve been studying classical computers for all these years, when it is totally obvious (at least to a physicist like me) that they should have been studying quantum computers. 😉
This reminds me of my favorite way to distinguish between a computer scientist and a physicist at quantum computing conference. Physicists are the ones who think that NP stands for “not polynomial” and computer scientists are the ones who think that a Hamiltonian is some sort of sandwich.
O brave new quantum world!
What computer scientists should know about computational complexity (that physicists already do):
1) The cost of computational complexity is measured by action, not time. I.e., one can sometimes solve a problem more quickly by dumping more energy into it.
2) Computational problems can be solved in continuous time. I.e., time does not have to be discrete for computational complexity to be nontrivial.
3) Computation is local. I.e., nonlocal computational models are unrealistic because known physical laws are fundamentally local. Even topological quantum computation requires particle fusion for readout, which is a local process.
Andrew when are you going to start your own blog? I want dualing Scott Aaronson versus Andrew battles on the blogosphere!
I would start a blog, but I just know it would be a huge time sink. I probably shouldn’t even be making this post right now! For the moment, I prefer trolling your blog and others’ every now and again and contributing my two cents when my hackles get raised.
As for me versus Scott on the blogosphere, I tend to agree with Scott most of the time, so such a matchup wouldn’t be all that exciting. Besides, Scott is a good computer scientist and already knows all the things in my previous post anyway. 🙂
Get back to work Andrew! Oh, wait, what am I doing posting right now.
“Besides, Scott is a good computer scientist and already knows all the things in my previous post anyway.”
Hey Andrew! I was going to make that exact point, but I see you already know that I already know those things. 🙂
As I cluess non-science guy, I liked the analogy between quantum entanglement and (not violating) the speed of light, and quantum computing and (not solving) NP-Complete problems. At least I can classify them together as ‘way to subtle for me’.