Abstract
We investigate a simple class of multi-prover interactive proof systems (classical non-local games), called binary constraint system (BCS) games, and characterize those that admit a perfect entangled strategy (i.e., a strategy with value 1 when the provers can use shared entanglement). Our characterization is in terms of a system of matrix equations. One application of this characterization is that, combined with a recent result of Arkhipov, it leads to a simple algorithm for determining whether certain restricted BCS games have a perfect entangled strategy, and, for the instances that do not, for bounding their value strictly below 1. An open question is whether, for the case of general BCS games, making this determination is computationally decidable. Our characterization might play a useful role in the resolution of this question.
Full version is available at http://arxiv.org/abs/1209.2729
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aravind, P.K.: Bell’s Theorem without inequalities and only two distant observers. Found. Phys. Lett. 15(4), 397–405 (2002)
Aravind, P.K.: Quantum mysteries revisited again. Am. J. Phys. 72, 1303–1307 (2004)
Arkhipov, A.: Extending and characterizing quantum magic games. arXiv:1209.3819 [quant-ph] (2012)
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998)
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1, 3–40 (1991)
Bell, J.S.: On the Einstein-Podolsky-Rosen paradox. Physics 1, 195–200 (1964)
Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: How to remove intractability assumptions. In: Proc. of the 20th ACM Symp. on Theory of Computing (STOC 1988), pp. 113–131 (1988)
Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23(15), 880–884 (1969)
Cleve, R., Høyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proc. of the 19th IEEE Conf. on Computational Complexity (CCC 2004), pp. 236–249 (2004)
Cleve, R., Mittal, R.: Characterization of binary constraint system games (2013), http://arxiv.org/abs/1209.2729
Cameron, P.J., Montanaro, A., Newman, M.W., Severini, S., Winter, A.: On the quantum chromatic number of a graph. The Electronic Journal of Combinatorics [Electronic Only] 14(1):Research Paper R81, 15 (2007)
Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268–292 (1996)
Ji, Z.: Binary constraint system games and locally commutative reductions. arXiv:1310.3794 [quant-ph] (2013)
Mermin, N.D.: Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett. 65(27), 3373–3376 (1990)
Mermin, N.D.: Hidden variables and the two theorems of John Bell. Rev. Mod. Phys. 65(3), 803–815 (1993)
Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge University Press, Cambridge (2000)
Speelman, F.: Personal communication (2011)
Cirel’son, B.S.: Quantum generalizations of Bell’s inequality. Lett. in Math. Phys. 4(2), 93–100 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cleve, R., Mittal, R. (2014). Characterization of Binary Constraint System Games. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)