Computational aspects of quantum simulation
ENS Lyon - 2026
Announcements
The lecture on Tuesday 22 September 2026 is cancelled.
General information
- Instructors: Omar Fawzi and Samuel Slezak
- Lectures: Tuesdays and Thursdays, beginning Tuesday 8 September 2026
Course overview
This course studies algorithms for predicting the behaviour of quantum systems. We will ask how to simulate dynamics, estimate properties of ground states, and compute or prepare equilibrium states. The emphasis is on both complexity-theoretic limitations and the structural features that make particular instances tractable.
The first part begins with quantum circuits and the class BQP, then develops two classical simulation mechanisms: algebraic structure in Clifford and Pauli methods, and limited entanglement in matrix product states. The second part studies local Hamiltonians, ground-state complexity, quantum preparation algorithms, and semidefinite-programming relaxations. The final part covers classical and quantum Gibbs states, partition functions, Monte Carlo methods, and quantum Gibbs sampling.
Prerequisites
Familiarity with linear algebra and probability will be assumed. Prior exposure to quantum information or complexity theory is useful, but is not required.
Schedule and lecture notes
| Date | Lecture | Topics | Lecture notes |
|---|---|---|---|
| Tue 8 Sep 2026 | 1. Quantum circuits and simulation tasks | Course introduction; pure states and measurements; formal quantum circuits; uniform circuit families; BQP and BPP; state, amplitude, strong, and weak simulation. | Lecture notes |
| Thu 10 Sep 2026 | 2. Simulation algorithms and stabilizer states | Worked examples of strong and weak simulation; expectation-value estimation; state-vector and path-enumeration algorithms; BQP contained in PSPACE; Pauli algebra and stabilizer states. | Lecture notes |
| Tue 15 Sep 2026 | 3. Stabilizer states and Clifford circuits | Signed stabilizer tableaux; Pauli multiplication and group membership; Clifford gates; Pauli measurements; exact efficient simulation of adaptive Clifford circuits via the Gottesman–Knill theorem. | Lecture notes |
| Thu 17 Sep 2026 | 4. Pauli propagation and matrix product states | Backward Pauli propagation; exact expectation values for Clifford + T circuits with few T gates; small output marginals; Schmidt decomposition, Schmidt rank, and optimal truncation across one cut; MPS definition and statement of the bond-dimension/Schmidt-rank theorem (proof in Lecture 5). | Lecture notes |
| Thu 24 Sep 2026 (upcoming) | 5. Matrix product states and exact circuit simulation | Solution of the Lecture 4 exercise; recap of the MPS definition and proof of the bond-dimension/Schmidt-rank theorem; explicit examples; norms, local observables, and sampling; one-site and adjacent two-site gate updates; exact simulation with polynomially bounded intermediate Schmidt ranks. | Available after the lecture. |
Assignments
Each lecture has one exercise that should be solved for the next lecture and a student will be asked to present it then. The statement of the exercise can be found at the end of the corresponding lecture note.
Student projects
Each student will have a 30-minute presentation slot. The tentative
presentation dates are Thursday 5 November, Tuesday 10 November, and
Thursday 12 November 2026. The written report is due two days before the
student's presentation.
Instructions
- Choose one paper and agree on a precise scope with the instructors.
- The presentation should explain the problem, the main ideas and results of the paper, and the student's own analysis, examples, or experiments.
- The report should be self-contained and submitted two days before the presentation slot.
Project ideas
- Sparse Pauli propagation. Rudolph et al., Pauli Propagation. Possible work: reproduce term-growth experiments and compare truncation rules on structured and random circuits.
- Simulation with few non-Clifford gates. Bravyi and Gosset, Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Possible work: explain the decomposition method and benchmark its scaling as the number of non-Clifford gates grows.
- Tensor-network contraction order. Markov and Shi, Simulating Quantum Computation by Contracting Tensor Networks. Possible work: compare contraction heuristics on circuit families with different interaction geometries.
- Entanglement growth and one-dimensional simulation. Vidal, Efficient Classical Simulation of Slightly Entangled Quantum Computations. Possible work: compare entanglement entropy, discarded weight, observable error, and runtime in small numerical examples.
- Complexity of two-qubit Hamiltonians. Cubitt and Montanaro, Complexity Classification of Local Hamiltonian Problems. Possible work: present one branch of the classification and construct explicit examples separating tractable and hard cases.
- Product-state approximations to ground energy. Brandão and Harrow, Product-State Approximations to Quantum Ground States. Possible work: explain one approximation guarantee and compare a small relaxation with exact diagonalization.
- The sign problem. Troyer and Wiese, Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations. Possible work: explain the complexity argument and illustrate cancellations or basis dependence on small Hamiltonians.
- Quantum partition functions. Bravyi et al., Complexity of Quantum Partition Functions. Possible work: map one of the paper's complexity connections and test a small-system approximation against exact diagonalization.
- Detailed balance for quantum Gibbs samplers. Ding, Li, and Lin, Efficient Quantum Gibbs Samplers with Kubo--Martin--Schwinger Detailed Balance Condition. Possible work: compare classical and quantum detailed balance and analyze a one- or two-qubit example.
- The boundary of an efficiently simulable circuit class. Van den Nest, Classical Simulation of Quantum Computation, the Gottesman--Knill Theorem, and Slightly Beyond. Possible work: relax one hypothesis of an efficient simulation result and seek a proof, counterexample, or carefully benchmarked obstruction.