Abstract
In this work we study the sets of two-party correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, no-signaling and unrestricted correlations can be expressed as projections of affine sections of appropriate convex cones. As a by-product, we identify a spectrahedral outer approximation to the set of quantum correlations which is contained in the first level of the Navascués, Pironio and Acín (NPA) hierarchy and also a sufficient condition for the set of quantum correlations to be closed. Furthermore, by our conic formulations, the value of a nonlocal game over the sets of classical, quantum, no-signaling and unrestricted correlations can be cast as a linear conic program. This allows us to show that a semidefinite programming upper bound to the classical value of a nonlocal game introduced by Feige and Lovász is in fact an upper bound to the quantum value of the game and moreover, it is at least as strong as optimizing over the first level of the NPA hierarchy. Lastly, we show that deciding the existence of a perfect quantum (resp. classical) strategy is equivalent to deciding the feasibility of a linear conic program over the cone of completely positive semidefinite matrices (resp. completely positive matrices). By specializing the results to synchronous nonlocal games, we recover the conic formulations for various quantum and classical graph parameters that were recently derived in the literature.
Similar content being viewed by others
References
Aspect, A., Grangier, P., Roger, G.: Experimental realization of Einstein–Podolsky–Rosen–Bohm–Gedanken experiment: a new violation of Bell’s inequalities. Phys. Rev. Lett. 49, 91–94 (1982)
Barvinok, A.: A Course in Convexity. American Mathematical Society, Providence (2002)
Bell, J.S.: On the Einstein–Podolsky–Rosen paradox. Physics 1(3), 195–200 (1964)
Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MOS-SIAM Series on Optimization (2001)
Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003)
Berta, M., Fawzi, O., Scholz, V.B.: Quantum bilinear optimization. arXiv:1506.08810 (2015)
Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V., Wehner, S.: Bell nonlocality. Rev. Mod. Phys. 86(2), 419 (2014)
Burgdorf, S., Laurent, M., Piovesan, T.: On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. arXiv:1502.02842 (2015)
Cameron, P.J., Montanaro, A., Newman, M.W., Severini, S., Winter, A.: On the quantum chromatic number of a graph. Electr. J. Comb. 14(1). arXiv:quant-ph/0608016 (2007)
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: Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pp. 236–249 (2004)
Cleve, R., Slofstra, W., Unger, F., Upadhyay, S.: Perfect parallel repetition theorem for quantum XOR proof systems. Comput. Complex. 17(2), 282–299 (2008)
Colbeck, R.: Quantum and relativistic protocols for secure multi-party computation. Ph.D. thesis, Trinity College, University of Cambridge (2006)
de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002)
Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th ACM Symposium on Theory of Computing (2014)
Dinur, I., Steurer, D., Vidick, T.: A parallel repetition theorem for entangled projection games. In: Proceedings of the 29th IEEE Conference on Computational Complexity, pp. 197–208 (2014)
Dykema, K.J., Paulsen, V.: Synchronous correlation matrices and Connes’ embedding conjecture. J. Math. Phys. 57, 015214 (2016)
Ekert, A.K.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67(6), 661–663 (1991)
Feige, U., Lovász, L.: Two-prover one-round proof systems: their power and their problems. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 733–744. ACM (1992)
Freedman, S.J., Clauser, J.F.: Experimental test of local hidden-variable theories. Phys. Rev. Lett. 28, 938–941 (1972)
Fritz, T.: Polyhedral duality in Bell scenarios with two binary observables. J. Math. Phys. 53, 072202 (2012)
Fritz, T.: Tsirelson’s problem and Kirchberg’s conjecture. Rev. Math. Phys. 24(5), 1250012 (2012)
Ji, Z.: Binary constraint system games and locally commutative reductions. arXiv:1310.3794 (2013)
Kempe, J., Regev, O., Toner, B.: Unique games with entangled provers are easy. SIAM J. Comput. 39(7), 3207–3229 (2010)
Lasserre, J.B.: New approximations for the cone of copositive matrices and its dual. Math. Program. 144(1–2), 265–276 (2013)
Laurent, M., Piovesan, T.: Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. SIAM J. Optim. 25(4), 2461–2493 (2015)
Mančinska, L., Roberson, D.E.: Note on the correspondence between quantum correlations and the completely positive semidefinite cone. Unpublished manuscript, available at https://sites.google.com/site/davideroberson/ (2014)
Mančinska, L., Roberson, D.E.: Quantum homomorphisms. J. Comb. Theory Ser. B 118, 228–267 (2016)
Mančinska, L., Roberson, D.E., Varvitsiotis, A.: On deciding the existence of perfect entangled strategies for nonlocal games. Chicago J. Theor. Comput. Sci. arXiv:1506.07429 (2016)
Maxfield, J.E., Minc, H.: On the matrix equation \(X^{\prime }X = A\). Proc. Edinb. Math. Soc. (Ser. 2) 13(02), 125–129 (1962)
Navascués, M., Pironio, S., Acín, A.: A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys. 10(7), 073013 (2008)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)
Paulsen, V.I., Severini, S., Stahlke, D., Todorov, I.G., Winter, A.: Estimating quantum chromatic numbers. J. Funct. Anal. 270(6), 2188–2222 (2016)
Roberson, D.E.: Conic formulations of graph homomorphisms. J. Algebraic Comb. 43(4), 877–913 (2016)
Sikora, J., Varvitsiotis, A., Wei, Z.: On the minimum dimension of a Hilbert space needed to generate a quantum correlation. arXiv:1507.00213 (2015)
Tsirelson, B.S.: Quantum analogues of the Bell inequalities: the case of two spatially separated domains. J. Sov. Math. 36, 557–570 (1987)
Upadhyay, S.: Quantum Information and Variants of Interactive Proof Systems. Ph.D. thesis, University of Waterloo (2011)
Watrous, J.: Theory of quantum information, lecture notes. https://cs.uwaterloo.ca/~watrous/LectureNotes.html (2011)
Acknowledgments
The authors would like to thank the referees for carefully reading the paper and for their useful comments. Furthermore, the authors thank S. Burgdorf, M. Laurent, L. Mančinska, T. Piovesan, D. E. Roberson, S. Upadhyay, T. Vidick and Z. Wei for useful discussions. A.V. is supported in part by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13. J.S. is supported in part by NSERC Canada. Research at the Centre for Quantum Technologies at the National University of Singapore is partially funded by the Singapore Ministry of Education and the National Research Foundation, also through the Tier 3 Grant “Random numbers from quantum processes,” (MOE2012-T3-1-009).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sikora, J., Varvitsiotis, A. Linear conic formulations for two-party correlations and values of nonlocal games. Math. Program. 162, 431–463 (2017). https://doi.org/10.1007/s10107-016-1049-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-016-1049-8
Keywords
- Quantum correlations
- Nonlocal games
- Completely positive semidefinite cone
- Completely positive cone
- Linear conic programming
- Quantum graph parameters
- Semidefinite programming relaxations