CMPT 476: Introduction to Quantum Algorithms


Quantum computing is a computational paradigm which utilizes quantum mechanical effects at the physical level to process information. By using these quantum effects we can solve certain problems faster than the best known classical methods, such as factorizing integers, simulating quantum mechanical systems, and solving some linear systems. Since the advent of such algorithms in the 90's, researchers in computing science, mathematics, physics, chemistry, engineering, and other fields have been attempting to not only build quantum computers but also to understand their power.

This course offers an introductory treatment to the field of quantum information and computation with an emphasis on algorithms. We will examine how these quantum algorithms work, as well as their implications on computational complexity and issues and techniques relating to their physical realization.

Final exam details

Practice problem sets

By popular request I've compiled a list of publicly available problem sets from other instructor's courses. Note that I haven't gone through all the problem sets myself so they may be more or less relevant --- the list is largely predicated on the assumption that undergraduate introductory quantum computing courses cover generally similar material to this one.

Midterm details

Updates

Course information

Instructor:   Matt Amy
Email:   matt_amy at sfu.ca
Office:   TASC1 9215
TAs:   Lucas Stinchcombe (lss6 at sfu.ca)
Ming Yin (mya124 sfu.ca)
Classes:   MoWeFr 10:30-11:20 (AQ 3159)
Office hours:   M 11:30-12:30 - Lucas (CSIL labs, ASB 9816)
Th 1:30-2:30 - Ming (CSIL labs, ASB 9816)
WeFr 11:20-12:30 - Matt (outside of classroom or TASC1 9215)
Textbook:   None (see additional resources below)
Discussion forum:   https://piazza.com/sfu.ca/spring2024/cmpt476

Tentative schedule

Date Topic(s) Materials Additional references
Jan. 8 Introduction to course & QC Lecture 1 KLM §1.1, §1.2, §1.6
Jan. 10 The circuit model of computation Lecture 2 KLM §1.3, §1.4
Jan. 12 Qubits & basic measurement Lecture 3 KLM §2.1, §2.2, §3.1, §3.4
Jan. 15 Operators and state evolution Lecture 4 KLM §2.3, §3.2
Jan. 17 Cancelled - snow day!
Jan. 19 Operators cont. Lecture 4 cont.
Jan. 22 Fun and games with a single qubit Lecture 5 Recorded lecture
Jan. 24 Composite systems Lecture 6 KLM §2.6, §3.3
Jan. 26 Partial measurements and Spooky Action at a Distance Lecture 7 KLM §3.4
Jan. 29 Non-local games and Bell's inequality Lecture 8
Jan. 31 Projective measurements Lecture 9 KLM §3.4 cont., §3.5
Feb. 2 Mixed states and Density matrices Lecture 9 cont. KLM §3.5 cont.
Feb. 5 Reduced density matrices and No Communication Lecture 9 cont. KLM §3.5 cont.
Feb. 7 Superdense coding and Bell basis measurements Lecture 11 KLM §5.1
Feb. 9 Quantum teleportation and the No-Cloning theorem Lecture 12 KLM §5.2
Feb. 12 Quantum computation and complexity theory Lecture 13 KLM §4.1
Feb. 14 Gate sets and quantum universality Lecture 14 KLM §2.4,§2.5,§4.2,§4.3,§4.4
Feb. 16 Gate sets and quantum universality cont. Lecture 14 cont.
Feb. 19-23 No class - reading week
Feb. 26 Reversible computation Lecture 15 KLM §1.5
Feb. 28 Midterm review
Mar. 1 Introduction to Quantum Algorithms Lecture 16 KLM §6.1,§6.2
Mar. 4 Early black-box algorithms Lecture 17 KLM §6.3,§6.4
Mar. 6 Simon's algorithm Lecture 18 KLM §6.5
Mar. 8 Simon's algorithm cont. Lecture 18 KLM §6.5
Mar. 11 Integer Factorization Lecture 19 KLM §7.3.1,§7.3.2, Group theory appendix
Mar. 13 The Quantum Fourier Transform Lecture 20 KLM §7.1
Mar. 15 Shor's period finding algorithm Lecture 21 KLM §7.3.4,§7.3.5
Mar. 18 Shor's period finding algorithm cont. Lecture 21 cont. KLM §7.3.4,§7.3.5
Mar. 20 Discrete logarithms and the Hidden Subgroup Problem (HSP) Lecture 22 KLM §7.4,§7.5
Mar. 22 Eigenvalue Estimation Lecture 23 KLM §7.2
Mar. 25 Hamiltonians and the Ground State Energy problem Lecture 23-Lecture 24
Mar. 27 Digital Hamiltonian simulation Lecture 24
Mar. 29 No class - Good friday
Apr. 1 No class - Easter monday
Apr. 3 Grover's Search Algorithm Lecture 25 KLM §8.1
Apr. 5 Applications of Grover's algorithm Lecture 26 KLM §8.2, §8.3, §8.4
Apr. 8 Error correction Lecture 27 KLM §10.1, §10.2, §10.3
Apr. 10 Quantum error correcting codes Lecture 28 KLM §10.4, §10.5
Apr. 12 Fault tolerance Silicon Quantum Technologies lab tour Lecture 29 KLM §10.6

Topics

Prerequisites

As quantum computing is an interdiscplinary field involving computer science, mathematics, and physics, the only formal requirements are satisfactory performance in linear algebra, which the course will rely upon heavily. Experience with topics such as algorithms, complexity, abstract algebra, and quantum mechanics will all be assets, but are not required. It is expected that students will encounter some topics with which they have very little familiarity.

Course goals

By the end of this course, students should understand the basic model of quantum information and computation, key quantum protocols and algorithms, and leave with a broad knowledge of how such algorithms are implemented and what the primary challenges in doing so are, from their high-level mathematical expression down to the physical realization.

Evaluation

Tentative dates

Additional resources

We will mostly be following Kaye, Laflamme, and Mosca's An Introduction to Quantum Computing (KLM), but it is not required. Mermin's Quantum Computer Science is of a very similar flavour and freely available in the form of lecture notes here.

Other great resources: