2020 July 11,
Carleton College, Spring 2020, Joshua R. Davis, , CMC 324, x4095
A quantum computer is a machine that exploits the strange phenomena of quantum theory (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 covering some background material, we study key exchange (cryptography), Shor's period-finding algorithm, Grover's search algorithm, error correction, and other topics as time permits.
The official prerequisites for this course 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. So I try to leaven the math with Python programming exercises. 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.
Finally, because we are learning remotely during a pandemic, there may be many disruptions and changes. We all need to accommodate, adjust, and empathize. All of this syllabus is subject to revision. However, working hard on our studies can give us dignity, accomplishment, and even comfort. So I intend to conduct this course in as normal a manner as possible — for example, covering the usual material with the usual rigor, if we can.
Here are some course materials.
Here are some more resources, which are not specific to this course but still relevant.
Although this term's final grading is SCrNC, I intend to maintain my usual detailed grading system: numerical grades, mapped to letter grades at the end of the term, only then mapped to SCrNC. For then your work gets the feedback that it deserves.
Your numerical course grade is determined by your fulfillment of the following responsibilities, which are detailed in the sections below. I reserve the right to tweak the percentages based on how the term proceeds.
Letter grades are assigned to numerical grades according to an approximate curving process. There are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades (A, B, C, etc.). Rather, I assign grades by comparing the students to each other, to earlier students, and most importantly to the course goals. An advantage of this system is that student grades don't suffer when I write a difficult exam, for example. 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 performance in this course, then let me know in the first week of class (or as soon as it arises). You may need to make official arrangements with Disability Services.
Our class meets for discussion during period 2A (MonWed 9:50-11:00, Fri 9:40-10:40). These discussions correspond to the interactive parts of a normal class meeting. We use Zoom or Google Hangouts Meet or something like them. You are required to participate in these discussions. Discussions are not just for English and history classes. Communication skills are essential to every academic discipline, and they are highly prized by employers.
During a discussion, you are expected to maintain a distraction-free environment: a quiet place (if possible), no phone, etc. You are required to take notes, just as in a normal class meeting. The material involves many diagrams and matrices, so you need to use paper or an electronic device that supports rapid drawing. Typing on a laptop is probably not adequate.
When technical problems prevent you from participating in a discussion, send me e-mail about your technical problems (if possible). Do not suffer in silence. Depending on how this aspect of the course goes, we might start meeting in small groups rather than all together.
I hold office hours as in any normal term. In a sense, office hours are extra, optional discussion time. Also, I intend to have a one-on-one meeting with each student early in the term.
You do not have permission to redistribute any images, video, audio, etc. from any of these discussions. The discussions should be a safe space, where no one feels that they're on display. Thank you for respecting the rights of everyone.
I am preparing pre-recorded video lectures. They correspond to the non-interactive parts of a normal class meeting. There might be 35 or 45 minutes of video per class meeting, broken into chunks by topic. Currently the lectures are recorded at my office chalkboard. As the situation evolves, I might switch to a whiteboard at home or even a tablet computer.
You are required to watch each video on its assigned day. You are again required to take notes, because the act of taking notes helps get the information into your brain.
On the other hand, you are free to choose the time of day of your viewing. You are able to pause, rewind, take breaks, etc. I hope that the viewing is not unpleasant.
I try to make the lectures self-contained, so that you don't have to do a lot of other reading. But I don't always succeed. So I also give you textbook sections and sometimes my personal notes or tutorials. They can fill in details or give you another perspective. You should at least skim them, to make sure you're not missing anything. Conversely, not everything we do is in the textbook.
When technical problems prevent you from viewing a video, then do the reading strenuously. Also send me e-mail about your technical problems (if possible). Do not suffer in silence.
The videos are my intellectual property. I retain copyright on them. You do not have permission to redistribute them. Thank you for respecting my rights to my work.
Our homework comes in two flavors: problem sets and programming assignments. For a programming assignment, you submit a Python file. For a problem set, you submit a PDF or other image file. The problem sets are a mixture of proofs and calculations. I strongly encourage you to type the problem sets in LaTeX. LaTeX lets you edit and compose your solutions carefully, and I give you LaTeX examples and templates for the more difficult typesetting. However, you may, if you insist, substitute other software for LaTeX. You may even write your solutions by hand and send me high-quality scans or photographs.
On homework, 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 they are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation.
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.
If you know me, then you know that I have a standard late pass policy. But let's not use it this term. Let's tentatively adopt this policy instead: If you submit homework late, then you must e-mail me when you submit it, and your e-mail must explain why the work is late.
You are expected to spend about 10 hours per week on this course outside lecture/discussion. Some students need to spend more than 10 hours. If you find yourself spending more than 15 hours, then talk to me.
We have three exams. Probably they are similar in format to the exams from spring 2018. However, I might make some changes. Perhaps one of the exams is oral.
The collaboration that is encouraged on homework is forbidden on exams. Academic Integrity standards still apply. Communication skills are still valued.
Because of the COVID-19 pandemic, this schedule is 25 days rather than the usual 28.
| Date | Day | Reading | Topics | Assignment | Due | Notes |
|---|---|---|---|---|---|---|
| M 4/06 | 01 | syllabus | introduction, overview | Day 01 | 01, 03 | |
| W 4/08 | 02 | tutorial | complex numbers, vectors | 1.1, 1.2, 2.1, 2.3, 3.2 | 04 | Complex Linear Algebra |
| F 4/10 | 03 | tutorials | unitary matrices, one qbit | 5.1, 5.2, 5.3; A, B | 05 | Complex Python |
| M 4/13 | 04 | one qbit, Bennett (1992) | Day 04 | 06 | ||
| W 4/15 | 05 | qc.py | Bennett (1992), two qbits | Day 05 | 07 | qc.py |
| F 4/17 | 06 | entanglement, partial measurement | Day 06 | 08 | ||
| M 4/20 | 07 | pp. 39-40 | gates, no cloning | Day 07 | 09 | |
| W 4/22 | 08 | 1.1-1.6 | Deutsch (1985) problem, many qbits | Day 08 | 10 | |
| F 4/24 | 09 | 1.7-1.10 | entanglement, partial measurement | Day 09 | 11 | |
| M 4/27 | 10 | 2.1, 2.2 | gates, tensor powers | Day 10 | 12 | |
| W 4/29 | 11 | 2.4 | Bernstein and Vazirani (1992) problem | Exam A | 12 | |
| F 5/01 | 12 | 2.5 | Simon (1994) problem | Day 12 | 14 | |
| M 5/04 | Midterm Break | |||||
| W 5/06 | 13 | 3.1, 3.2 | Simon (1994) problem, modular powers | Day 13 | 15 | |
| F 5/08 | 14 | 3.4, 3.5 | periods, Fourier transform | Day 14 | 16 | |
| M 5/11 | 15 | 3.7 | Shor (1994) algorithm | Day 15 | 17 | |
| W 5/13 | 16 | 3.3, 3.10 | finding periods, RSA | Day 16 | 18 | |
| F 5/15 | 17 | 4.1, 4.2 | factoring, Grover (1996) algorithm | Day 17 | 19 | |
| M 5/18 | 18 | 4.2, 4.4 | Grover (1996) algorithm | Day 18 | 20 | |
| W 5/20 | 19 | 4.4, 4.5 | Grover (1996) algorithm | Day 19 | 21 | |
| F 5/22 | 20 | 4.1, 5.1 | Grover (1996) applications, classical error correction | Day 20 | 22 | |
| M 5/25 | 21 | 5.2, 5.3 | three-qbit code, general errors | Exam B | 22 | |
| W 5/27 | 22 | 5.6, 5.7 | Steane (1996) code | Day 22 | 24 | |
| F 5/29 | 23 | 5.4 | Steane (1996) code, implementing large gates | Day 23 | 25 | |
| M 6/01 | 24 | 2.6, 5.8, 4.3 | implementing large gates | Day 24 | ||
| W 6/03 | 25 | 3.6 | implementing large gates, adiabatic quantum computing | |||
| M 6/08 | Exam C |