Beware of Roaming Complexity Classes?

Ack am I missing something or is the Complexity Zoo missing most of its inhabitants? Crap I don’t want to get run over by a loose AM! Update 5/2, 2:50pm Whew. That’s more like it. All the complexity classes now seem to be back in the zoo. Most disturbing, of course, was the missing ALL beast. End Update
On a more amusing front, this page on the qwiki is depressing, no?:

Articles in category “Faculty Position”
There are 0 articles in this category.
Retrieved from “http://qwiki.caltech.edu/wiki/Category:Faculty_Position”

Once I Was a Physicist

I’ve always (not really 🙂 ) dreamed of being in Physics Today (and not in the obituary section!), but I never imagined that when it happened I would be called a computer scientist! From Physics Today, Aprill 2007 edition, in the web watch box (sorry subscribers only!):

Scirate
Dave Bacon, a computer scientist at the University of Washington, has devised a way to filter the torrent of preprints from arXiv and other servers. His experimental website, Scirate, works like flickr and other social websites. Individual users rank the preprints they come across. Scirate then gathers those rankings and lists the preprints according to their popularity.
http://scirate.com

My apologies to all you real computer scientists for whom calling me a computer scientist is very much quite an insult!

AQIS 2007, Kyoto, Japan

Come to Japan! See who can eat more sushi, Dave or Scott?

Asian Conference on Quantum Information Science
September 3-6, 2007
Shiran Kaikan, Kyoto University
Webpage http://qc.naist.jp/aqis07. Poster here.

Quantum Missile Command

My new favorite quantum hyperbole:

Handed to generals, a quantum computer might transform an ordinary nation into an instant superpower. Dozens of incoming missiles could be tracked at once.

Ketchup-ing

Things that happened while I was off the edge of the Interwebs:

  • Cormac McCarthy (my office neighbor while I was at the Santa Fe Institute) won the Pulitzer for fiction for his novel The Road. Cormac is also (amazingly!) giving an interview on Oprah, which is almost as amazing as Pynchon appearing on the Simpsons.
  • A new branch campus for the University of Washington is moving forward. This is a compromise over a previous attempt by the city of Everett to establish an independent polytechnic, which they hypothetically called the “Washington Institute of Technology” (WIT…you have to have a sense of humor to teach there?) This will bring to four the number of posts I have under the category of WIT.
  • Quantum inteference in photosynthesis
  • Earth-like planet discovered only twenty light years away. (Probably) five times the size of as massive as the Earth. If we send off an expedition today, by the time we arrive we should have been able to evolve to survive in the five times higher gravity?
  • Papers scirate wants me to read while I was away: 0704.3432, 0704.2529, 0704.2575, 0704.2575, 0704.2241, and 0704.3142.
  • A horrible title for a Nature blurb, “Quantum cryptography is hacked,” about an experiment performed at MIT (Phys. Rev. A, 75, 042327.) Notice how an inacurate title leads to all sorts of bad follow ups. That’s almost egregious enough to induce a Rage Against Doofosity!

Pontiff and Evolution

That other Pontiff has declared that he “believes in evolution.” Am I the only one who read “[reclaim] a dimension of reason we have lost” and thought of string theory? (That’s a joke peoples, so don’t get your stringy hair in an uproar!)

The NP-complete Dog and Pony Show Comes to Seattle

Scott’s coming to town:

CSE Colloquium, 04/12/2007 3:30 pm, EE-105
Talk: The Limits of Quantum Computers
Speaker: Scott Aaronson (University of Waterloo)
Abstract: In the popular imagination, quantum computers would be almost magical devices, able to “solve impossible problems in an instant” by trying exponentially many solutions in parallel. In this talk, I’ll describe four results in quantum computing theory that directly challenge this view.
First, I’ll show that any quantum algorithm to decide whether a function f:[n]->[n] is one-to-one or two-to-one needs to query the function at least n^{1/5} times. This provides strong evidence that collision-resistant hash functions, and hence secure electronic commerce, would still be possible in a world with quantum computers.
Second, I’ll show that in the “black-box” or “oracle” model that we know how to analyze, quantum computers could not solve NP-complete problems in polynomial time, even with the help of nonuniform “quantum advice states.”
Third, I’ll show that quantum computers need exponential time to find local optima — and surprisingly, that the ideas used to prove this result also yield new classical lower bounds for the same problem.
Finally, I’ll show how to do “pretty-good quantum state tomography” using a number of measurements that increases only linearly, not exponentially, with the number of qubits. This illustrates how one can sometimes turn the limitations of quantum computers on their head, and use them to develop new techniques for experimentalists.
No quantum computing background will be assumed.

Since no quantum computing background is assumed, I may even be able to follow this one!