2022 March 19,
Carleton College, Winter 2022, Joshua R. Davis, , CMC 324, x4095
A quantum computer is a machine that exploits the strange phenomena of quantum physics — superposition, measurement, entanglement, etc. — to solve computational problems. For some problems, quantum computers can vastly out-perform non-quantum computers. However, identifying these problems and devising quantum algorithms for them is difficult.
This course is an introduction to quantum computing. We focus on the computer-scientific problem of how to devise and analyze algorithms, rather than the physical problem of how to engineer the hardware. After learning some background material, we study key exchange (cryptography), Shor's period-finding algorithm, and Grover's search algorithm. As time permits, we also study sparse matrix algorithms, error correction, and adiabatic computing.
The prerequisites are Data Structures (CS 201), Linear Algebra (Math 232), and a proof course (CS 202 or Math 236). We do a lot of math — so much, that this course sometimes seems like a math course. However, the course also includes a significant programming component, where we build a quantum computer simulator in Python. If you don't know Python, then study it on your own (using the links below or other tutorials). For what it's worth, Python is one of the easiest languages to learn, and we use only the basics. Talk to me if you are concerned about your background.
My understanding of the college's accreditation is that this course requires 150 hours of work. That amounts to about four hours outside of class, for each class meeting. If you find yourself spending much more or less than that, then talk to me.
Your numerical course grade is a weighted average of six scores: participation (5%), homework (5%), Exam A (25%), Exam B (25%), Exam C (25%), and project (15%).
Numerical grades are converted to letter grades only at the end of the term. There are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades (A, B, C, etc.), because I cannot write problems that are so precisely and reliably tuned. Instead, I assign letter grades by comparing students' scores to the course goals. Roughly speaking, a student who meets most of the goals earns a B. A student who meets almost all goals — and sometimes exceeds them — earns an A. A student who demonstrates effort but meets only a few of the goals earns a C. Students, for whom I have insufficient evidence of learning and effort, might earn grades below C.
An advantage of this system is that students are not in competition with each other. Also, students don't suffer when I accidentally write a difficult exam. The disadvantage is that you cannot compute your own grade. Send me e-mail, if you want me to estimate your current grade for you.
If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with Accessibility Resources.
Our class meets in CMC 304 during period 2A (MonWed 9:50-11:00, Fri 9:40-10:40). I view each meeting as an "interactive lecture" or a "lecture/discussion". You are expected to do your fair share of asking and answering questions. You are expected to let other people do their fair share. Sometimes you do group work with one or two classmates.
You are expected to take notes on paper or a tablet. (Typing on a laptop is not recommended, because of all the math and drawing.) The act of taking notes helps get the information into your brain. No photography or other recording is permitted. Except in emergencies, phones should not appear in class.
I try to make the lectures self-contained, but I don't always succeed. So I also give you textbook sections and sometimes my personal notes or tutorials. Conversely, not everything we do is in the textbook.
If you miss class, then e-mail me explaining why. Obtain notes from another student. If you have questions after studying the notes, then we can meet to discuss your specific questions.
Homework consists of working examples, solving problems, and writing proofs, as in other theoretical CS and math courses. You are encouraged to figure out the problems with other students. However, you should always write/type your solutions individually, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is a violation of Carleton's Academic Integrity standards.
Writing is not just for English and history majors. Communication skills are essential to every academic discipline and highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. Consider typing the problem sets in LaTeX, so that you can compose and edit your solutions. I give you some LaTeX examples below.
Homework is handed in on paper. If you need to hand in homework late, then do so. Put it in a separate pile from the on-time homework. Depending on the grader's schedule, it might be graded for full credit, or it might not be graded at all.
Depending on time constraints in any given week, perhaps not all of your homework is graded. In order to ensure full credit, do all of the assigned problems. Although homework itself counts for not much of your grade, it can have a huge effect on your exam grades.
We have three exams.
The goal of the project is to build a library of Python functions that simulate almost all of our quantum computations. In a sense, this project is tangential — the whole point of quantum computers is that they don't work like Python — but implementing abstract mathematical ideas in code is a good way to check that we understand them.
Roughly speaking, project work alternates with homework. That is, every second class day there is no homework, but instead a set of Python functions for you to implement, with unit tests to help you debug. The entire project is due at 5:00 PM on the last day of final exams. However, you are expected to implement and test these functions promptly as they are assigned. Questions about the project might show up on exams. I reserve the right to add progress checks during the term.
Office hours are essentially extra, optional class meetings. No appointment is necessary; just show up. They are now
in my office, which is CMC 324. No photography or other recording is permitted. If you want to schedule an appointment outside office hours, then consult my weekly schedule and e-mail me with several times, at which we are both available.
Our official textbook is Introduction to Quantum Algorithms via Linear Algebra by Lipton and Regan, 2nd edition. It is optional. I do not assign readings or problems out of it. Nonetheless, you might enjoy reading it, to get a treatment different from mine. Here are five other textbooks, which I have placed on two-hour reserve in the library.
Here are some resources about quantum computing and the requisite math.
Here is the start of our Python library for simulating quantum computations.
Here are some Python resources.
Here are some resources for students who choose to use LaTeX.
To help you decode the schedule, let's talk through an example. Friday January 7 is Day 02 of the course. On that day, we learn about complex numbers. I supply you with notes called complex.pdf. You optionally read the notes. You have a homework assignment called Day 02. You make a serious attempt to complete it immediately (before Day 03), but it is due at the start of class on Day 04.
| Date | Day | Topics | Reading | Homework/Project | Due | Notes |
|---|---|---|---|---|---|---|
| W 1/05 | 01 | overview, outline | syllabus | Day 01 | 01 | |
| F 1/07 | 02 | complex numbers | notes | Day 02 | 04 | complex.pdf |
| M 1/10 | 03 | vectors, unitary matrices, one qbit | notes | Day 03 | 05 | complex.py |
| W 1/12 | 04 | one qbit, Bennett (1992) cryptosystem | Day 04 | 06 | ||
| F 1/14 | 05 | Bennett | Day 05 | 07 | ||
| M 1/17 | 06 | two qbits, entanglement, partial measurement | Day 06 | 08 | ||
| W 1/19 | 07 | partial measurement, gates | Day 07 | end | ||
| F 1/21 | 08 | no cloning, Deutsch (1985) problem | 6.2, 8.1, 8.2 | Day 08 | 10 | |
| M 1/24 | 09 | Deutsch, many qbits | 2.0, 3.5 | Day 09 | end | |
| W 1/26 | 10 | entanglement, partial measurement, tensor powers | 6.5, 6.6 | Day 10 | 12 | |
| F 1/28 | 11 | Exam A | ||||
| M 1/31 | 12 | classical vs. quantum, Bernstein-Vazirani (1992) problem | 5.1, 5.3 | Day 12 | end | |
| W 2/02 | 13 | Bernstein-Vazirani, Simon (1994) problem | 10 | Day 13 | 15 | |
| F 2/04 | 14 | Simon | 10 | Day 14 | end | |
| M 2/07 | midterm break | |||||
| W 2/09 | 15 | modular powers, periods | 11.1, 11.2 | Day 15 | 17 | |
| F 2/11 | 16 | Fourier transform, Shor (1994) algorithm | 5.2, 11.3 | Day 16 | end | fourier.pdf, .nb |
| M 2/14 | 17 | Shor | 11.4, 11.5 | Day 17 | 19 | |
| W 2/16 | 18 | finding periods | 11.6, 11.7 | Day 18 | end | periodsFactors.pdf |
| F 2/18 | 19 | factoring, Grover (1996) algorithm | 13.0, 5.5 | Exam B | 20 | |
| M 2/21 | 20 | Grover | 13.1, 13.2 | Day 20 | 22 | |
| W 2/23 | 21 | Grover known k | 13.1, 13.2 | Day 21 | end | |
| F 2/25 | 22 | Grover unknown k, implementing large gates | 13.3 | Day 22 | 24 | |
| M 2/28 | 23 | implementing large gates | Day 23 | end | ||
| W 3/02 | 24 | implementing large gates | Day 24 | 26 | ||
| F 3/04 | 25 | adiabatic quantum computing | notes | Day 25 | end | complex.pdf |
| M 3/07 | 26 | adiabatic | notes | Day 26 | Farhi et al. (2000) | |
| W 3/09 | 27 | adiabatic | notes | |||
| F 3/11 | 28 | Exam C | ||||
| W 3/16 | project due at 5:00 PM |