CS 150: Quantum Computer Science (Spring 2023)
Course description:
This is an elementary-level introduction to quantum computing through the
computer science lens. One of the goals of this course is to present a
language of quantum mechanics that is accessible to students working in computer science
and vice versa. Topics include Hilbert spaces, the Dirac notation, the Schrödinger
equation, quantum circuits, quantum Fourier transforms, quantum algorithms,
quantum memory, quantum machine learning, and the quantum black-box model.
Students from different areas of engineering and sciences such as computer science, physics,
electrical engineering, mathematics, or chemistry who wish to learn about the computer science
foundations of quantum computers can benefit from this class.
General Information
Class Information:
- Class schedule: Mon/Wed 3:00-4:15pm
- Class location: Bromfield-Pearson Room 007
- Office hours: Tue 2-3 pm, Fri 9-10 am or by appointment
- Recitations: Fridays, 12-1pm in SEC Anderson #309
- TA office hours: Mondays 12-1 pm, JCC 542
- Piazza: https://piazza.com/tufts/spring2023/cs150
Instructors Information:
- Instructor's name: Saeed Mehraban
- Email: Firstname.Lastname@tufts.edu
- Office: JCC-465
- TA: Michael Joseph
- TA Email: Firstname.Lastname@tufts.edu
Special dates:
- Midterm exam: Monday, March 13, 3:00-4:15 pm, at Bromfield-Pearson #007
- Final exam: Friday, May 05, 3:30-5:30 pm, at Bromfield-Pearson #007
- Deadline to Drop: February 22 is the last day for AS&E students to DROP Full Term courses without
record of enrollment.
- Deadline to withdraw for a grade of W:
- May 1 is the last Day for graduate students to WITHDRAW from Full Term and Receive a Grade of W.
- April 5 is the last Day for Undergraduate AS&E Students to WITHDRAW from Full Term Courses and Receive a Grade of W.
- Last day of classes: May 01 2023
- Scheduled class cancellations:
- No Classes on February 20, Presidents’ Day Observed (University Holiday) — there will be a class on Thursday 2/23, 3:00-4:15 instead.
- No classes on the week of Monday 03/20; spring break.
- No classes will be on 04/17 (Patriots’ Day) — substitute class on Friday 04/20.
- There will be no classes on April 19; make-up day.
- Out of schedule classes: There will be a classes on Thursday 2/23 and Friday 4/20, 3:00-4:15 (re- placement for Monday 2/20 holiday and 4/17, respectively)
Quick Links:
Announcements
Course Logistics:
Grading Policy
Course Material:
Rules, Accomodations, & Resources
Announcements:
03/15: Problem set 6 is released.
04/01 : Problem set 5 is released
03/01: Problem set 4 is released.
02/14: Problem set 3 is released.
02/03: Problem set 2 is released.
01/25: Problem set 1 is released.
01/23: Please complete the (ungraded) pre-assessment survey posted on the gradescope.
01/18: Please join gradescope via the entry code ZZ48Y6.
01/18: Please join Piazza through https://piazza.com/tufts/spring2023/cs150 .
Course Logistics
Prerequisites:
The main requirement for this course is linear algebra (MATH 70 or equivalent). Basic familiarity with discrete math, algorithms, and calculus is also recommended.
Textbook:
Students are encouraged to consult the following textbooks as a basis for learning:
Tufts has kindly provided a digital version for the book by Mermin (see the link above);
we are working to do the same for the book by Nielsen and Chuang.
You are not required to purchase these textbooks in order to complete this class.
The below schedule is an approximation of what we will cover during the class. A pdf version of the syllabus
can be found here.
Main:
- Overview
- Introduction to quantum mechanics.
- What is computation?
- Reversible computations
- Matrix representation of computations
- Quantum computation.
- Quantum protocols (quantum games, teleportation).
- The quantum black-box model.
- The Deustch-Josza problem
- The Bernstein-Vazirani problem
- The Simon problem
- Quantum Algorithms.
- Quantum Fourier Transform
- Shor's Factoring
- Grover's search
- Quantum Simulation
- Solving linear systems
- Noise, Fault-tolerance and error-correction.
Special topics:
- Computation with magic states.
- Adiabatic quantum computation.
- Quantum machine learning
- The stabilizer formalism
- Complexity
Assignments
Grading rules:
There are 6-8 problem sets, a midterm exam and a final exam. 10% of the overall is class participation;
participation also includes Piazza, office hours and recitations. Please let us know in advance if you will miss a class.
Please consult with the instructor if you have missed or will miss more than three classes.
- 10%. Class participation.
- 15% Midterm exam
- 40%. Problem sets
- 35%. Final exam.
10% of your grade for the problem sets is considered extra credit. E.g., if your overall grade for problem sets is 80/100,
we will scale your grade to 88/110 and then apply your extra credit, and you will get 88/100.
How to submit the assignments:
Please submit your problem sets via gradescope by the prescribed deadline;
please contact us in advance if you need special arrangements. Please join gradescope via the entry code ZZ48Y6.
Late submission policy:
No late submissions will be accepted.
You can discuss your ideas with your classmates during the preliminary stages of working on your problem sets,
but all assignements should be written individually using your own words.
If you consulted any source (classmates, friend, TA, textbook, paper, faculty member, etc.) please cite that
source in your submission.
Course Material
This section will be developed as the semester unfolds.
Thanks to Tufts libraries the digital copy of the book by Mermin is available at this link.
Problem sets
Suggested reading
Please note that the "preliminary notes" which I put out for some lectures are my personal notes which I use before the classes.
You can use them if you find them helpful.
The notes you take from the class are the main references for this course.
I do not follow exactly from a specific reference.
You are only responsible to know the topics we cover in class. You can use the textbooks to help help you understand specific
topics better.
Below each lecture I will put approximate
reading suggestions. If there are topics that were not covered in class
you can view them as optional reading (which would help you gain deeper understanding of the course).
Overview and history
- Lecture 1 (01/18): History and outlook [ Preliminary notes]
Models of computation
- Lecture 2 (01/23): Reversible computation [ Preliminary notes]
- Lecture 3 (01/25): Matrix representation of classical computations [ Preliminary notes]
- Reading: 1.5-1.6 of Mermin's book.
- Lecture 4 (01/30): Unitary computation [ Preliminary notes]
- Reading: Chapter 1 of Mermin's book.
- Read section 2.1.7. of Nielsen Chuang for tensor product.
Linear algebra backgound
Please use these lecture notes for the preliminary mathematics background for this course.
- Lecture 5 (02/01): Introduction to linear algebra [ Preliminary notes]
- Reading: Section 2.1 of Nielsen Chuang.
- Lecture 6 (02/06): Introduction to linear algebra (continued)[ Preliminary notes]
- Reading: Section 2.1 of Nielsen Chuang.
- Lecture 7 (02/08): Linear algebra aspects of quantum computing[ Preliminary notes]
- Reading: Section 2.1 of Nielsen Chuang.
- Reading: Section 2.2 of Nielsen Chuang.
- Lecture 8 (02/13): Linear algebra aspects of quantum computing contintued[ Preliminary notes]
- Reading: Section 2.2 of Nielsen Chuang.
Quantum computation
- Lecture 9 (02/15): Quantum computing[ Preliminary notes]
- Reading: Chapter 1.7-1.12 of Mermin's book.
- Reading: Section 2.2 of Nielsen Chuang.
- Lecture 10-11 (02/22-23): Quantum computing (continued)[ Preliminary notes]
- Reading: For a quick overview of the topics read relevant topics in 1.3 of Nielsen Chuang
- Reading: Read relevant topics from 4.1 of Nielsen Chuang (Optional: 4.5.1-4.5.5)
- Lecture 12 (02/27): Formalism and Uncertainty relations[ Lecture notes]
- Reading: 2.2 Nielsen Chuang
- Lecture 13 (03/01): No Cloning and Incompatible Variables [ Lecture notes ]
- Reading: 1.3.5., Box 12-1 Nielsen Chuang
Quantum protocols
- Lecture 14 (03/06): Entanglement and Teleportation[ Preliminary notes, Lecture notes ]
- Reading: 1.3.6., 1.3.7., 2.3 and 2.6 Nielsen Chuang
- Lecture 15 (03/08): Review lecture.
- Lecture 16 (03/13): Midterm exam. [Notes on Quantum non-local effects from the exam]
Quantum Algorithms
Full preliminary notes for quantum algorithms are here.
- Reading: Chapter 2 and 3 or Mermin's book.
- Reading: Read the relevant material from chapter 4.7, 5, 6 of Nielsen Chuang (only what we covered in class is required).
- Lecture 17 (03/15): Deustch-Josza Algorithm. Lecture notes.
- Lecture 18 (03/27): Bernstein-Vazirani and Simon's Algorithms. Lecture notes.
- Lecture 19 (03/29): Quantum Fourier transform Lecture notes.
- Lecture 20 (04/03): Shor's algorithm. Lecture notes.
- Lecture 21 (04/05): Quantum phase estimation.
- Lecture 22 (04/10): Grover's algorithm. Lecture notes.
- Lecture 23 (04/12): Quantum simulation.
- Lecture 24 (04/21): Quantum algorithm for linear systems.
Quantum error correction
- Reading: Nielsen Chuang 10.1-10.2
- Reading: Nielsen Chuang 10.5.1-10.5.4 (Only the parts we covered in class)
- Reading: Chapter 5 of Mermin's book (through 5.5)
- More reading on stabilizer formalism: Link
- Lecture 25 (04/24): Repitition and phase correcting codes.
- Lecture 26 (04/26): Shor's 9-qubit code.
- Lecture 27 (05/01): Stabilizer formalism. Lecture note Lecture note
Useful links
The following are nice introductory notes about quantum computation.
You can use the following references as encyclopeida of complexity classes or quantum algorithms
Rules, Accomodations, & Resources
Attendance rule:
If a student misses or expects to be missing more than three lectures,
they should consult with the instructor. In any situation, please contact the course staff with any concerns.
Covid-19:
If you have flu-like symptoms, please refrain from attending the class. If possible, please let us
know in advance via email. For more information regarding Tufts's resources and policies regarding Covid-19,
please visit Tufts's response to Covid-19.
Religious holy days:
In case a student is observing a religious holy
day and might have to skip a class or miss a deadline, please let us know in advance. We will accommodate such circumstances.
Equal access:
Tufts is committed to providing equal access and support to all qualified students through the provision
of reasonable accommodations. If you have a disability that requires reasonable accommodations,
contact the StAAR Center at StaarCenter@tufts.edu or 617-627-4539. Please be aware that
accommodations cannot be enacted retroactively, making timeliness a critical aspect for their provision.
Tufts's academic integrity statement:
Tufts holds its students strictly accountable for adherence to academic integrity. The consequences of violations can be severe. It is critical that you understand the requirements of ethical behavior and academic work as described in Tufts’
academic integrity handbook. If you ever have a question about the expectations concerning a particular assignment or project in this course, be sure to ask me for clarification. The Faculty of the School of Arts and Sciences and the School of Engineering are required to report suspected cases of academic integrity violations to the Dean of Student Affairs Office. If I suspect that you have cheated or plagiarized in this class, I must report the situation to the dean.
Student Support, including Mental Health:
As a student, there may be times when personal stressors or difficulties
interfere with your academic performance or well-being. The
Dean of Student Affairs Office offers support
and care to undergraduates and graduate students who are experiencing difficulties and can also aid faculty in their work
with students. In addition,
through Tufts’
Counseling and Mental Health Service (CMHS) ,
students can access mental health support 24/7, and they can provide information on additional resources.
CMHS also provides confidential consultation, brief counseling, and urgent care at no cost for all Tufts
undergraduates as well as for graduate students who have paid the student health fee. To make an appointment,
call 617-627-3360. Please visit the CMHS website
to learn more about their services and resources.