Parallel repetition theorems for all entangled games
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.
Subscribe to A Quantum Bit
Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...
Sign Up Now
Sign up to receive A Quantum Bit in your email!