Second International Conference on Quantum, Nano and Micro Technologies (ICQNM 2008) Classical, Quantum and Non-signalling Resources in Bipartite Games February 10-February 15 ISBN: 978-0-7695-3085-7
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICQNM.2008.18
We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games admit a non-signalling winning strategy is in P. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudo-telepathy game yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.
Index Terms:
Game Theory, Graph Theory, Nonlocality, Bell Theorems, Interactive Proof Systems
Citation:
Gilles Brassard, Anne Broadbent, Esther H?nggi, Andr? Allan M?thot, Stefan Wolf, "Classical, Quantum and Non-signalling Resources in Bipartite Games," icqnm, pp.80-89, Second International Conference on Quantum, Nano and Micro Technologies (ICQNM 2008), 2008 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb