More notes and a homework for CSE599d Quantum Computing
Lecture Notes
Introduction and Basics of Quantum Theory
Dirac Notation and Basic Linear Algebra for Quantum Computing
Homework
Homework 1
More Hot Water Fodder
Since, my remarks in the last post about classical computational complexity got me into such hot water with those who are much smarter than I am, I thought I’d post another of the less often expressed reasons for studying quantum computation from my notes:
It is often remarked upon by mathematicians and physicists that there is a mysterious harmony between these two disciplines. Indeed both fields have benefitted immensely from each other. The same can not be said, I think, for computer science. A good question to ask is why this is true? One idea floating around in research land is that the reason for the lack of such deep connections has been that this is because the wrong model of computation has been studied. It makes sense that if the universe obeys the laws of quantum theory, then we shouldn’t be surprised if a theory of computation based on classical theory doesn’t make connection to the physics of these devices. And going one further step it also seems likely that if we use the theory of computation which is more relevant to the way our world works, then we just might be able to prove and reason about these computers in a simpler manner. A rough analog might be that between real analysis and complex analysis: certainly those of you who have had a class on real analysis and complex analysis remember how “easier” everything is in complex analysis than in real analysis. Might quantum computers lead to a similar shift? Right now there are only a few results that I can point to along these directions, for example Scott Aaronson’s has a very eloquent proof that the complexity class PP is closed under intersection which begins by first showing that PP is equal to a model of quantum computing in which one can post-selection the outcome of the quantum computation and then is extremely simple due to the properties of the quantum model of computation to show closure under intersction. Might not more of the theory of computational complexity be as easy if we focus on the model of quantum computation?
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”:
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 
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.
Jobs in Quantum Information Science
This is the first year in a few that I haven’t been applying for jobs (You might suspect that this makes me less grumpy. Well, judge for yourself!) Now I could be wrong, but is this the first explicit advertisement by a U.S. university physics department for a theory position in quantum information science?
Quantum Information Theory
The Department of Physics and Astronomy at the University of Southern California invites applications for tenure or tenure track positions at all faculty levels in the area of Quantum Information Theory.
Well even if it isn’t the first, can we take this as a good sign?
Ion Trap Quantum Computer Papers
Interesting papers in experimental ion trap quantum computation:
Creation of a six-atom ‘Schrödinger cat’ state from Wineland’s group at NIST Boulder, Nature 438, 639-642 (1 December 2005.) Schrodinger’s cat is now six qubits big! And growing! What a cute little kitten.
Scalable multiparticle entanglement of trapped ions from Blatt’s group in Innsbruck. Nature 438, 643-646 (1 December 2005.) In this paper the group discusses experiment they performed which created the so-called “W” entangled state for up to eight qubits. That’s a quantum byte, peoples! Amazingly the group performs full state tomography on these states. Wow that sounds like an awful lot of graduate student hours.