2018 June 5,
Carleton College, Spring 2018, Joshua R. Davis, , CMC 325, 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 necessary background material, we study Shor's period-finding algorithm, Grover's searching algorithm, error correction, and other topics as time permits. The materials are
Our class meets in CMC 301 during period 1A (MonWed 8:30-9:40, Fri 8:30-9:30). If you want to meet with me outside class, then try to come to my office hours, which are
If you cannot make office hours, then e-mail me to make an appointment, listing several possible times.
Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The advantage of this system is that student grades don't suffer when I write a difficult exam. The disadvantage is that you cannot compute your own grade. Visit me in my office, if you want me to estimate your current grade for you. The following elements contribute.
You are expected to spend about 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than 15 hours, then talk to me.
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. Written and oral communication skills are essential to every academic discipline and 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 will be graded. In order to ensure full credit, do all of the assigned problems.
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 the Disability Services.
This schedule is tentative. It will be adjusted as we proceed. To help you decode the schedule, here is an example. On Day 2 we discuss complex numbers. I've written a tutorial for that material; read it before or after class, to get another treatment. You have four homework problems, which are due at the start of class on Day 3.
| Date | Day | Reading | Topics | Assignment | Due | Notes |
|---|---|---|---|---|---|---|
| M 3/26 | 1 | introduction | Day 1 | 1, 2 | ||
| W 3/28 | 2 | tutorial | complex numbers | tutorial Exercises A, B, C, D | 3 | |
| F 3/30 | 3 | tutorial | complex numbers | tutorial Exercises E, F, H, I | 4 | distortion.py |
| M 4/02 | 4 | 1.2, 1.3, 1.5 | 1 qbit | Day 4 | 6 | |
| W 4/04 | 5 | 1.2, 1.3, 1.5, 1.6 | 2 qbits | finish Day 4 | 6 | entanglement.py |
| F 4/06 | 6 | 1.7, 1.8, 1.9 | 2 qbits | Day 6 | 8 | |
| M 4/09 | 7 | 1.7, 1.8, 1.9 | 2 qbits | Day 7 | 9 | |
| W 4/11 | 8 | 2.2 | Deutsch's problem | Day 8 | 11 | |
| F 4/13 | 9 | Chapter 1 | n qbits | Day 9 | 11 | |
| M 4/16 | 10 | Exam A | ||||
| W 4/18 | 11 | 2.4 | Bernstein-Vazirani's problem | Day 11 | 13 | |
| F 4/20 | 12 | 2.5 | Simon's problem | Day 12 | 14 | |
| M 4/23 | 13 | 2.3 | Simon's problem | Day 13 | 15 | |
| W 4/25 | 14 | Chapter 4 | Grover's algorithm | none | ||
| F 4/27 | 15 | Chapter 4 | Grover's algorithm | Day 15 | 17 | |
| M 4/30 | Midterm Break | |||||
| W 5/02 | 16 | Chapter 4 | Grover: applications | Day 16 | 18 | |
| F 5/04 | 17 | Chapter 4 | Grover: unknown m | |||
| M 5/07 | 18 | Chapter 3 | Shor: number theory | Day 18 | 21 | |
| W 5/09 | 19 | Chapter 3 | Shor: Fourier analysis | none | ||
| F 5/11 | 20 | Exam B | ||||
| M 5/14 | 21 | Chapter 3 | Shor: subroutine | Day 21 | 23 | |
| W 5/16 | 22 | Chapter 3 | Shor: probability | Day 22 | 24 | |
| F 5/18 | 23 | Chapter 3 | Shor: factoring | none | ||
| M 5/21 | 24 | Chapter 5 | error correction | Day 24 | 27 | |
| W 5/23 | 25 | Chapter 5 | error correction | none | ||
| F 5/25 | 26 | Chapter 5 | error correction | Day 26 | 27 | |
| M 5/28 | 27 | Chapter 5 | error correction, conclusion | |||
| W 5/30 | 28 | Exam C |
With more time, we might have covered...