Cours FSMP: Interactive proofs with quantum devices

Lectures: Tuesdays 10:00-12:00 AM
Location: Institut Henri Poincaré (Amphitéatre Hermite)
Update: Starting 11/10 class will take place online. Instructor: Thomas Vidick (
FSMP website:

Course description

Quantum mechanics distinguishes itself by such phenomena as superpositions and the uncertainty principle, entanglement, and the no-cloning principle. These uniquely quantum oddities all have “classical signatures” that can be witnessed by the end user and have served to validate the theory from an experimental physics point of view (e.g. a double-slit experiment, or a Bell test).

In recent years computer scientists have built on such experimental setups to go much further than testing specific features of quantum mechanics: they have developed protocols that allow one to (1) test that a black-box device must operate non-classically, (2) certify that it generates intrinsically random bits, (3) verify that it contains a specific quantum state, (4) verify that it implements a desired quantum computation, and more.

The goal for this course is to lay the foundations for an emerging research area of “hybrid classical-quantum protocols” and build towards a concrete understanding of some of the most important results of the past few years. These include Mahadev’s celebrated protocol for classical delegation of quantum computation (arXiv:1804.01082) and the recent complexity-theoretic result MIP* = RE (arXiv:2001.04383). Towards a self-contained presentation of these results we will develop the required foundations in quantum information, complexity theory, and cryptography. Time allowing and depending on the participants’ interests we will present connections with the field of operator algebras.

Lecture notes

Lecture notes for the course are available here. In addition, the latex code is available on Overleaf at this link. Direct corrections of typos can be made by anyone; I welcome comments or questions by email.

Indicative schedule of lectures

  • 22 Sept. Lecture 1: Introduction
    • Testing quantum systems
    • What is a qubit?
    • Video.
  • 29 Sept. Lecture 2: Formalizing the setup for testing
    • Interactive proofs
    • An updated definition for a qubit
    • First test for a qubit
    • A test for quantum memory
    • Video.
  • 06 Oct. Lecture 3: Using non-locality for testing
    • Nonlocal games and strategies
    • Binary linear system games
    • The Magic Square game
    • A nonlocal test for a qubit
    • Video.
  • 13 Oct. Lecture 4: Using computational advantage for testing
    • Simon’s algorithm
    • Claw-free functions
    • A computational test for a qubit
    • Video.
  • 20 Oct. Lecture 5: Overview of approaches to delegated computation
    • Problem statement
    • Overview of approaches
    • The circuit-to-Hamiltonian construction
    • Post-hoc verification: the Fitzsimons-Morimae protocol
    • Video and slides.
  • 27 Oct. Lecture 6: The Mahadev delegation protocol: single-qubit Hamiltonians
    • Construction of trapdoor claw-free function family from LWE
    • Extracting a qubit
    • A protocol for verifying single-qubit Hamiltonians
    • Video.
  • 10 Nov. Lecture 7: The Mahadev delegation protocol: n-qubit Hamiltonians in XX-ZZ form
    • This lecture will take place on Zoom: link.
    • The general verification protocol
    • Extracting n qubits
    • Copmleteness and soundness
    • Construction of function family
    • Scribe notes. Video.
  • 17 Nov. Lecture 8: Multiprover interactive proof systems
    • Multiprover interactive proof systems with provers sharing entanglement
    • MIP* = RE
    • Consequences: Tsirelson’s problem and CEP
    • Scribe notes. Video.
  • 24 Nov. Lecture 9: Compression of nonlocal games
    • The Halting problem
    • The comptession procedure
    • High-level proof sketch of MIP* = RE
    • An n-qubit test
    • Scribe notes. Video.
  • 1 Dec. Lecture 10: Quantum linearity testing
    • Definining n approximate qubits
    • Approximate group representations
    • Testing n qubits
    • Scribe notes. Video.


The two main papers that we aim to discuss in the course are

  • Classical verification of quantum computations, by Mahadev. I wrote a high-level technical overview of the paper addressed at a mathematical audience in the Bulletin of the AMS here. For more popular accounts, there is a very good Quanta article on the paper as well as an IQIM blog post.

  • MIP*=RE, by Ji, Natarajan, Vidick, Wright and Yuen. See the excellent IQIM blog post written by Yuen, as well as an article I wrote for the Notices of the AMS that motivates the problem by explaining its connection to Tsirelson’s problem.

  • On the general topic of delegation of quantum computation, I recommend the survey by Gheorghiu, Kapourniotis and Kashefi. The survey was published right as Mahadev’s result appeared, so it only mentions it briefly; however, it gives a detailed overview of most other approaches to delegation and provices a great introduction to the topic.

  • On the topic of nonlocal games and self-testing, see the lecture notes by Richard Cleve for a recent course on the topic.