BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

You must have n qubits or more to win: efficient self-tests for high-dimensional entanglement Natarajan, Anand


How much, and what sort of entanglement is needed to win a non-local game In many ways this is the central question in the study of non-local games, and as we've seen in the previous talks, a full understanding of this question could resolve such conundrums as Tsirelson's problem, the complexity of MIP*, and Connes' embedding conjecture. One approach to this question which has proved fruitful is to design *self-tests*: games for which players who wish to play almost optimally must share a quantum state that is close to a specific entangled state. In this talk I'll present a self-test for high-dimensional maximally entangled states that is *efficient* and *robust*: to test n qubits of entanglement requires a game of poly(n) size, and the test gives guarantees even for strategies that are constant far from optimal. These properties are motivated by the complexity-theoretic goal of showing that the entangled value of a nonlocal game is strictly harder to approximate than the classical value. Based on joint work with Thomas Vidick.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International