Computational aspects of quantum simulation
ENS Lyon - 2026
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 | 5. Matrix product states and quantum Hamiltonians | Solution of the Lecture 4 exercise; proof of the bond-dimension/Schmidt-rank theorem; exact MPS simulation of low-entanglement circuits; contractions and observables; Hamiltonians, ground energy, locality, and the transverse-field Ising chain. | Lecture notes |
| Tue 29 Sep 2026 | 6. Hamiltonian simulation and the ground-state problem | Solution of the Lecture 5 exercise; three computational tasks for local Hamiltonians; classical constraint satisfaction as a diagonal ground-energy problem; Hamiltonian time evolution; commuting local Hamiltonians; the first-order product formula; and efficient quantum simulation. | Lecture notes |
| Thu 1 Oct 2026 | 7. Variational and convex methods for ground states | Variational upper bounds; product-state and alternating-circuit ansatzes; semidefinite relaxations; Pauli moment matrices; sum-of-squares lower-bound certificates; and an exact two-qubit example. | Lecture notes |
| Thu 15 Oct 2026 | 8. QMA, circuit-to-Hamiltonian constructions, and adiabatic quantum computation | NP and QMA; the local Hamiltonian problem and its containment in QMA; QMA-hardness; history states; and the Feynman-Kitaev circuit-to-Hamiltonian construction. | Lecture notes |
| Tue 20 Oct 2026 | 9. Adiabatic quantum computation | Adiabatic paths and spectral gaps; the adiabatic theorem; ground-state preparation by interpolation; adiabatic simulation of quantum circuits; and the history-state construction. | Lecture notes |
Assignments
An exercise marked as assigned in the lecture notes should be solved for the next lecture, and a student will be asked to present it then.
Student projects
Each student will have a 20-minute presentation slot. The project
presentations will take place during the week of Monday 9 November 2026,
in the usual Tuesday and Thursday lecture slots. No written report is
required. Slides must be sent to the instructors before the lecture in
which the student presents.
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.
- Send the slides to the instructors before the start of the lecture in which you present. No written report is required.
Provisional presentation schedule
Each numbered slot lasts 20 minutes. The slots begin at the usual lecture start time and run in the order shown below. Unassigned slots are reserved for students who have not yet selected a project.
| Date | Slot | Student | Project | Duration |
|---|---|---|---|---|
| Tue 10 Nov 2026 | 1 | Zacharie Dillmann | The boundary of an efficiently simulable circuit class | 20 min |
| 2 | Killian Dugueperoux | Simulation with few non-Clifford gates | 20 min | |
| 3 | Maxence Ponsardin | Pauli propagation | 20 min | |
| 4 | Benjamin Court | Tensor-network contraction order | 20 min | |
| 5 | Bruno Monasson | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem | 20 min | |
| Thu 12 Nov 2026 | 1 | Perig Monfort | The complexity of the local Hamiltonian problem | 20 min |
| 2 | Iannis Morvan | Quantum partition functions | 20 min | |
| 3 | Hugo Segoufin-Chollet | The sign problem | 20 min | |
| 4 | Arthur Djevahirdjian | Stochastic Series Expansion quantum Monte Carlo | 20 min | |
| 5 | Elise Souche | Complexity classification of local Hamiltonian problems | 20 min |
Project ideas
- [Taken by Maxence Ponsardin] Sparse Pauli propagation. Rudolph et al., Pauli Propagation: A Computational Framework for Simulating Quantum Systems. Possible work: reproduce term-growth experiments and compare truncation rules on structured and random circuits.
- [Taken by Killian Dugueperoux] 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.
- [Taken by Benjamin Court] 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.
- [Taken by Elise Souche] 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.
- [Taken by Hugo Segoufin-Chollet] 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.
- [Taken by Iannis Morvan] 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.
- [Taken by Zacharie Dillmann] 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.
- [Taken by Perig Monfort] The complexity of the local Hamiltonian problem. Kempe, Kitaev, and Regev, The Complexity of the Local Hamiltonian Problem. Possible work: explain why the 2-local Hamiltonian problem is QMA-complete and present one of the paper's two proofs at a high level.
- [Taken by Arthur Djevahirdjian] Stochastic Series Expansion quantum Monte Carlo. Melko, Stochastic Series Expansion Quantum Monte Carlo.
- [Taken by Bruno Monasson] The dihedral hidden subgroup problem. Kuperberg, A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. Possible work: introduce the DHSP and explain the main idea leading to Kuperberg's subexponential-time quantum algorithm.