Quantum Information and Computation
CSE 534* | Autumn 2024
Course Information
Instructor: Chinmay Nirkhe
Teaching Assistants: TBD
Location: TBD
Times: TBD
Course Description
Introduction to quantum information and computation. Qubits, quantum gates, and measurements. Entanglement and non-locality. Density matrix formalism. Quantum algorithms: Simon's algorithm, Grover search, Shor's factoring, and Hamiltonian Simulation. Quantum error-correction. Recommended: either solid background in mathematics and/or theoretical computer science, or prior familiarity with quantum-computing fundamentals.
Prerequisites
The course material will be accessible to both computer scientists and physicists, provided they have a strong mathematical background. No explicit prerequisites are set for this course. We will review what is necessary but students with weaker math backgrounds may need to review material outside the course as necessary.
My expectation is that students have strong mathematical background in linear algebra (such as MATH 318, 340, or equiv.). They should have taken and done well in such courses. In terms of computer science prerequisites, exposure to the theory of computation (such as CSE 431, 531, or equiv.) and theory of algorithms (such as CSE 417, CSE 521-22, 525, or equiv.) is useful as we will be extending the results from classical computation to quantum computation. No physics knowledge is necessary but it doesn't hurt to have taken a previous course on quantum mechanics (such as PHYS 225, 324, or equiv.). It is also helpful (but not necessary) to have taken group theory (such as MATH 402-04, 411-12, or equiv.), and analysis (such as MATH 327, 424-28 or equiv.).
Undergraduate students or graduate students of non-traditional backgrounds for this course are encouraged to contact me to see if this course is right for them.
Literature
There are no explicit textbooks for this course but the following is a pretty good library to have around. I will link related readings from these books or online lecture notes as appropriate:
- Nielsen and Chuang. Quantum Computation and Quantum Information.
- Kitaev, Shen, and Vyalyi. Classical and Quantum Computation.
- Wong. Introduction to Classical and Quantum Computing.
The following are topics textbooks that might be helpful.
- Watrous. The Theory of Quantum Information.
- Arora and Barak. Computational Complexity: A Modern Approach.
- Vidick and Wehner. Introduction to Quantum Cryptography.
Course Schedule/Topics
- Introduction, Mathematical fundamentals
- Randomness, Density Operators
- Measurements, Chanels, Deutch-Josza game, Elitzur-Vaidman tester
- Bell inequalities, CHSH game
- Superdense coding, quantum teleportation
- Quantum circuits, complexity theory
- Grover's algorithm for search
- Simon's problem, black-box model
- Period finding
- Shor's factoring algorithm
- Shor's factoring algorithm
- Quantum simulation, cannonical problems
- Complexity theory, QMA
- Complexity theory, QMA
- Error-correction
- Error-correction
- Quantum PCP conjecture
Grading
Grades in this course are based on intermittent problem sets, a final, and a literature review/research project to be conducted in the final weeks of the course. Exact ratios will be set closer to the start of the term.
*. This course was previously known as CSE 599Q.↩