2018 June 5,

CS 358: Quantum Computing

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.

Standards for Work

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.

Special Accommodations

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.

M 3/261introductionDay 11, 2
W 3/282tutorialcomplex numberstutorial Exercises A, B, C, D3
F 3/303tutorialcomplex numberstutorial Exercises E, F, H, I4distortion.py
M 4/0241.2, 1.3, 1.51 qbitDay 46
W 4/0451.2, 1.3, 1.5, 1.62 qbitsfinish Day 46entanglement.py
F 4/0661.7, 1.8, 1.92 qbitsDay 68
M 4/0971.7, 1.8, 1.92 qbitsDay 79
W 4/1182.2Deutsch's problemDay 811
F 4/139Chapter 1n qbitsDay 911
M 4/1610Exam A
W 4/18112.4Bernstein-Vazirani's problemDay 1113
F 4/20122.5Simon's problemDay 1214
M 4/23132.3Simon's problemDay 1315
W 4/2514Chapter 4Grover's algorithmnone
F 4/2715Chapter 4Grover's algorithmDay 1517
M 4/30Midterm Break
W 5/0216Chapter 4Grover: applicationsDay 1618
F 5/0417Chapter 4Grover: unknown m
M 5/0718Chapter 3Shor: number theoryDay 1821
W 5/0919Chapter 3Shor: Fourier analysisnone
F 5/1120Exam B
M 5/1421Chapter 3Shor: subroutineDay 2123
W 5/1622Chapter 3Shor: probabilityDay 2224
F 5/1823Chapter 3Shor: factoringnone
M 5/2124Chapter 5error correctionDay 2427
W 5/2325Chapter 5error correctionnone
F 5/2526Chapter 5error correctionDay 2627
M 5/2827Chapter 5error correction, conclusion
W 5/3028Exam C

With more time, we might have covered...