More notes for CSE599d Quantum Computing. I am calling these notes the Allegro notes because I have been spending a lot of time at the local coffee house called “Allegro.” Well at least it gives me a good excuse for the many many mistakes in the notes: they are obviously the fault of all the caffeine I consume at Allegro.
Lecture Notes
Lecture Notes 1: Introduction and Basics of Quantum Theory
Lecture Notes 2:Dirac Notation and Basic Linear Algebra for Quantum Computing
Lecture Notes 3:One Qubit, Two Qubit
Lecture Notes 4:The No-Cloning Theorem, Classical Teleportation and Quantum Teleportation, Superdense Coding
Homework
Homework 1
Handouts
Syllabus
CSE 599d Lecture Notes 3
More notes for CSE599d Quantum Computing
Lecture Notes
Introduction and Basics of Quantum Theory
Dirac Notation and Basic Linear Algebra for Quantum Computing
One Qubit, Two Qubit
Homework
Homework 1
Link Dumpage
My goal, of course, is to keep you from being productive (hence making me look more productive, wah hah hah!) Luckily some of my readers are kind enough to send me links that will aid me in this quest. The first, is from Tom, who send me a link to AtomChip® Quantum® II processor 6.8GHz with 256MB on-board memory. By the time we actually build a quantum computer, I fear that all of the good product names will have been taken!
And just in case you wanted to know about the end of the world in 2012, there is Prophet’s Manual – Fractal Supersymmetry of Double Helix. Chaos, physics, and biology…nice! When I was a graduate student our group consisted of physicist, chemists, and mathematicians. We were always looking for a biologist, so we could write a quantum bio nano paper.
CSE 599d Lecture Notes 2
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 
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.