RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Parallel repetition theorems for all entangled games

June 8, 2016 - 11:00am
Henry Yuen

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.

CSS 3100A

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!

 Have an idea for A Quantum Bit? Submit your suggestions to