BQP, NP, and All That

The mothership, aka Seed magazine, has a crib sheet for quantum computing. Its not half bad, considering how bad things like this can go. And of course this is probably due in part to the fact that they list the Optimizer as a consultant. But the real question is whether that little shade of black outside of NP is an illustrators trick or the result of a complexity theorist being the person they asked to vet the cheat sheet?

In Probability We Trust?

When discussing ways that quantum computing may fail, a common idea is that it may turn out that the linearity of quantum theory fails. Since no one has seen any evidence of nonlinearity in quantum theory, and it is hard to hide this nonlinearity at small scales, it is usually reasoned that these nonlinearities would arise for large quantum systems. Which got me thinking about how to well we know that quantum theory is linear, which in turn got me thinking about something totally wacko.
Continue reading “In Probability We Trust?”

To Woo Engineers

Hoisted from the comments, Rod says

You guys are much more blunt than I usually am (except with students :-). You’re also a lot more succinct.
This particular paper may be wrong, and the authors should be told that, but: as the field grows, and more engineers join, there are going to be more people who start with naive positions. The goal is not to run them off, but to teach them, so they can help us build these things :-).

To which, of course, I can only plead guilty, guilty, guilty. I mean no harm to engineers, that is for sure, especially considering the fact that I am surrounded by them 😉 And damn straight I know how important engineers will be in building a quantum computer, and that physicists all by themselves are more likely to be doomed in this endeavor (but I might add that D-wave or Transmeta might demonstrate that just having the engineering bravado isn’t necessarily enough. Damn straight sometimes those physics and theory people know what the hell they are talking about.)
Continue reading “To Woo Engineers”

A Race for Quantum Computing People

Okay, quick, who can be the first to tell me what is drastically wrong with arXiv:0804.3076? (via rdv.) Winner gets a beer next time I see them. This is almost as fun as the game of trying to spot the error in papers claiming thethe discovery of a quantum algorithm for efficiently solving NP-complete problems.

Best Science Movie? It Doesn't Take a Genius…

After a comment suggesting that a Science Film festival be held to combat a certain idiotic movie, He of Uncertain Principles agreed, and then the powers that be at scienceblogs decided to hold a poll on the Best Science Movies. And the four choices are….”Contact”, “Gattaca”, “An Inconvenient Truth”, and “Jurassic Park.” To which I can only say…
Continue reading “Best Science Movie? It Doesn't Take a Genius…”