CSE 599d Lecture Notes 5

The Allegro notes continue. Today’s notes are brought to you courtesy the great espresso drink “an Americano.”
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
Lecture Notes 5:The Quantum Circuit Model and Universal Quantum Computation
Homework
Homework 1
Handouts
Syllabus

CSE 599d Lecture Notes 4

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 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.

CSE 599 – Quantum Computing

The course I’m teaching next term:

CSE 599 (Special Topics in Computer Science)
Quantum Computing
—————————
Instructor: Dave Bacon
Time: Monday and Friday, 1:30-2:50, Wednesday 1:00-2:20
Location: CSE 503
What are the ultimate limits to the information processing power of computing machines? Since computers are physical devices, it makes sense to look for the answer to this question through the lens of our theories of physics. Astoundingly it was discovered over a decade ago that there exists a completely different kind of a computer than today’s modern computer. This new type of computer has the peculiar feature that it processes information according to the laws of quantum physics. Remarkably, such quantum computers have been shown to possess superior computing power over today’s classical computers. For example, in 1994 Peter Shor showed that a quantum computer could efficiently factor whole numbers (a task for which there is no known efficient classical algorithm.) This discovery is especially important since it tells us that if we build a large scale quantum computer, the most widely used public key cryptosystems will no longer be secure.
This course will serve as an introduction to the theory of quantum information science. Today this field is too large to cover in one course, but we will cover two of the most exciting fields in quantum computing: quantum algorithms and quantum error correction. No prior knowledge of quantum theory is necessary for this course, but prior exposure to linear algebra will be assumed.
The course will run three days a week from Wednesday January 4, to Friday February 17. Questions about the course can be directed to Dave Bacon at dabacon[aaattt]cs.washington.edu .

The course has a number which makes it sound like it is for sale, 599.

Comic Relief on Finals

Quotes which I put on the final for my quantum computing class:

“I didnt’ fail the test, I just found 100 ways to do it wrong.” — Benjamin Franklin
“People will accept your idea much more readily if you tell them Benjamin Franklin said it first.”–David H. Commins

Unfortunately I didn’t put a comic on the test. It always seemed that the exams I took in intro level physics and chemistry courses at Caltech, or the ones I saw in similar courses at Berkeley, always had either a Far Side or a Calvin and Hobbes comic on them. In fact, I have a conjecture about this. I’m convinced that you can identify the exam by the comic on the front of the exam. Far Side: physics. Calvin and Hobbes: chemistry. But this just may be a result of my local experience.

The GHZ Final Problem

Well, my grades are all turned in, and so I’ve pretty much officially finished teaching my first class. On the final, I had an extra credit problem which was basically the GHZ problem. It was very interesting to see the different ways in which the students would come up with a contradiction for the impossibility of winning the GHZ game. My favorite was the student who wrote a spreadsheet for every single possible strategy and showed that none of those would win. This is such a computer science way to solve the problem: I love it! The students all did remarkably well on the final and I was very happy with their final scores (they may be more or less happy.) One of the students didn’t miss a point the entire term!
This week I’m preparing my lectures for a summer school in Italy. Again it will be a course for graduate students in computer science. Pretty soon Dirac notation will be standard in computer science departments 😉 Here is my favorite quote about Dirac notation:

Mathematicians tend to despise Dirac notation, because it can prevent them from making important distinctions, but physicists love it, because they are always forgetting such distinctions exist and the notation liberates them from having to remember.–David Mermin

CSEP 590tv – Quantum Computing

Well, I just finished my last lecture for the quantum computing class I taught this summer. Now all I have to do is grade the final and submit grades. The class started roughly, with me going too fast, then things smoothed out, and then a tough homework hit, and then things sped up again. Not what I was shooting for, but, well, live and learn. I would say that I am 60 percent happy with the way the class went: i.e. I’d give myself a D.
What would I do different? Lots of things. One is that I might try to teach the course along with one of the quantum simulator programs. These are, after all, professional masters students in a computer science program. This means that the majority are programmers. And programmers, well they like to learn by programming. So I think I would teach it that way for this particular audience.
I have to teach a quantum course in Italy to graduate students in computer science coming up in a few weeks. The course will have twelve hours of lectures and a two hour final examination. How do you talk about quantum computation in twelve hours? Four hours to introduce quantum theory, four hours to build up to quantum algorithms, two hours for quantum error correction, and two hours for quantum cryptography? Or is it better to do more surveying of results? It’s an interesting question and one I’ll be struggling with for the next week.

Teaching Myself to Teach

A confession. When I was an undergraduate, I really didn’t go to classes as much as I should have. In particular, I didn’t go to many of my physics and math classes. Why? Mostly because these were the classes where I had the least problem picking up the material and my own self-motivation to learn the material on my own was almost always enough to carry me through the class. So the classes I attended the most were my humanities classes (to get that valuable B.S. in literature 😉 ) and my elective scientific courses, particularly the courses I took in computational neural science. Now that I’ve started teaching my own class, I wonder how much my own teaching suffers because of my past habits skipping class?
One thing I’ve noticed is that I have a hard time lecturing around a textbook. I have this insane desire to explain the subject material in my own words, and following a textbook closely makes me feel like I am not much more than a glorified parrot. I think, perhaps, this just has to do with my own proximity to the subject matter I’m teaching, quantum computing. Teaching about a subject which is not your own field of research in some ways seems like it would be easier, because you feel less of a desire to make sure you get it just right.
I am also fighting, in my own teaching, the three subject structure which was prevalent at Caltech. The three subject structure was the expectation that a course would involve lectures on one part of the subject, homeworks on another, and tests on a third part. Of course there was always some overlap, but there was also a lot of “thrown them into the fire” homeworks and tests. I can’t count the number of times I realized halfway through a test, “Oh, so this is what that means!” Fine for self-motivated self-learners, but not the best for everyone else.
Anyway, I think I’m slowly beginning to learn to teach. The first lecture for the course, I, uh, how to put this nicely, well I totally misjudge the appropriate difficulty level I should have been shooting for in the classs. In particular, I’m teaching the course to professional master’s students in computer science, some of whom have been out of school for a few years, and so, while I may want to teach them quantum theory in one lecture, this just is not very realistic! So starting in lecture two, we slowed down the pace quite a bit. Now entering into the fifth lecture, we’re beginning to get to things which I would consider truely quantum computing subjects. Now the challenge will be, again, to restrain myself from running rampshot through this material. Certainly there last homework was significantly harder than their first two, so I’m really trying to slow the pace as we enter the really cools stuff in quantum computing. Interestingly, slowing down has resulted in, I think, teaching the material in a careful manner, but has also kept me from teaching the big picture as effectively as possible. Mixing these two styles, big picture and instruction on the details, is something I’m working on.
Well, back to working on my lecture and the next homework set!