Lecture notes on the Mahadev verification protocol

My street in lockdown

As announced earlier I am currently teaching a course on “interactive proofs with quantum devices” in Paris. The course is proceeding apace, even though the recent lockdown order in France means that we had to abandon our beautiful auditorium at the Institut Henri Poincaré and retreat behind the fanciful Zoom backgrounds whose pretension is a sad reminder of what our summers used to be (Banff, anyone?). A possible upshot is that more may be able to attend the now-online course; if you are interested see the course page for info. (Things are actually fairly good here–in spite of the apparently strict restrictions on daily outings (max 1h, 1km) you can count on the French to bend things their way; most shops are closed but the streets remain quite busy.)

We just finished a sequence of four lectures on the Mahadev “classical verification of quantum computation” protocol. In the process of preparing the lectures I arrived at a presentation of the protocol that is fairly self-contained, so I decided to compile the associated lecture notes as a stand-alone group of 4 lectures that is available here. The notes are aimed at beginning graduate students with a first course in quantum computing and in complexity desiring to gain a concrete understanding of the inner workings of the result; the notes are a bit lengthy but this in part because they take the time to introduce related concepts and slowly build up to the main result. Overall, my hope is that these should be relatively easily readable and provide a good technical introduction to the Mahadev result on classical verification, including an almost complete analysis of her protocol (there are a few explicitly declared shortcuts that help simplify the presentation without hiding any important aspects). For additional background you can also consult the full 10-week notes. Comments on the notes are welcome; I’m afraid they most likely contain numerous typos so if you find any please feel free to correct them directly on the associated overleaf document.

The last three lectures of the course will be devoted to the problem of testing under spatial assumptions, building up to an introduction to the proof of MIP* = RE. If all goes well I’ll aim to prepare some stand-alone notes for that part as well.