The Quantum Pontiff

Update: Patrick says I’m very senstive. Which I certainly am. And as Patrick says, what Clifford is doing with the course sounds very very cool. So take this post with a grain of salt, or as an indication of what happens when I wake up on the wrong side of the bed (or the world?)
Update, update: Well it turns out that the answer to my question was neither (a),(b), or (c)! See the comments for the answer!
Clifford over at Cosmic Variance, tells a story

The semester started, and I showed up to teach what I thought was supposed to be the second part of a graduate string theory class, as long promised.
…
The first warning sign was that I looked on the online schedule to see where my class was to be held (small classes often end up in surprise mystery buildings all over campus…I like this because I get to learn of new teaching spaces over in the Humanities territories, for example), and saw that the title of the course was something like “Introduction to Relativistic Field Theory”.
…
So I showed up for the first class (this is three weeks ago now), and sure enough, there are the six or seven graduate students from Nick’s class…. but there are four or five students from the condensed matter group, and from the quantum information groups, part of CSI (I kid you not) over in Electrical Engineering! They saw a course with that title and, understandably, thought it was a good chance to learn some Relativistic Field Theory.

Which perplexs me. Is Clifford (a) confused that quantum information is part of the Communication Science Institute, (b) shocked that quantum information science is “relegated” to Electrical Engineering, or (c) dismayed that there are smart people in quantum information science who are interested in learning relativistic field theory, because, you know, quantum information science is just linear algebra and all?

In 1993, Bernstein and Vazirani had demonstrated a superpolynomial query complexity speedup for quantum computers over classical computers. Charlie Bennett wrote a article in Nature in April 1993 about these new recent developements in quantum computing. In this article, Charlie wrote:

An early but probably vain hope was that quantum parallelism might provide a fast way of solving problems such as factoring or the travelling-salesman problem, which appear to be hard in the same way as finding a needle in a haystack is hard, that is because they involve a search for a successful solution among exponentially many candidates. A computer able to test all the candidates in parallel, and signal unambiguously if it found one that worked, would solve these problems exponentially faster than known methods.
It is easy to program a quantum computer to branch out into exponentially many computational paths; the difficult part is getting the paths to intefere in a useful way at the end, so that the answer comes out with a non-negligible probability. This difficulty is illustrated by the factoring problem above. Suppose the quantum computer is programmed to factor a 100-digit number by trying in parallel to divite it by all numbers of fifty digits or fewer. If any of the approximately 10^50 computation yeilds a zero remainder, it will in a sense have solved the problem. But if there is only one successful path, the interference pattern among all the paths, which determines the behaviour of the computer as a whole, will scarecely be affected. Quantum computers cannot amplify an answer found on a single computation to a detectable level because interference is an additive process, to which each path contributes only as much weight as it started out with.

How strange: to use brute force factoring as the example of a hard problem for quantum computing! Amazingly, Charlie wasn’t even the first to perform this strange analogy. Here is Greg Egan in the book Quarantine in 1992:

Let a computer smear-with the right kind of quantum randomness-and you create, in effect, a ‘parallel’ machine with an astronomical number of processors…All you have to do is to be sure that when you collapse the system, you choose the version that happened to find a needle in the mathematical haystack.

Which makes one wonder, why the heck were all these people thinking about factoring and quantum computers right before Shor’s discovery? Strange, no?

SODA papers are out. One quantum paper: “Quantum Verification of Matrix Products” by Harry Buhrman and Robert Spalek. Also known as quant-ph/0409035.

Patrick Hayden (awesome ski picture) sends me an email that negative quantum information was discussed…..on the public radio show “Car Talk!” (The August 27th edition, available for purchase from audible.com.) You know your work has hit it big time when it makes it onto a show which discusses how to repair your car. The next step after “Car Talk” is if your work appears on “The Daily Show.”
Of course, we shouldn’t be too surprised. The hosts of “Car Talk”, Tom Magliozzi and Ray Magliozzi (click and clack), both graduated from MIT. In the show where they discuss negative quantum information, one of the two hosts says something like “Of course you know who Claude Shannon is.” Of course!

A workshop I very much regret missing because I was in Italy, “IBM Workshop on Fault-Tolerant Quantum Computation” now has all of their presentations online.