Thomas Vidick 2020

Thomas Vidick, professeur en sciences informatique et mathématique au California Institute of Technology, lauréat 2020 de la Chaire d'excellence de la FSMP, accueilli à l'IRIF, à Inria et au DI-ENS, donnera dans le cadre de sa chaire un cours intitulé Interactive proofs with quantum devices.

Retrouvez ici le blog de Thomas Vidick.

Dates et lieux des séances

Les séances du cours ont lieu le mardi de 10h à 12h à partir du 22 septembre 2020 à l'Institut Henri Poincaré (11 rue Pierre et Marie Curie, 75005 Paris).

Les cours à partir du 10 novembre auront lieu à l'heure prévue mais se feront en ligne. Pour les détails de connexion, veuillez consulter cette page ultérieurement.


Mardi 22 septembre 2020 : Introduction. Testing quantum systems. What is a qubit? (Amphithéâtre Hermite)

Mardi 29 septembre 2020 : Formalizing the setup for testing: Interactive proofs. Operational measures of distance.
 (Salle 314)

Mardi 6 octobre 2020 : Using non-locality for testing: The Magic Square (Amphithéâtre Hermite)

Mardi 13 octobre 2020 : Using computational advantage for testing: A qubit from computational assumptions (Amphithéâtre Hermite)

Mardi 20 octobre 2020 : Overview of approaches to delegated computation (Amphithéâtre Hermite)

Mardi 27 octobre 2020 : The Mahadev delegation protocol (1/2) (Amphithéâtre Hermite)

Mardi 10 novembre 2020 : The Mahadev delegation protocol (2/2) (en ligne)

Mardi 17 novembre 2020 : Overview of complexity of quantum multi-prover interactive proofs (en ligne)

Mardi 24 novembre 2020 : Quantum linearity testing and quantum low-degree testing (en ligne)

Mardi 1er décembre 2020 : Towards MIP* = RE (en ligne) 

Résumé du cours

Interactive proofs with quantum devices


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.

Notes de cours et vidéos

Cours n°1 (22/09/2020) : Introduction. Testing quantum systems. What is a qubit? 
Cliquez ici pour retrouver les notes de cours de cette séance.

Cours n°2 (29/09/2020) : Formalizing the setup for testing: Interactive proofs. Operational measures of distance. 
Cliquez ici pour retrouver les notes de cours de cette séance.

Cours n°3 (06/10/2020) : Using non-locality for testing: The Magic Square 
Cliquez ici pour retrouver les notes de cours de cette séance.

Cours n°4 (13/10/2020) : Using computational advantage for testing: A qubit from computational assumptions
Cliquez ici pour retrouver les notes de cours de cette séance.

Cours n°5 (20/10/2020) :  Overview of approaches to delegated computation
Cliquez ici pour retrouver les notes de cours de cette séance.
Cliquez ici pour obtenir les transparents de cette séance.

Cours n°6 (27/10/2020) :  The Mahadev delegation protocol (1/2)
Cliquez ici pour retrouver les notes de cours de cette séance.