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.

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.Like or Dislike: 0 0

Andrew when are you going to start your own blog? I want dualing Scott Aaronson versus Andrew battles on the blogosphere!

Like or Dislike: 0 0

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.

Like or Dislike: 0 0

Get back to work Andrew! Oh, wait, what am I doing posting right now.

Like or Dislike: 0 0

“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.

Like or Dislike: 0 0

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’.

Like or Dislike: 0 0