کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438680 | 690309 | 2013 | 7 صفحه PDF | دانلود رایگان |

One of the most fascinating consequences of quantum theory are non-local correlations: Two–possibly distant–parts of a system can have a behavior under measurements unexplainable by shared information. A manifestation thereof is so-called pseudo-telepathy: Tasks that can be performed by two parties who share a quantum state, whereas classically, communication would be necessary to always succeed. We show that pseudo-telepathy games can often be modeled by graphs: The classical strategy to win the game is a coloring of this graph with a given number of colors. We discuss these parallels and study the class of graphs corresponding to the first two-party pseudo-telepathy game, proposed by Brassard, Cleve, and Tapp in 1999. This leads to a proof that the game indeed has the desired property.
Journal: Theoretical Computer Science - Volume 486, 20 May 2013, Pages 20-26