Grothendieck Inequalities, Nonlocal Games and Optimization

htmlabstractMotivated by applications in quantum information theory and optimization we introduce new variants of a celebrated inequality known as Grothendieck's Inequality. In quantum information theory we apply these mathematical tools to study of one of the most surprising and counter-intuitive predictions of Quantum Mechanics: entanglement. In optimization we use them to determine the precision of efficient approximation algorithms for geometric problems that arise naturally from the study of entanglement and from models of interacting particles considered in classical statistical physics. In this thesis we study entanglement by using nonlocal games. A nonlocal game involves two or more players who are not allowed to communicate with each other, but do interact with an extra party usually referred to as the referee. At the start of the game the referee asks each of the players a question, upon which they each reply to him with some answer. Then, the referee decides if the players win or lose based only on the questions he asked and the answers he received. The players know in advance what set of answers would cause them to win, which of course is their objective. The catch is that they only know the question that was aimed directly at them and not any of the other players' questions. The players thus don't play against each other, but should somehow coordinate their strategies to win. The best course of action for players who live in a world described by Classical Mechanics is the simplest kind imaginable: just fix in advance what to answer to each question. In a Quantum Mechanical world, more sophisticated strategies sometimes give better results. Each player can base their answer on the outcome of an experiment done on some private physical system. The key feature of such strategies is that they can cause the players to produce answers that are correlated in ways that are impossible in a classical world. In this case the players are said to be entangled. The fact that Quantum Mechanics predicts such phenomena was used by Einstein, Podolski and Rosen in 1935 to argue that this theory must be incomplete, as surely entanglement could not be part of a reasonable description of Nature. Surprisingly, experiments done by Aspect et al. in the 1980's gave convincing evidence that the world we live does in fact allow for this! Entanglement is usually mathematically described by a vector in a Hilbert space. Such a vector is referred to as a state. We prove that for a large class of states the advantage gained by using them over classical strategies in the simplest nonlocal games involving three or more players is severely limited. As a bonus, the proof of this result can also be used to resolve a 35-year-old open problem posed by Varopoulos in an area of mathematics called Banach Space Theory. Optimization means searching over a huge collection to find some element with the best characteristics. One example of such a problem is finding a strategy for a nonlocal game that maximizes the players' winning probability. An second example is to optimize the directions of the magnetic fields of interacting particles so as to minimize the total energy of the system. The most-studied optimization problems usually have a combinatorial nature. For example, finding an optimal classical strategy for a nonlocal game or minimizing the energy of interacting particles described by the celebrated Ising model amounts to searching over a discrete set of possibilities. In this thesis we consider problems with a more geometric flavor. To picture this, imagine searching for some optimal configuration of a finite number of points on a three-dimensional sphere. Such problems arise naturally from the study of entanglement when one restricts the amount of entanglement players are allowed to use in nonlocal games, and from the Heisenberg model of interacting particles in classical statistical physics. Unfortunately, most problems like the ones described above likely can't be solved exactly by any computer in a reasonable amount of time. If time is of the essence, then the next-best thing is to search for any solution that is near-optimal, but can be found in a reasonable amount of time. We will use new variants of Grothendieck's Inequality to analyze algorithms that offer exactly such an alternative for the geometric optimization problems mentioned above