Introduction to Quantum Computing
CSE 190 / Math 152 - Spring 2024
| Place and Time: | FAH 1450, TTh 2:00pm-3:20pm |
| Instructor: | Daniel Grier (dgrier@ucsd.edu) |
| TA: | Sihan Liu (sil046@ucsd.edu) |
| Course materials: | Canvas, Gradescope, Piazza |
| Daniel's office hours: | Thursday from 3:30pm-4:30pm in CSE 4218 |
| Sihan's office hours: | Monday from 2:30pm-3:30pm in CSE B260A |
- Homework 1 - due April 9th at 1:30pm
- Homework 2 - due April 16th at 1:30pm
- Homework 3 - due April 23rd at 1:30pm
- Homework 4 - due April 30th at 1:30pm
- Homework 5 - due May 21st at 1:30pm
- Homework 6 - due June 4th at 1:30pm
| Lecture 1 | Introduction to quantum bits and quantum operations | pg 1-5 |
| Lecture 2 | Quantum systems with many qubits and tensor products | pg 1-4 |
| Lecture 3 | Entanglement, tensor products of unitaries, and Dirac notation | pg 3-5 |
| Lecture 4 | Dirac notation, no cloning theorem, and circuits | pg 6-8, pg 55-56 |
| Lecture 5 | Quantum circuits, gate sets, and controlled-operations | pg 2-5 |
| Lecture 6 | Controlled unitaries and partial measurement | pg 4-8 |
| Lecture 7 | Query complexity and Deutsch's algorithm | pg 3-6 |
| Lecture 8 | Deutsch-Jozsa algorithm | pg 3-6 |
| Lecture 9 | Simon's algorithm | pg 1-5 |
| Lecture 10 | Grover's algorithm | pg 1-6, pg 1-5 |
| Lecture 11 | Quantum Fourier Transform | pg 4-6 |
| Lecture 12 | Quantum Fourier Transform continued, phase estimation | pg 1-6, pg 4-6 |
| Lecture 13 | Kitaev phase estimation, reducing factoring to order finding | pg 3-4 |
| Lecture 14 | Shor's algorithm part 1 | pg 2-5 |
| Lecture 15 | Phase Estimation Exercise | notes |
| Lecture 16 | Optional: Introduction to quantum hardware | video, slides |
| Lecture 17 | Shor's algorithm part 2 | pg 1-2 |
This is an advanced undergraduate course focusing on the mathematical theory of quantum computers. The course will start with a general introduction to quantum computers: How do we mathematically specify a quantum state? What kinds of operations can we apply to a quantum state? How can we measure quantum states to solve computational problems? After having developed these basics, we will learn how to construct and analyze quantum algorithms, including those that have generated some of the most excitement about the future of quantum computing.
Textbook: All content will be covered in lectures. There is no official textbook nor will there be a set of canonical lecture notes. That said, most of what will be taught in class is covered in one of the following sources, all of which can be accessed freely online:
- Quantum Computation by John Watrous
- Introduction to Quantum Information Science by Scott Aaronson
- Introduction to Classical and Quantum Computing by Tom Wong
Prerequisites: A previous course in linear algebra is required (Math 18, Math 20F, or Math 31AH). All previous math experience will be very helpful, especially discrete math (Math 15A, CSE 20), probability (Math 11, CSE 21), and complex numbers. No prerequisite knowledge of physics or quantum computation is required.
- Foundations: states, operations, measurements
- Quantum information: entanglement, no-cloning theorem
- Circuits: gates, universality, measures of complexity, programming
- Algorithms: Deutsch-Jozsa, Simon, Grover, quantum Fourier transform
- Complexity: classical simulation, quantum computational advantage
- Homework (30%): There will be 6-7 homework assignments throughout the quarter. The lowest homework grade will be dropped. You are allowed to turn homeworks assignments in 1-day late for a 25% penalty. No other late submissions will be accepted.
- Participation (10%): Participation is based entirely on online quizzes on Gradescope given both synchronously and asynchronously. Your lowest 3 quiz scores will be dropped.
- Midterm (25%): Date - May 2nd in class. There is no make-up midterm.
- Final (35%): Date - June 11th at 3pm during finals week. If final grade is higher than midterm, it will replace the midterm grade.