Hardness amplification for entangled games via anchoring
| Autor: | Mohammad Bavarian, Henry Yuen, Thomas Vidick |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Computer Science::Computer Science and Game Theory 0209 industrial biotechnology TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Conjecture Repetition (rhetorical device) Quantum pseudo-telepathy ComputingMilieux_PERSONALCOMPUTING Combinatorial game theory TheoryofComputation_GENERAL 0102 computer and information sciences 02 engineering and technology Quantum entanglement 01 natural sciences 020901 industrial engineering & automation Transformation (function) 010201 computation theory & mathematics Simple (abstract algebra) Completeness (statistics) Mathematics |
| Zdroj: | STOC |
| DOI: | 10.1145/3055399.3055433 |
| Popis: | We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called anchoring, inspired in part by the Feige-Kilian transformation, that turns any (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|