Quantum Computing for Beginners

A class for quantum enthusiasts

Category: Lecture Notes

Final class meeting

Here are the slides for the final lecture, where we graded Chapter 7 problems and discussed how to encode NP-complete optimization problems onto a D-Wave architecture, as well as designing a cryptosystem around any such problem.

I’d like to gratefully acknowledge the following people:

  • my students for their effort and creativity this quarter
  • Stephen Rice for his illustrations
  • anyone who sent me support and feedback over Facebook, Twitter, and email, especially Ryan Bowler, Blake Stacey, and Dave Bacon
  • my advisor Aram Harrow and the quantum theory group at UW

Unfortunately, I didn’t have time to finish the historical narrative that went along with the course material.

However, I intend to keep developing this class, and I’d like to offer improved versions in the future. I hope you enjoyed following along as much as I enjoyed teaching the class. Happy holidays!

Lecture notes on quantum machine learning and D-Wave

Here are the slides from class on Tuesday, December 4th, on the connection between quantum computing and machine learning via the quantum annealing algorithm, and also a little bit about the D-Wave architecture.

Shor’s factoring algorithm lecture

Here are the slides from my Shor’s factoring algorithm lecture.

Many facts about number theory must be taken for granted for so short a presentation, unfortunately, but in future versions I would like to present more intuition for the Chinese Remainder Theorem.

First class meeting

Quantum computing for beginners has begun! I was very pleased with the first class meeting this past Tuesday. Students came up with really creative examples of analog computers (in nature and man-made), probabilistic machines, and systems which failed to operate outside of their designed environments. I’ll ask them to post some of their ideas in the comments. The main point of the lecture is that computation is physical.

What I want to do in the class is help develop physical intuition. As computer scientists, we are not used to dealing with physical objects that take up space, have mass, dissipate energy. We are used to creating virtual worlds, to defining the rules for the universe and executing a program for the computer to work out the consequences and enforce these rules. It may be frustrating or repetitive for you to see so many examples, when you are used to abstracting out the general principle. But details are powerful, and at the beginning it’s not clear what you are trying to abstract away and what is essential that you are trying to keep. Details add color and spice, details help you remember. Rather than giving you facts, I want you to have a felt experience of computation.

Here are the Lecture 1 slides (Chapter 0), and now some special bonus notes, like the extra features on a DVD. First, a correction. Aram pointed out that I said the FERMIAC was built before the ENIAC, but in reality, Fermi designed and built it during the period when the ENIAC was being moved and non-functional. Thanks to him, and also to Lukas Svec for telling me about the Fermiac in the first place and machining an actual replica in the UW Physics machine shop!

Some bibliography links:

Bloch sphereEnigma machine photographUW Blinov ion trap group photoPhotosynthesis photoFlock of birds photoReview article on functional quantum biology, including photosynthesisArticle on avian compassSteiner tree soap bubble analog computerSlime mold solving a mazeCrab nebula pulsar as taken by Chandra, Spirals in pine cone seeds follow the Fibonacci sequence

Some of you may be wondering why I am spending so much time talking about the people, stories, and events surrounding the birth of quantum physics and computer science. Isn’t it enough to learn the abstract models and mathematics and write some code? There are a few reasons to care about the history and culture surrounding scientific discoveries.

First of all, science doesn’t happen in a vacuum, and human beings in the 1940s are pretty much the same as human beings today. Learning about their motivations, fears, and desires, both in research and in their personal lives, can help us understand where their ideas came from, including their limitations. My two advisors, Dave and Aram, who taught previous quantum computing classes, are fond of saying that quantum computers would have happened much sooner if the very scientists developing it had not been so stubborn in clinging to classical intuitions and classical ways of thinking. But alas, it’s easy for us to say. Even today, quantum physics is still highly non-intuitive. We didn’t grow up with quantum at medium scale of human life, the way we experience a ball bouncing on the ground or an apple falling out of a tree. By the way, Chris Fuchs has a great book titled “Coming of age with quantum information” which I misremembered as “Growing up with quantum”. Dave lent it to me once, and it was a great spring break read.

Second of all, they can also inspire us to make new discoveries. These discoveries may be more recent, but they are not more modern. The scientific method, and the curiosity that drives it, are exactly the same today as they were during the Enlightenment and in the ancient world.

Third, scientists are human beings embedded in history. I’m sure some quantum physicists in the 1930s wanted to ignore politics and were very annoyed when WWII broke out and they could no longer freely travel and talk to their other scientist friends. We are embedded in the history of the future. Students in the year 2100 will wonder why we took so long to build a quantum computer, too. So pay attention!

And finally, history is fun, and I said so. Okay that’s all.