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.

Ski Season 05-06, Day 1

This last Saturday I had the opportunity to go on my first ski trip of the season. Amazingly the northwest has been getting pounded by snow over the last few weeks. Now this posed a problem, because, as some of you may recall at the end of last season I did the stupidest thing I’ve ever done, and had to be rescued by the ski patrol. In the process, my skis from last year were completely destroyed. Well with the snow starting to fall, this made me extremely nervous. Would, after nearly twenty years of skiing I finally be forced to actually rent skis again? The horror! Well I went to rent skis at a local shop, and well, you know how it is. You see the nice pretty new skis and you just can’t resist. So I’m now the proud owner of a pair of 2005 Rossignol Bandit B2 182cm skis. And a helmet.
Anyway, we made the two and half hour drive from Seattle to Mt. Baker. The snow was good. They had a bit over a foot of new snow. The first runs were very nice and at the end of the day, when I’d remembered how to ski again, it began snowing again and so was again very nice. Mt. Baker is a very flakey ski resort. They have like one trail map sign for the entire resort. There were a couple of place I would have liked to ski, but they need another few feet of snow before I take my new skis on those runs.
Two highlights from the trip. One was early in the day. I hit a jump, not realizing that there was another jump immediately after it. I ended up nearly eating my ski tips, but somehow managed to stay upright over the second jump. I’m not sure what happened to my friend Bill who was following me over these two bumps. All I know is that we were under the chair lift and the most amazing groans and shouts of awe came from the lift. It must have been pretty good to illicit such a vocal response. The other highlight came at the end of the day. It was snowing and the conditions were such that you couldn’t see ANYTHING. I mean I had absolutely no depth perception. So I skied by following one of my fellow travels, a fellow by the name of Brendan. He’s a boarder and he was flying down the hill with me close on his heals. Turn. Turn. Turn. Tur….whooops that turn was in the middle of the air. Brendan had hit a dropoff mid turn. I was able to stop, but I can tell you there is nothing funnier than watching the increasing panic in someone who is midair and wondering, “where the heck is the ground.” Priceless.

Talking in L.A. Talking in L.A. Nobody Talks in L.A.

Yesterday I gave a talk on quantum computing in Los Angeles at math-club. What is math-club? From their website (“be there or be square”):

People who like books and stories have movies, libraries, and even book clubs to amuse them. Those interested in math and logic have amazon.com and the occasional brain teaser at the back of in-flight magazines.
MATH-CLUB was formed to engage a group of LA’s math-inclined people in analytical discussions under an easy going atmosphere.
The club got rolling under suitably informal circumstances — its founder, Roni Brunn, brought up the idea for a math club at a bar and was lucky enough to do so within ear shot of a friend, Matt Warburton, who liked the concept and thought of others who would as well. Soon after that, we had our first math club meeting.
Stewart Burns lectured on a Sunday afternoon in September, 2002, to a crowd that included David X. Cohen, Kirsten Roeters, April Pesa, Ken Keeler, Daisy Gardner, Sean Gunn, James Eagan, and, of course, Matt, using most horizontal surfaces at Roni’s apartment as seating.
Because many of those most actively involved with MATH-CLUB do have writing credits at shows like “The Simpsons” and “Futurama,” some assume the club is only the province of professional Hollywood writers. In fact, the club as a whole is a diverse group of people who punch the clock as professors, computer programmers, musicians, actors, designers, journalists, and documentarians.
Similarly, people come to meetings with a wide range of math backgrounds. Some of the members have advanced degrees in math and have been published; some are recreational users of math. People do ask questions and explore the topic as a group. We kick off meetings with a cocktail party.

Who could resist talking to such a club? Certainly not me. Especially when I received an email from the organizer, Roni Brunn, which had as it’s subject “math and simpsons.” Such subject lines stimulate approximately 90 percent of my brain. If you include the word “ski” as well, then the extra 10 percent is activated and I go into epileptic seizures. Not a pretty sight.
I am especially fond of the math club analogy with book clubs (which were described to me by one of the people present last night as “mom’s drinking night.” Crap, now I’m going to get an email from my mother.) Why aren’t there more math clubs in the mold of book clubs: where small groups get together to hear about subjects which stretch their critical brains? I certainly think it’s a grand idea and am tempted to start a math club myself (but in Seattle we replace writers with programmers?)
When I was at Caltech I would often attend the talks in fields outside of physics/computer science. I called it “my television.” Certainly hearing a biology or geology talk and trying to discern what the heck they were talking about made me feel like a total moron. But whenever you hear a good talk outside of your field, you get a little bit of the feeling for what is going on, and this feels great. I personally wish that more graduate students would do this in order to help combat the graduate student fatigue which comes from being far to narrowly focused and not remembering why it is that all of science is interesting.
Anyway, it was a fun talk, and hopefully I didn’t punish people too much. When I was in Italy recently, I noticed that when I noticed that the students were not understanding the English I was using, I would try to fix this by reverting back to speaking in idioms, which are simpler, of course, but totally incomprehensible to the Italian students. I noticed last night that I sometimes do a similar thing when I give a talk: when I’m talking about something and I think people are lost, I oscillate back to a language which is far simpler but whose content doesn’t really help to discern my original meaning. What I need to learn to do is to ramp down to medium levels with content. Ah well, much to learn about this “giving talks” thing.

Jerry Rice Retires (1985-2004)

And now, for a totally different kind of post…a post on American football!
Jerry Rice, the greatest wide receiver in football history, announced his retirement from the National Football League today. I grew up watching Jerry Rice play for the super bowl winning San Francisco Forty Niners and he is (probably amusingly to most of you) one of my personal heros. One of my most treasured posessions is a signature of Rice’s (“To Dirty Dave, Peace, Jerry Rice”) on a copy of an article in the Los Angeles times which described some of the research I did while I was an undergraduate at Caltech.
Jerry was the son of a bricklayer, and grew up helping his father lay bricks. One of his brothers would throw bricks up and Jerry would catch them for his father to place. An ominous sign, I suppose, for someone who would go on to catch a thousand five hundred receptions in an NFL career spanning twenty years. During those years, he won three superbowls and claimed almost every single recieving record in the NFL. He is the all time leader in touchdowns (207 versus 2nd best Emmit Smith’s 175), receiving yards (1549 versus 2nd best Cris Carter’s 1101), receiving yards (22895 versus 2nd best Tim Brown’s 14934), and the list goes on and on.
Growing up watching Jerry Rice was a treat which is hard to explain. He and Joe Montana, arguably the greatest quarterback of all time, formed an awesome duo. With Joe and Jerry in the game, one never, ever, thought that the 49ers couldn’t pull out a victory. Montana recorded an astounding 31 come from behind victories in the fourth quarter, with Rice often being a central figure in these amazing comebacks. To this day, I have a hard time not believing that a come from behind isn’t possible, no matter how the ridiculous the score is, in large part due to these two remarkable players. Thinking of Jerry brings back the halcyon days of my youth, when anything was possible, and no obstacle, no matter how seemingly insurmountable, could not be overcome.
Just the other day, I looked up a game which has stuck in my mind all these years later. My friend Luis and I were going camping with his father, and possibly also his brother Isaac. We stopped to get some supplies, listening to the 49er game on the radio. The game appeared to be over, so we turned off the radio. When we got back into the car, we heard the anouncer say “Wersching lines up to kick the winning extra point.” Now Ray Wersching was the 49er’s kicker: somehow the 49ers had come back from absolute disaster and won the game! Here, is, what happened while we were in the store:

The Cincinnati Bengals led the San Francisco 49ers by six points in the closing seconds of a game played at Cincinnati’s Riverfront Stadium on September 20, 1987; faced with a fourth down in their own territory, Bengals head coach Sam Wyche called a running play. The 49ers had no timeouts remaining, and it was Wyche’s belief that this play would successfully run out the clock. However, Wyche overlooked the fact that under NFL rules, the clock is automatically stopped on any play that results in a change of possession – and that is what occurred on this play as the Bengals did not gain enough yardage on it to obtain a first down. There were six seconds remaining when the clock was stopped; the 49ers then took possession of the ball,
and on the ensuing play Joe Montana threw a touchdown pass to Jerry Rice, and the successful extra point attempt that followed gave San Francisco a 27-26 victory.

What I recall reading the next day was that Montana gave Rice a hand signal at the line of scrimage and then threw a long pass to Rice, who made a towering leap and grab in the end zone. The number of similar stories that Jerry and Joe orchastrated is huge, and I could go on and on about these fantastic stories.
But what I will miss most about Jerry Rice is his work ethic. And this is one of the reasons he is among my personal heros. Jerry’s workout ethic is legendary, involving a kind of focus and dedication which may be unrivaled in or outside of sport. Particularly during my years at Caltech, where I was working my butt off, I remember thinking of him as a role model: that talent is important, but hard work and talent are a vicious combo. Whenever I think I might be working hard, I think about Jerry Rice, and think, “sheesh, I’m not working hard at all!” Whatever you may think about sports, one has to say that this kind of role model is hard to come by and for this I will always thank Jerry Rice.

Italy

Well I’m back from a one week trip to Italy to teach at “GII Scuola di Dottoratio in Ingegneria Informatica” held at the University of Siena.
We arrived into Rome on Saturday after spending a good portion of our time on the Detriot/Rome flight playing the inflight trivia game. Nothing like a slow trivia game to pass the hours. In Rome we stayed in the Hotel Forum, which is very centerally located, just a stones throw from these ruins
Civilizations Do Fall
and a hop skip and a jump to a certain, very famous, fountain:
Doofus
On Sunday we made our way to Florence, where we did the requisite looking at some cathedrals
Church Halos
Unfortunately we didn’t get the chance to see it, but apparently Galileo’s embalmed finger is in Florence. I wonder which finger it was? Actually I also would have liked to see if the church where Galileo sat timing the period of the swings of the chandeleers allowed h
After Florence, we headed to Siena. Siena is a very beautiful medieval town on a hill. It is filled with tourists. We were there just after Siena’s famous Palio horse race. In the Palio di Siena, the seventeen different neighborhoods (contrades) of Siena compete against each other for grand bragging rights and a whole lot of pride. While we missed the actual race, the team that won this years race had not won in over forty years. Needless to say, this meant that they were still celebrated when we arrived, and, we were told, would continue to celebrate for as many days as years since they had last won the Palio! Part of this celebration involves things like going into enemy contrades late at night and pounding drums and singing songs taunting the enemy.
While in Siena, I taught here
I Taught Here
Well, actually the venue where I taught was the school of Economis at the University of Siena, whose entrance is just to the right of this large church. I taught twelve hours of lectures to computer science and engineering graduate students on quantum computing. The lectures went well, I think, and they really treated us very nicely in Siena.
Before leaving on Saturday, I got a chance to do some siteseeing. I felt right at home…here are some Popes

Before the twenty four hour trip back home, I bought myself a nice big book of Sudoko. If you haven’t tried Sudoko, please take it from me and avoid Sudoko at all costs! This little logical number game is very addictive. I must have spent twelve hours on the trip home working on these puzzles.

My New Toy

Just in time for the end of the semester, my new tablet pc arrived.
My New Toy
It’s a monster Tecra M4 and so far I must say I love it (once I removed all the bloatware and the ugly stickers!) That’s a picture of Mt. Shasta, a volcano near where I grew up, displayed on Google Earth. I’m really looking forward to taking notes with this thing. One thing that is certainly cool is that the size of my screen is such that an entire page of pdf is just about the same size as the real thing:
No Scrolling

Been Around the World, and I, I, I…

One of the cool things about being a scientist these days is that the level of international collaboration is fairly high, and this means that one gets to make exciting trips to exciting lands. Last week I booked some travel for the end of the summer. Italy and Singapore. What a rough rough life!

Can Good News Cure a Cold?

First the bad news. The bad news is that I am fighting a really nasty cold. I can hear a little more out of my right ear than yesterday, but I’m still pretty plugged up. Anyone who knows any home remedies that don’t involve a hot potato, feel free to advise 😉
The good news is that today we recieved notification that a NSF grant which I had applied for with Mark Oskin has been officially awarded. This is the first grant I’ve applied for, and I’m just going to sit here and enjoy the feeling of batting one thousand, because I know I’m lucky and I know that the long hard slog for grants is destined to smash my ego multiple times in the future. As many of you may know, I have been extremely lucky to find a position here at the University of Washington, during a time when my family has been undergoing quite a lot of, how shall I put it, difficult transitions. In many ways, the computer science and engineering department here was taking quite a gamble on me, and I can only begin to express how appreciative I am for what they have done for me. The awarding of this grant is, then, I hope, the beginning of their gamble paying off. It will certainly mean that I have a more certain future. Now if only this good news could cure my cold.

Back!

Posting has been nonexistent because I’ve been traveling. I’m now back from giving a lecture at the 4th biannual SQuInT student retreat, held at USC and organized by Todd Brun. I’ve been lucky enough to attend all four such retreats, once as a student, and three times as a lecturer (once as a graduate student, once as a postdoc, and once as whatever it is I am now 😉 .) This year I got the opportunity to lecture on quantum algorithms. I’ve put the contents of my slides online here.
The student retreat was a lot of fun, including a trip to the King Tut exhibit at LACMA. Unfortunately, my enjoyment was tempered by the nasty nasty cold I’ve come down with. I can’t hear anything out of my right ear. Bah!
SQuInT, by the way, stands for Soutwest Quantum Information and Technology Network. Yeah, someone must have been smoking something when they thought that one up 😉

FOCS 2005 Papers

The list of 2005 FOCS (46th Annual IEEE Symposium on Foundations of Computer Science ) accepted papers has been posted here. I see four quantum papers (out of 62, one to be announce). They are

“The Symmetric Group Defies Strong Fourier Sampling,” Cristopher Moore, Alexander Russell, and Leonard J. Schulman
“Cryptography in the Bounded Quantum-Storage Model,” Ivan Damgaard, Serge Fehr, Louis Salvail and Christian Schaffner
“Quantum Information and the PCP Theorem,” Ran Raz
“From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups,” Dave Bacon,Andrew M. Childs and Wim van Dam

I guess I can now officially call myself a “theoretical computer scientist.” Does this mean if someone says to me “Hermitian matrix” I cannot immediately follow with the words “diagonalize it”?