Tese de Doutorado #301: Gláucia Guimarães

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, there is no general algorithm to perform this task. As an intermediate step, the development of efficient computable bounds to the quantum value of Bell inequalities has played an important role for the advance of the field. In the first part of this thesis we introduce the necessary background to follow the main results: Concepts and results of optimization and computational complexity theories, focusing on nonlocality problems; The framework 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 an efficiently computable bound to the quantum value of a particular class of Bell inequalities known as 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 generalization of the principle of nonlocal computation for functions assuming d possible values. (iii) A systematic way to design device independent witnesses of genuine tripartite entanglement.