CSCI5370 Quantum Computing (Spring 2025)

Course Instructor:

Prof. Xiao LIANG (xiaoliang [at] cse.cuhk.edu.hk)

Time and Location: We meet every Tuesday in two sessions:

09:30AM - 10:15AM at Lee Shau Kee Building LT2
10:30AM - 12:15PM at Lee Shau Kee Building 302

Teaching Assistant:

Mr. LUO, Robin Bin (bluo23 [at] cse.cuhk.edu.hk)
TA Office Hour: Tue 2:30 - 3:30 pm, Room 120, Ho Sin Hang Engineering Building

Weekly Schedule

Class Days (dd/mm): 07/01, 14/01, 21/01, 04/02, 11/02, 18/02, 25/02, 04/03, 11/03, 18/03, 25/03, 01/04, 08/04, 15/04

Week	Date	Topics	Slides
1	07/01/2025	Course overview and logistics, general computing devices and physics, single-qubit systems, a simplified version of "The Four Postulates" of Quantum Mechanics.	week-01
2	14/01/2025	Exemplary orthogonal matrices, true random number generators, Elitzur-Vaidman bomb, BB84 QKD protocol, the necessity of complex numbers in quantum mechanics. Supplementary reading: Chapters 4.4 and 8.2 of Prof. Aaronson's lecture notes. Alessio Avella's article	week-02
3	21/01/2025	Abstract algebra approach to vector space, sets (Russell's paradox, countability), magma, semigroup, monoid, group (commutativity), ring (polynomials), fields, modules, vector space, linear operators, eigenvalue decomposition.	week-03
4	28/01/2025	--- Course canceled due to Lunar New Year holidays ---	N.A.
5	04/02/2025	Metric space, normed space, inner-product space, Cauchy-Schwarz, Hilbert space, linear algebra in Dirac notation, Postulate 1 (full-fledged), adjoint operators, spectral theorem, normal operators and examples (unitaries, Hermitians, projectors, positive and positive definite oprators)	week-05
6	11/02/2025	Postulate 2 (full-fledged), unitary nature of Shrödinger's solution, functions of normal operators, example unitaries, Postulate 3 (full-fledged), projective measurements, generality of projective measurements, Hamiltonians and observables, expected value of quantum properties, POVM Supplementary reading: Section 2.2.2, 2.2.3, 2.2.5, 2.2.6 of Nielsen-Chuang. Chapter 12 of Prof. Aaronson's lecture notes.	week-06
7	18/02/2025	Global phase vs relative phase, Kronecker product, tensor product space from Kronecker product, Postulate 4 (full-fledged), linear operators over tensor product space, no-cloning theorem Supplementary reading: Section 2.2.7, 2.2.8 of Nielsen-Chuang. Chapter 12 of Prof. Aaronson's lecture notes.	week-07
8	25/02/2025	Quantum Teleportation, measure of information, modelling of noisy channels, Holevo's theorem, super-dense coding, EPR paradox, hidden variables and the "incompleteness" of quantum mechanics Supplementary reading: Lecture 9.1, 10.1, and 13 of Prof. Aaronson's lecture notes. Section 2.6 of Nielsen-Chuang (only the philosophical discussion). The first section of Prof. John Watrous' lecture.	week-08
9	04/03/2025	CHSH game, introduction to density operators, complete characterization of density operators Supplementary reading: Lecture 13 and 14.1 of Prof. Aaronson's lecture notes. Section 2.4.1 and 2.4.2 of Nielsen-Chuang. Also, Section 2.6 of Nielsen-Chuang discusses the EPR paradox using tools that, compared to those presented in our lecture, seem unnecessarily complex. You are encouraged to read that section, though it is not mandatory.	week-09
10	11/03/2025	The four postulates in density-operator formalism, mixed states vs pure states, entangled states vs mixed states, criterion for pure states, "global phase" explained in density-operator formalism, reduced density operator, partial trace, partial views in EPR game. Supplementary reading: Section 2.4 of Nielsen-Chuang. Lecture 6 of Prof. Aaronson's lecture notes.	week-10
11	18/03/2025	Classical circuits, quantum circuit model, QC as a superset of classical computing, Toffoli gate, reversible computing, standard oracle and phase oracle, the "1+2" universal set theorem, Solovay-Kitaev theorem. Supplementary reading: Section 3.1.2, 3.2.1, 3.2.2 of Nielsen-Chuang. Lecture 17.1, 17.2 of Prof. Aaronson's lecture notes.	week-11
12	25/03/2025	Solovay-Kitaev continued, Deutsch Algorithm, Binary Quantum Fourier Transform, Deutsch-Josza Algorithm Supplementary reading: Lecture 17.3, 17.4 of Prof. Aaronson's lecture notes.	week-12
13	01/04/2025	--- Midterm Exam ---	N.A.

The weekly teaching schedule will be released progressively as the course unfolds...

Meta Information

Target Audience:

This course is primarily designed for postgraduate students. However, senior undergraduates are also welcome. Please note that undergraduate students must obtain formal approval to enroll in postgraduate courses at CUHK. If you're an undergraduate interested in joining, ensure you complete this approval process. If you encounter any difficulties during the process, don't hesitate to reach out to the course instructor, who will be happy to assist.

Prerequisites:

Ideally, this course requires the completion of its undergraduate counterpart, CSCI3350 Introduction to Quantum Computing. However, CSCI3350 was suspended for a few years and only recently reactivated (with availability likely starting next semester at the earliest). Thus, this time, the instructor is more open to considering exceptions for interested students who have not taken an undergraduate Quantum Computing course. If you encounter any enrollment issues due to this prerequisite, please feel free to contact the course instructor for assistance.

Please note, however, that undergraduate-level knowledge of linear algebra and probability theory is required and cannot be waived.

Course Description

This course serves as an advanced follow-up to its undergraduate counterpart, CSCI3350 Introduction to Quantum Computing. It offers an in-depth exploration of quantum computing, with a particular focus on areas at the forefront of both academic research and (ongoing but promising) industrial implementations.

The course is structured into two parts:

First Half: This portion focuses on the foundational concepts and algorithms of quantum computing, with an emphasis on depth. This contrasts with CSCI3350, which prioritizes breadth over depth in the topics covered.
Second Half: The latter part of the course explores several interdisciplinary areas where quantum computing intersects with fields such as computational complexity, cryptography, machine learning, networking, information theory, and more.

This approach aims to equip students with a comprehensive range of quantum-related skills, preparing them to contribute to the rapidly evolving field of quantum computing, which presents abundant opportunities in both industry and academia.

Tentative topics include:

(Quick review) Basics of quantum information, the quantum circuit model
(Quick review) Basic quantum protocols, such as quantum teleportation, superdense coding, and more
(Quick review) Basic quantum algorithms, such as Simon's algorithm, Shor's factoring algorithm, and Grover's search
(In-depth) Quantum Fourier Transform, phase estimation, and amplitude amplification
(In-depth) The linear-algebraic formalism of quantum computing
(In-depth) Entanglement, non-local games
(In-depth) Quantum error correction and fault tolerance
(In-depth) Selective topics from quantum cryptography, proofs of quantumness, quantum information theory, quantum complexity theory, quantum machine learning, and quantum networks

The final topics covered will depend on student feedback, their ability to grasp the material, and the time available.

Course Learning Outcomes

By the end of the course, students will:

Build a solid foundation in quantum computing, developing essential conceptual frameworks and technical skills in the field.
Gain the ability to understand and discuss cutting-edge research papers in quantum computing, effectively communicating complex ideas with collaborators and peers. Be prepared to contribute to ongoing research and development within the field.
Acquire interdisciplinary knowledge of how quantum computing interacts with other areas, including computational complexity, cryptography, machine learning, networking, and information theory. Be able to identify and appreciate the intersections between quantum computing and their own research areas, and pursue interdisciplinary research opportunities.

Existing Similar Courses

There are currently four courses at CUHK similar to this one:

CSCI3350 Introduction to Quantum Computing
IERG5380 Quantum Information Processing
IERG6130 Advanced Topics in Information Engineering II: PSD Matrices and Quantum IT
MAEG5110 Quantum Control & Quantum Information

To help students avoid confusion and make informed decisions when planning their study scheme, I include a comparison between this course and the similar offerings:

Compared to the undergraduate course CSCI3350, this course (1) covers several advanced topics not included in CSCI3350, and (2) for overlapping topics, explores them from a new perspective, typically with greater depth and a more powerful mathematical formalism.
Courses such as IERG5380, IERG6130, and MAEG5110 place a stronger emphasis on the information-theoretic aspects of quantum computing. In contrast, this course focuses on the algorithmic side of quantum computing. While we will touch on topics central to quantum information theory—such as various notions of quantum entropy, quantum channel characterizations, entanglement distillation, and the capacity of quantum channels—we will only cover them to the extent necessary to support the main topics listed in the course description. The primary focus will be on subjects with a theoretical computer science flavor, which are at the forefront of current research, offering numerous open questions and opportunities that are likely to excite computer science students.