Quantum computation is an exciting area that at the intersection of computer science, mathematics and physics. It touches on fundamental questions in computer science as well as quantum physics. This course will provide a comprehensive introduction to this area including:
1. An introduction to quantum physics from a quantum information viewpoint.
2. Quantum algorithms for factoring, discrete log and search.
3. Limits on the power of quantum computers.
3. Quantum error-correcting codes and fault-tolerant quantum computation.
4. Quantum information and cryptography.
5. Survey of proposals for implementation of quantum computers.
Prior coursework in quantum mechanics is not essential. This interdisciplinary subject draws on techniques from theoretical computer science, mathematics, and quantum physics. Students with a strong background in any one of these areas are welcome to attend.
A list of papers for projects is now available at project-list
There will be no lecture on Tuesday 9/21 and Thursday 9/23. Please use the opportunity to digest the concepts already introduced and to work on the new assignment. I will announce makeup lectures later in the semester.
| Topic | Notes (modified) | ||||
| 1 | 8/31 | Intro, Qubits, Measurements, Bell Inequalities. | [pdf,ps] (9/5) | ||
| 2 | 9/2 | Two qubit states, Unitary Evolution, Quantum gates, Superdense coding | [ps] (9/13) | ||
| 3 | 9/7 | Hilbert Spaces, Tensor Products, No Cloning Theorem, Teleportation (preliminary version) | [ps] (9/8) | ||
| 4 | 9/9 | Universal Gate Sets, Solovay-Kitaev theorem, BQP, Reversible Computation. | [pdf,ps] (9/20) | ||
| 5 | 9/14 | Reversible computation, BPP in BQP, accuracy. | [pdf,ps] (10/5) | ||
| 6 | 9/16 | BQP in PSPACE, #P, Deutsch-Jozsa, Bernstein-Vazirani. | [scan1, [scan2, scan3, [scan4] (9/24) | ||
| 7 | 9/28 | Simon's Algorithm | [pdf,ps] (10/2) | ||
| 8 | 9/30 | Quantum Fourier Transform | [pdf,ps] (10/15) | ||
| 9 | 10/5 | Shor's Factoring Algorithm | [pdf,ps] (10/15) | ||
| 10 | 10/7 | NP-complete problems - quantum lower bounds + Grover's algorithm. | [pdf,ps] (10/7) | ||
| 11 | 10/12 | Grover contd. + Quantum zeno effect + Vaidman Bomb. | [pdf,ps] (10/15) | ||
| 12 | 10/14 | Hidden Subgroup Problem + discrete log. | [pdf,ps] (10/17) |
||
| 13&14 | 10/19 and 10/21 | Quantum Walks, Hitting Time, Element Distinctness | [pdf,ps] (10/30) | ||
| 15 | 10/26 | Hamiltonians, Schrodinger's Equation, Uncertainty Relations. | [pdf,ps] (11/7) | ||
| 16 | 10/28 | Dirac Equation, Entropic Uncertainty Relation. |
[pdf,ps] (11/12) |
||
| 17-19 | 11/2, 11/4, 11/9 | Quantum simulation, Quantum NP. |
[pdf,ps] (11/15) |
||
| 20 |
11/16 | Density Matrices, trace norm, von Neumann entropy. | [pdf,ps] (11/20) |
|
21 |
11/18 and 11/23 | Quantum Error-correcting codes. | [pdf,ps] (11/20) |
|
On quantum computation
Mathematical background
On quantum mechanics in general