Modern quantum algorithms

This course gives a modern introduction to quantum algorithms, with an emphasis on far-term quantum algorithms, rigorous proofs and complexity-theoretic perspectives.

We begin with the basic language of quantum computation: quantum circuits, universal gate sets, and classically simulable families such as Clifford circuits. We then develop the central primitives used in designing quantum algorithms, including search, phase estimation and amplitude amplification. We will conclude this part of the course by presenting the unifying framework of the quantum singular value transform.

The second part of the course is on algebraic perspectives. Here we will cover the quantum Fourier transform, period-finding, hidden subgroup problems, and Shor's algorithm.

If time permits, we will introduce coding theory and the role of decoding in modern quantum algorithm design, including Regev's reduction and Decoded Quantum Interferometry.

The course concludes with a project to develop new quantum algorithms. These new algorithms will be presented in an "Algorithmic Fight," a format inspired by the International Young Physicists' Tournament. Here, teams of students will present and defend their solutions to the project while an opposing team critiques their ideas, challenging them on mathematical rigor, feasibility of input assumptions and how well their solution generalizes. Grades will be determined based on technical novelty of solutions, as well as quality of presentation and critique of opposing teams.