### Spring 2022

## CPSC 447/547: Introduction to Quantum Computing

### ______________________________

#### Time: Mondays and Wednesdays, 11:35am - 12:50pm ET

#### Location: William L. Harkness (WLH) Hall 116

This course will introduce the fundamental concepts in the theory and practice of quantum computation. Topics covered include information processing, quantum programming, quantum compilation, quantum algorithms, and error correction. The objective of the course is to engage students in applying fresh thinking to what computers can do – we establish an understanding of how quantum computers store and process data, and discover how they differ from conventional digital computers. Students should have taken CPSC 201 and CPSC 202 or their equivalents. Basic familiarity with discrete probability and linear algebra is recommended. Prior experience in quantum computing is useful but not required. We anticipate this course will be of interest to students working in computer science, electrical engineering, physics, or mathematics.

### ______________________________

### Logistics

- Instructor: Yongshan Ding. Office Hour: Wednesdays 2-3PM (Zoom). Contact information announced on Canvas.
- Course Assistants: Yue Wu and Ben Foxman. Office Hours: Mondays 7-8PM (in person), Tuesdays 4-5PM (hybrid), and Fridays 1-2PM (Zoom). Contact information announced on Canvas.
- Syllabus (general information): https://www.yongshanding.com/cpsc447-s22
- Canvas (announcements and assignments): https://canvas.yale.edu
- Ed Discussion (Q&A forum): Access through Canvas
- Yale Course Search (registration): Link

### Classes

This course will be an introduction to quantum computing and information. The lectures are divided into several modules with the following tentative topics:

**Module 1.**Introduction to the Principles of Quantum Computation- Quantum Computing – A CS Perspective
- Quantum States: Superposition for Computation
- Quantum Operations and Circuits
- Quantum Entanglement
- Quantum Teleportation
- No-cloning Theorem

**Module 2.**Quantum Logic and Programming- Program Compilation
- Reversible Logic
- Quantum Oracles
**Module 3.**Quantum Algorithms- Deutsch-Jozsa Algorithm
- Simon's Algorithm
- Shor's Factoring Algorithm
- Grover’s Search Algorithm
**Module 4.**Fault-Tolerant Quantum Computation- Quantum Channels
- Quantum Error Correction with 9-Bit Shor Code
- Stabilizer Formalism
- CSS Code
- Topological Error Correction

### Textbooks and Readings

There is no required textbook for this course. Instead, we have a list of recommended textbooks and some course readings (which will be updated and linked from the schedule below). Recommended textbooks and references:

- D&C:
**Quantum Computer Systems**, by Ding and Chong. Free access via Yale VPN [link]. - N&C:
**Quantum Computation and Quantum Information**, by Nielsen and Chuang.

### Course Assignments

The course grade will be based on five assignments (50%), an in-class midterm exam (25%), and a final exam (25%). Assignments are due on Yale Canvas at 5:00PM US Eastern Time unless otherwise indicated on the assignment. You may submit up to two days late, with a 50% penalty. Students in CPSC 547 will conduct a programming-intensive project on selected topics and give presentations in class (an additional 10%).

There will be five assignments, roughly bi-weekly. There will be written and/or programming components within each assignment.

- Assignment 1: Basics of Quantum Computation. Friday of week 3. (10% for CPSC 447, 8% for CPSC 547) · pdf · starter code
- Assignment 2: Advanced Quantum Circuits. Wednesday of week 6. (10% for CPSC 447, 8% for CPSC 547) · pdf · starter code
- Assignment 3: Fun with Quantum Algorithms. Friday of week 10. (10% for CPSC 447, 8% for CPSC 547) · pdf · starter code
- Assignment 4: Basics of Fault Tolerance. Wednesday of week 12. (10% for CPSC 447, 8% for CPSC 547) · pdf · starter code
- Assignment 5: Quantum Error Correction. Wednesday of week 14. (10% for CPSC 447, 8% for CPSC 547) · pdf · starter code

To facilitate cooperative learning, collaboration on the assignments is encouraged. A discussion may take place in a small group (on a whiteboard or on a scratch paper, etc.), but notes or recordings of the discussion are prohibited. All assignments should be written up on one’s own after sufficient time (i.e., at least two hours) has elapsed since any discussion. You must list all your collaborators on every assignment. If you have used external reference materials, please also note this on the assignment. The objective is to demonstrate that you can (re)create a solution on your own. It is prohibited, however, to share solutions or provide hints to other students after you have already arrived at the solution. Take a moment to familiarize yourself with Yale’s Academic Integrity Policy. if you have not done so already. If you have any questions about what does or does not constitute plagiarism, ask! Plagiarism is a serious offense and will not be treated lightly. Fortunately, it is also easy to avoid and if you are careful about giving credit where credit is due you should not run into any problems.

### Exams

There are two exams in this course:

- Midterm Exam: A written midterm exam will be held in class on March 9. (25%)
- Final Exam: A written final exam will be held during the final period on Saturday, May 7 at 2PM ET. (25%)

### Project (547 Students Only)

Students in CPSC 547 will complete a course project. Details have been released on Ed.

### Policies and Wellness

**Covid-19.** According to the university covid-19 guideline, instructors and students are required to properly wear face coverings while in classrooms. As such, we will plan *a 5-min break in each class* to allow everyone to go outside and take off masks, health conditions permitting. All covid-19-related policies are subject to change as we closely monitor the situations in the community. Please refer to information posted on the university website for details of covid-19 related policies.

**In-class Engagement.** This course made several modifications in its teaching and learning practices:

- Selected course materials will be posted on Canvas to allow students to review at their own pace.
- Incremental assessments over time are implemented.
- Hybrid office hours provide the students with flexibility in ways to reach out to the instructor.
- Group discussions are integrated into classes to enhance student interactions.

**Well-being.** The well-being of students is important to us at Yale. We know it has been an especially challenging time for many of us over the past year or two, and the university experience can be overwhelming at times. We all rely on support as we navigate during times of struggle. If you or anyone you know are experiencing any stress, anxiety, or isolation, please consider reaching out to a friend, family member, or faculty you trust. *If you have a personal emergency that might impact your work in the class, please let Yongshan know so that appropriate arrangements can be made.* You may also consider some helpful resources available on campus -- The Good Life Center is the official student wellness center of Yale University and is supported by the Yale Well Initiative.

### Schedule

A tentative course schedule can be found below. Please refresh page frequently for updates. All lectures are in WLH 116 unless otherwise indicated.

### ______________________________

Wednesday, 01/26

Lecture 1 (zoom): **Introduction to QC - a CS perspective** · lecture note

Due: None

Readings: Course syllabus, D&C Ch 1

### ______________________________

Friday, 01/28

Lecture 2 (zoom):**Mathematics toolkit**· lecture note

Due: Course welcome survey on Canvas

Readings: N&C Ch 2.1

### ______________________________

Monday, 01/31

Lecture 3 (zoom):**From bits to qubits**· lecture note

Due: None

Readings: D&C Ch 2.1

### ______________________________

Wednesday, 02/02

Lecture 4 (zoom):**Superposition and entanglement**· lecture note

Due: None

Readings: D&C Ch 2.2.1-2.2.2

### ______________________________

Friday, 02/04

Due: None### ______________________________

Monday, 02/07

Lecture 5:**Quantum gates and circuits**· lecture note

Due: None

Readings: D&C Ch 2.2.4

### ______________________________

Wednesday, 02/09

Lecture 6:**Measurements**· lecture note

Due: None

Readings: D&C Ch 2.2.4

### ______________________________

Friday, 02/11

Due: Assignment 1 at 5:00PM ET on Canvas### ______________________________

Monday, 02/14

Lecture 7:**Quantum teleportation**· lecture note

Due: None

Readings: N&C Ch 1.3.7, D&C Ch 6.3.3

### ______________________________

Wednesday, 02/16

Lecture 8:**Quantum compiling**· lecture note

Due: None

Readings: D&C Ch 6.1-6.3

### ______________________________

Friday, 02/18

Due: None### ______________________________

Monday, 02/21

Lecture 9:**Quantum compiling II**· lecture note

Due: None

Readings: N&C Appendix 3

### ______________________________

Wednesday, 02/23

Lecture 10:**Reversible logic and oracles**· lecture note

Due: None

Readings: D&C Ch 6.4.3 and Ch 3.1

### ______________________________

Friday, 02/25

Due: None### ______________________________

Monday, 02/28

Lecture 11:**Deutsch-Jozsa, Bernstein-Vazirani**· lecture note

Due: None

Readings: D&C Ch 3.2

### ______________________________

Wednesday, 03/02

Lecture 12:**Simon's algorithm**· lecture note

Due: Assignment 2 at 5:00PM ET on Canvas

Readings: N&C Ch 5.4.3

### ______________________________

Friday, 03/04

Due: None### ______________________________

Monday, 03/07

Lecture 13:**Quantum Fourier transform**· lecture note

Due: None

Readings: N&C Ch 5.1

### ______________________________

Wednesday, 03/09

In class: Midterm exam at 11:35AM ETDue: None

Readings: None

### ______________________________

Friday, 03/11

Due: None### ______________________________

Monday, 03/14

Lecture 14:**RSA and Shor's factoring algorithm**· lecture note

Due: None

Readings: N&C Ch 5.3.1-5.3.2

### ______________________________

Wednesday, 03/16

Lecture 15:**Grover's search algorithm**· lecture note

Due: None

Readings: N&C Ch 6.1

### ______________________________

Monday, 03/21

Lecture: No class (Spring recess)Due: None

### ______________________________

Wednesday, 03/23

Lecture: No class (Spring recess)Due: None

Readings: None

### ______________________________

Monday, 03/28

Lecture 16:**Grover's search algorithm II**· lecture note

Due: None

Readings: N&C Ch 6.1

### ______________________________

Wednesday, 03/30

Lecture 17:**Noisy quantum states and density operators**· lecture note

Due: None

Readings: D&C Ch 2.3

### ______________________________

Friday, 04/01

Due: Assignment 3 at 5:00PM ET on Canvas### ______________________________

Monday, 04/04

Lecture 18:**Error channels**· lecture note

Due: None

Readings: N&C Ch 8.3-8.4

### ______________________________

Wednesday, 04/06

Lecture 19:**Basics of quantum error correction (Guest Lecture by Yue Wu)**· lecture note

Due: None

Readings: N&C Ch 10.1-10.3

### ______________________________

Friday, 04/08

Due: NoneActivity: Attend Quantum Week at Yale ❯❯

### ______________________________

Monday, 04/11

Lecture 20:**Basics of quantum error correction II**· lecture note

Due: None

Activity: Attend Quantum Week at Yale ❯❯

Readings: N&C Ch 10.1-10.3

### ______________________________

Wednesday, 04/13

Lecture 21:**Classical error correcting codes**· lecture note

Due: Assignment 4 at 5:00PM ET on Canvas

Activity: Attend Quantum Week at Yale ❯❯

Readings: N&C Ch 10.4

### ______________________________

Friday, 04/15

Due: None### ______________________________

Monday, 04/18

Lecture 22:**Stabilizer formalism**· lecture note

Due: None

Readings: N&C Ch 10.5

### ______________________________

Wednesday, 04/20

Lecture 23:**Stabilizer Codes and Normailizers**· lecture note

Due: None

Readings: None

### ______________________________

Friday, 04/22

Due: None### ______________________________

Monday, 04/25

Lecture 24:**Logical Operations**· lecture note

Due: None

Readings: None

### ______________________________

Wednesday, 04/27

Lecture 25:**Review and Five Qubit Code (Optional)**· lecture note

Due: Assignment 5 at 5:00PM ET on Canvas

Readings: None

### ______________________________

Monday, 05/02

Lecture: No class (Reading period)Due: None

Readings: None

### ______________________________

Wednesday, 05/04

Lecture: No class (Reading period)Due: None

Readings: None

### ______________________________

Saturday, 05/07

In class: Final exam 2:00PM ET