In complexity theory and cryptography, parallel repetition is a natural operation to reduce the error of a game or protocol without increasing the number of rounds. Raz's parallel repetition theorem is a cornerstone result in complexity theory showing that the value of two-player one round game, when repeated in parallel, decreases exponentially fast with the number of repetitions. Although the statement is intuitive, its analysis requires sophisticated techniques in information theory.
A major open question in quantum complexity theory concerns whether an analogue of Raz's theorem holds when the players use quantum entanglement. Until recently, quantum parallel repetition theorems have only been established for special classes of games, but none were applicable to all games. In this talk, I'll discuss two new results on quantum parallel repetition theorems that apply to all games, including the first result that shows the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1.
Joint work with Mohammad Bavarian and Thomas Vidick.
