Subject |
A computer is a physical device that helps us process information by executing algorithms. An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information- processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the relationship between computing and physics. Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum in- formation processing are known as quantum computers. In this class we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur.. |
Prerequisites |
Mathematical maturity; APPM 2360, APPM 3310, CSCI 2820,MATH 2130, MATH 2135, or something else covering linear algebra. If you have not taken those classes but believe that your background is close to being sufficient, please make sure you have filled up any potential gaps by the end of the second week of classes. If you are not sure whether your background suffices, please see the instructor. The course is designed for ungraduate students but may be suitable for some graduate students. |
Instructors |
Alexandra Kolla (alexandra.kolla [at] colorado [dot] edu) 122 ECES [AK] Graeme Smith (Graeme.Smith@Colorado.edu)JILA S326 [GS]
|
Graders |
Computer Science: Steven Kordonowy (Steven.Kordonowy@colorado.edu) Physics: Ariel Shlosberg (Ariel.Shlosberg@Colorado.EDU) Matteo Wilczak(matteo.wilczak@colorado.edu)
|
Times |
MWF 2:00PM - 2:50PM |DUAN G130 |
Office Hours |
Alexandra Kolla/ Graeme Smith: Friday 3:00-4:00 pm, JILA X317. Ariel Shlosberg: Tu/Th 2:00-4:00pm, DUANG2B90 (physics help room) Steven Kordonowy: Th 11am-12pm, ECAE 124. Matteo Wilczak: Wednesday, 1-2pm, DUANG2B90 (physics help room) |
| # | Date | Topic | Lecture Slides | Reading Material |
|---|---|---|---|---|
| 1 | M January 13 | Introduction to Quantum Computing | Slides | Chapter 1 of textbook |
| 2 | W January 15 | Introduction to Quantum Computing, Part II | Slides | Chapter 1 of textbook |
| 3 | F January 17 | Introduction to Quantum Computing, Part III | Slides | Chapter 1 of textbook |
| 4 | W January 22 | The General Computational Process. | Slides | Chapter 2.1 of textbook |
| 5 | F January 24 | Deutsch's Problem. | Slides | Chapter 2.2 of textbook |
| 6 | M January 27 | Linear Algebra refresher. | Slides | Appendix A of textbook |
| 7 | W January 29 | Linear Algebra refresher. | Slides | Appendix A of textbook |
| 8 | F January 31 | Deutsche's Problem, revisited. | Slides | Chapter 2.2 of textbook |
| 9 | M February 3 | Bernstein Vazirani. | Slides | Chapter 2.4 of textbook |
| 10 | W February 5 | Bernstein Vazirani continued, set-up of Simon's Problem. | Slides | Chapters 2.4, 2.5 of textbook |
| 11 | F February 7 | Simon's Problem. | Slides | Chapters 2.5 of textbook |
| 12 | M February 10 | Simon's Problem. | Slides | Chapters 2.5 of textbook |
| 13 | W February 12 | Midterm 1. | ||
| 14 | F February 14 | Quantum Cryptography, BB84. | Slides | Chapters 6.1,6.2 of textbook |
| 15 | M February 17 | Quantum Cryptography, BB84 continued. | Slides | Chapters 6.1,6.2 of textbook |
| 16 | W February 19 | Quantum Cryptography, BB84 continued. | Slides | Chapters 6.1,6.2 of textbook |
| 17 | F February 21 | Quantum Cryptography, Dense Coding. | Slides | Chapters 6.1,6.2,6.4 of textbook |
| 18 | M February 24 | Dense Coding. | Slides | Chapter 6.4 of textbook |
| 19 | W February 26 | Teleportation. | Slides | Chapter 6.5 of textbook |
| 20 | F February 28 | GHZ Puzzle. | Slides | Chapter 6.6 of textbook |
| 21 | M March 2 | Period Finding, Shor's Algorithm. | Slides | Chapter 3.4 of textbook |
| 22 | W March 4 | Period Finding, Shor's Algorithm. | Slides | Chapter 3.4-3.7 of textbook |
| 23 | F March 6 | Period Finding, Shor's Algorithm. | Slides | Chapter 3.4-3.7 of textbook |
| 24 | M March 9 | Period Finding, Shor's Algorithm. | Slides | Chapter 3.4-3.7 of textbook |
| 25 | W March 1 | Period Finding, Shor's Algorithm, Cryptography introduction. | Slides | Chapter 3.4-3.7 of textbook |
| 26 | F March 13 | NO CLASS-READING MATERIAL ON MODULAR ARITHMETIC. | Chapter 3.4-3.7 of textbook | |
| 27 | M March 30 | Grover's Search. | Slides, Video | Chapter 4.1 of textbook |
| 28 | F April 3 | Grover's Search, contd. | Slides, Video | Chapter 4 of textbook |
| 29 | M April 6 | Grover's Search with reflections. | Slides, Video | Chapter 4 of textbook |
| 30 | W April 8 | Grover's Search Optimality. | Slides, Video | Chapter 4 of textbook |
| 31 | F April 10 | Grover's Search Optimality, Quantum Complexity. | Slides, Video | Chapter 4 of textbook |
| 33 | M April 13 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 34 | W April 15 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 35 | F April 17 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 36 | M April 20 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 37 | W April 22 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 38 | F April 24 | Quantum Information Theory, Error Correcting Codes. | Slides, Video | Chapter 5 of textbook |
| 39 | M April 27 | Classical and Quantum Complexity, Hamiltonians. | Slides, Video |
| Homework # | Due | Homework Solutions |
|---|---|---|
| HW0 | January 20 | Solutions |
| HW1 | January 27 | Solutions |
| HW2 | February 3 | Solutions |
| HW3 | February 10 | Solutions |
| Solutions | ||
| HW4 | February 24 | Solutions |
| HW5 | March 2 | Solutions |
| Practice Problems for Midterm 2 | Solutions | |
| Solutions | ||
| Homework |
|---|
| There will be weekly homework, including Homework 0. |
| They have to be turned in individually by each student . |
|
Please do not forget to cite your sources (you will get a zero if you use material from elsewhere and do not cite the source!) ***Absolutely no late homework accepted***. Instead, the lowest two homework grades will be dropped. |
| Exams |
|---|
| There will be two midterms and a Final exam. More details to come. |
| Grading |
|---|
| 30% homeworks, 20% each midterm, and 30% final exam. Extra 2% points may be given for class participation at various occasions. |
|
|
|
Chapter 1: " Classical and Quantum Bits and Circuits " (1 week) |
- We will start with "basic" material about quantum bits, unitary matrices, quantum gates and circuits, and quantum computation. |
|
Chapter 2: " Simple Quantum Algorithms" (1 week)
|
- We will cover Simon's, Bernstein-Vazirani, and Deutsch's algorithms. |
|
Chapter 6: "Few-qubit Protocols" (about 2 weeks)
|
- We will cover teleportation, dense coding, quantum cryptography. |
|
Chapter 4 : "Quantum Search" (1 week)
|
- We will cover Grover's algorithm. |
|
Chapter 3 : "Quantum Factoring" (1-2 weeks)
|
- We will cover quantum factoring. |
|
Chapter 5 : "Quantum Error Correction" (remaining time)
|
- We will cover quantum information theory and error correcting codes. |