Séminaire Bourbaki du vendredi

Omar Fawzi — The computational complexity of (quantum) two-prover games

Europe/Paris
Darboux (IHP)

Darboux

IHP

Description

I will present the simple concept of two-prover games which has been extremely fruitful in complexity theory and in quantum information. In complexity theory, one way of stating the famous PCP theorem is that computing the optimal winning probability of two-prover games, even approximately, is hard. In quantum information, Bell’s celebrated theorem can be phrased as a two-prover game for which there is a quantum strategy achieving a winning probability that is strictly larger than any classical strategy. I will try to present these two points of view.