Quantum Pontiff
February 2010
M T W T F S S
« Nov    
1234567
891011121314
15161718192021
22232425262728

Physicists and Computer Scientists

December 14, 2005 on 8:22 pm | In Computation, Physics, Quantum |

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.

6 Comments »

RSS feed for comments on this post.

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

    Comment by Andrew L. — 12/15/2005 #

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

    Comment by Dave Bacon — 12/15/2005 #

  3. 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. :)

    Comment by Andrew L. — 12/15/2005 #

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

    Comment by Dave Bacon — 12/15/2005 #

  5. “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. :)

    Comment by Scott Aaronson — 12/15/2005 #

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

    Comment by Jon — 12/15/2005 #

Leave a comment

XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>

Powered by WordPress with Pool theme design by Borja Fernandez.
Entries and comments feeds. Valid XHTML and CSS. ^Top^