General information

• Instructors: Omar Fawzi and Samuel Slezak

Topics covered

This course will focus on algorithms for the simulation of quantum systems. The main questions we plan to focus on are: simulating the dynamics of a model (e.g., a quantum circuit) and computing properties of equilibrium states of a model. We plan to cover both the complexity-theoretic aspects as well as algorithms.

We will start with simulating dynamics and introduce the complexity class BQP capturing the worst-case complexity of the problem. We will then cover special classes of circuits (e.g., Clifford circuits or producing limited entanglement) for which time dynamics can be classically simulated.

In the second part, we will study the ground state (i.e., zero temperature) properties of a quantum system described by a Hamiltonian. The complexity theory aspects of this question goes by the name Hamiltonian complexity and it is captured by the class QMA. We will also cover general algorithms for this problem namely based on semidefinite programming relaxations.

In the third part, we will cover the complexity of Gibbs states (i.e., equilibrium states at non-zero temperature) and partition functions of quantum systems. We first study the complexity of computing partition functions and see how it is related to a "counting" generalization of the class QMA. Finally, we study the preparation of quantum Gibbs states, paying special attention to the quantum Gibbs sampling algorithms that generalize Markov chain Monte Carlo.

Prerequisites:

• Familiarity with linear algebra and probability will be assumed. Prior exposure to quantum information or complexity theory is a plus, but is not assumed.

Grading

• Two assignments
• A small project which may take different forms such as writing a report about an article or implementing and comparing several algorithm