Bounds on quantum nonlocality

Abstract

Nonlocality is one of the most intriguing aspects of quantum theory which reveals that nature is intrinsically different than our classical view of the world. One of the main goals in the study of quantum nonlocality is to determine the maximum violation achieved by quantum correlations in a Bell scenario. However, given a Bell inequality, there is no general algorithm to perform this task. As an intermediate step, the development of efficiently computable bounds has played an important role for the advance of the field. In this thesis we present our contributions exploring efficiently computable bounds, based on a normof some matrices, to the quantum value of a particular class o Bell inequ alities:the linear games. In the first part of the thesis we introduce the necessary background to follow the main results: Concepts and results of optimization and computational complexity theories, focusing on nonlocality problems; Theframework of nonlocal games as a particular class of Bell inequalities; And the graph-theoretic approach to nonlocality. In the second part we present our main results concerning the characterization of necessary and sufficient conditions for an XOR game to have no quantum advantage, and we prove an efficiently computable upper bound to the quantum value of linear games. The main outcomes of the research presented in this thesis are: (i) The determination of the Shannon capacity for a new family of graphs; (ii) A larger alphabet generalization of the principle of no-advantage for nonlocal computation; (iii) And a systematic way to design device-independent witnesses of genuine multipartite entanglement for tripartite systems.