CSE 599d Lecture Notes 1

Well class begins for me this afternoon. As I’ve mentioned before I’m teaching a graduate course in quantum computing. Here are the first set of lecture notes for the class: Introduction and Basics of Quantum Theory. As part of these notes, I’ve put a little section with some of the less often expressed reasons I think doing research in quantum computing is important. Here is one excerpt which I’m sure many of you will enjoy:

If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.

Schurly Your Joking Drs. Bacon, Chuang, and Harrow?

What better way to start the new year than with the new paper dance. You can dance, you can dance, everyone publish their rants.
Thanks to the hard work and good timing of coauthor Aram Harrow, we were able to get the first paper of the new year on quant-ph: quant-ph/0601001. Happy new year!
The Quantum Schur Transform: I. Efficient Qudit Circuits
Authors: Dave Bacon, Isaac L. Chuang, Aram W. Harrow
Comments: 24 pages

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.

Quantum Trickery

A nicely written article in the New York Times about entanglement: Quantum Trickery: Testing Einstein’s Strangest Theory by Dennis Overbye (author of “Einstein in Love”.) Interestingly, the article claims that the Einstein, Podolsky, Rosen paper is now Einstein’s most cited paper. Of course a lot of this is because this is one of Einstein’s most controversial papers. But I think quantum information science has got a lot to do with this as well. Take a look at this plot from S. Redner’s physics/0407137 “Citation Statistics From More Than a Century of Physical Review”:
Rise of EPR
In 1994 Peter Shor showed quantum computetrs could factor and EPR hasn’t been the same since. Well and certainly those working in electron paramagnetic resonance have had a tougher time finding their own literature!
On a related note, for an interesting take on Einstein’s own view of the EPR paper you might be interested in reading The Shaky Game: Einstein, Realism, and the Quantum Theory by Arthur Fine (who is in the philosophy department here at UW.) One thing which Fine reveals is that it seems that Einstein wasn’t really that happy with the argument in the EPR paper.

Merry Christmas!


Chirstmas Eve at my mom’s home in Yreka (“Yreka Bakery” backwards is “Yreka Bakery”) enjoying a warm meal before going out to look at the Christmas lights. I will say that Wal-Mart is making a killing off of those blow up Santas and blow up Snowmen.

"A World Without Time: The Forgotten Legacy of Gödel and Einstein" by Palle Yourgrau

I have often heard it describe that to be a great philospher, one must grab ahold of a single idea, put on blinders to all opposing thoughts, and then run with it. This is not to accuse all philosophers of such maniacal tunnel vision, but there certainly is at least a grain of truth in this idea. And it is certain the one part of philosophy as practiced by philosophers which drives physicists absolutely nuts!
Why all of the sudden philosophy bashing? Well I just finished reading A World Without Time: The Forgotten Legacy of Gödel and Einstein by Palle Yourgrau. From the title you would guess that this book is a discussion solely of the friendship between Einstein and Gödel, but really the book is a vigorous argument that Gödel should be taken seriously as an important philosopher. In particular Yourgrau believes that Gödel’s work in general relativity and his argument “against time” have been overlooked by philosophers as is of great importance. The book, therefore, will be of more interest to those familiar with Kant and Wittgenstein than to those who are interested in the logic and the physics that Gödel and Einstein are usually associated with.
Now back to philosophers going overboard in one direction. Here I think that Yourgrau is so zealous in his defense of Gödel as a philosopher that he misinterprets the reason why physicists argue against the relevance of Gödel’s universe. Gödel’s universe is a cosmological solution to the equations of general relativity in which the universe is rotating. Interesting in this solution to the equations of general relativity there exist closed timelike curves. Now I won’t get into the reasons why Gödel is interested in this universe and I don’t object to the use of this universe in philosophical discussions about the nature of time, but I think that Yourgrau’s characterization of physicist’s reaction to solutions to Einstein’s equations with closed timelike curves isn’t quite right. In particular he bluntly dismisses the chronology protection conjecture as totally adhoc. Or, in his words

Just as David Hilbert tried at first to avoid the consequences of the incompleteness theorem by inventing a new rule of logical inference out of whole cloth, so too the relativistic establishment, in the person of Stephen Hawking, tried to get around the embarrassing consequences introduced by the Gödel universe. If the annoying Gödel universe was consistent with the laws of general relativity, why not change the laws? Hawking thus introduced what he called the “chronology protection conjecture” (though a better name would have been the “anti-Gödel amendment”), which proposed a modification of general relativity whose primary goal was to rule out the possibility of world models like Gödel’s, with their awkward chronologies premitting closed temporal loops and causal chains with no beginning. Despite having, as Russell noted in a different context, all the advantages of theft over honest toil, Hawking’s chronology protection conjecture has won few adherents, its ad hoc character betraying iteself.

This characterization of the chronology protection conjecture seems to me very misleading. Why? Because the chronology protection conjecture isn’t just an “add-on” to general relativity: it is the conjecture that general relativity when combined with the other laws of physics does not allow for closed timelike curves. This is different from arguing, as Yourgrau later does, that the objection is simply that Gödel’s universe is not our universe: it is arguing that the more complete laws of physics disallow closed timelike curves. Of course, if your blinders are on, like a good philosoher, then perhaps this distinction is not important. But as a physicist, where there is more than just general relativity to consider, the chronology protection conjecture is a different sort of statement and has considerable evidence in favor of it (and I think most phyisicsts don’t have much of a problem with the chronology protection conjecture, in constrast to Yourgrau who thinks that most people have a problem with it.)
So read “A World Without Time…” with your “physicist” or “scientist” mode shut off and you will be fine. Is it actually possible to turn off these modes? Only if you were a literature major like me 😉

Ion Trap Scaling Work

One of the big pushes occuring in ion trap quantum computing these days is the construction of different ion traps which will be useful in scaling up these quantum computer architectures. Chris Monroe’s group at Michigan (in collaboration with Keith Schwab at the PRL in Maryland) has a nice paper out a few days ago in Nature Physics describing a new ion trap they have built (for a news release, see here. ) This microtrap is built, basically, on a semiconductor chip, and is of the micrometer size as compared to the millimeter sized traps normally used for trapping ions. Because these traps are fabricated using semiconductor MEMS technology, it is not unreasonable to think of building traps which can stored hundreds to thousands of ions at a time.
One interesting property of the traps described in the paper is the shallow depth of the trapping potential as compared to the depth of the potential for larger, milimeter scale traps (about 0.08 eV in the former compared to order 1 eV in the latter.) What this means is that the ions they trap stay in the trap for minutes as opposed to days, and that it has not been possible to simultaneously trap two ions in the trap. Which is what I love about experiments: while this is an important step, we’re certain to see more steps in the future and it is not unreasonable to expect some good scaling up in of ion trap quantum computers in the next few years.
Another set of experiments involving traps designed to be scalable comes from Isaac Chuang’s group at MIT. A preprint of their work is available as quant-ph/0511018. Me, I just like to flip to the end of their paper and stare at their neat hexagonal trap and dream of the cool things I could do with such a trap.

Physicists and Computer Scientists

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.

QIP 2006 Talks

QIP 2006, to be held in Paris, now has the list of talks for this workshop here. There were 160 submissions! There are eight invited talks, sixteen long talks, and sixteen short talks. Lots of interesting talks, which makes me wish I could have figured a way to attend (that and I’ve never spent any time in Paris.)
By the way, for those of you thinking of applying to graduate school in quantum information science theory, this list of speakers, and the institutions they represent, would probably be a good place to start.