Quantum entanglement in non-local games, graph parameters and zero-error information theory
Giannicola Scarpa

Abstract:
We study quantum entanglement and some of its applications in graph
theory and zero-error information theory.

In Chapter 1 we introduce entanglement and other fundamental concepts
of quantum theory.  Entanglement was first described in 1935 by
Einstein, Podolsky and Rosen, who observed that it allowed for
stronger-than-classical correlations between distant particles. They
did not believe such correlations existed in nature, and interpreted
this as evidence for incompleteness or incorrectness of quantum
mechanics. Bell took the next step in 1964, proposing an experiment to
test whether such non-classical behavior occurs in nature. He showed
that classical input-output correlations satisfy a certain inequality,
called a Bell inequality. Then, he showed that quantum mechanics
allows for correlations that violate it.  Aspect et al., in the early
1980s, realized such an experiment for the first time, showing that
Nature violated a Bell inequality. Therefore, Nature does not follow
the rules of classical physics!

In this thesis we make use of quantum entanglement as a resource for
various information-processing tasks.  In Chapter 2 we address the
question of how much quantum correlations can deviate from classical
predictions. We focus on non-local games: experiments in which two
players are separated and forbidden to communicate, and have to
collaborate to accomplish a task. In this case, a Bell inequality is
an upper bound on the maximum success probability of classical
players.  We have a Bell inequality violation when quantum players use
an entangled state to achieve a larger success probability.  Upper
bounds on Bell inequality violation of Gs were given by Junge et
al. in 2009. They proved that the maximum violation depends on the
number of possible inputs and outputs of each player, and on the
dimension of the entangled state. We give ower bounds in the form of
two games exhibiting violations that are very close to the upper
bounds of Junge et al.  Remarkably, our results in theoretical physics
are inspired by theoretical computer science. The first non-local game
is based on a communication complexity problem called "hidden
matching", while the second one derives from the work of Khot and
Vishnoi on the famous Unique Games Conjecture from computational
complexity theory.

Chapter 3 is dedicated to the study of quantum graph parameters.
Interestingly, well-known quantities such as the chromatic number and
the independence number of a graph can be interpreted as parameters
for non-local games.  For example, a "referee" can test if two
players, Alice and Bob, have a k-coloring of a graph G, i.e., an
assignment of one out of k colors for each vertex of the graph such
that adjacent vertices get different colors. He separates the two
players, gives each of them a vertex of G, and asks them for the color
(out of the k possible) of that vertex. If he gave Alice and Bob the
same vertex, he expects to receive back the same color, if he gave
them two adjacent vertices, he expects to get two different
colors. The minimum number of colors k such that Alice and Bob have a
classical strategy that always succeeds is the chromatic number of
G. If Alice and Bob can use quantum entanglement, then the minimum k
such that they always win is called the quantum chromatic number of
the graph. For some graphs, it can be strictly smaller than the
classical one.  %A similar discussion can be made for the independence
number: quantum payers can "fool" a referee into believing that they a
graph has an independent set much larger than its classical
independence number.  The study of quantum graph parameters officially
started with two papers by Cameron et al. in 2010 and Cubitt et al. in
2009, but was implicit in earlier work.  We contribute to the field in
a number of ways. We study the relationship between these quantum
graph parameters and other parameters such as the Lovász ϑ number and
the orthogonal rank. We find a surprising characterization of the
graphs having a separation between the quantum and classical chromatic
numbers. This is related to the Kochen-Specker theorem, a result in
the foundations of quantum mechanics from 1967. We also find various
constructions of graphs that feature separations between the quantum
and classical independence numbers, based for example on graph
products and graph states. Additionally, we use quantum graph
parameters to give bounds on the value of general non-local games.

In Chapter 4, we move to zero-error information theory. We study the
zero-error capacity of a classical noisy channel when the sender and
the receiver can use quantum entanglement. We also study the source
problem, where the receiver has partial information about the message
that is going to be delivered, as well as the combined source-channel
problem.  The main tools in this field are graphs and their
parameters, so zero-error information theory with entanglement is a
fertile field for the concepts studied in previous chapters. For
example, the capacity of a channel can be calculated using the
independence number of a graph and the source-problem is related to
the chromatic number of a graph.  We define the entangled chromatic
number, the entangled independence number and other related
quantities. The exact relation with the parameters of Chapter 3 is
still an open problem.  We initiate the study of the source problem
and source-channel problem with entanglement and we find channels and
sources that exhibit a strong divergence in quantum and classical
behaviors. To do that, we use results in combinatorics, linear
algebra, optimization and number theory.

This thesis is based on the following articles:
 - "Near-optimal and explicit Bell inequality violations", by H. Buhrman, O. Regev, the author and R. de Wolf. Theory of Computing, December 2012.
 - "Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number", by the author and S. Severini. IEEE Transactions on Information Theory, April 2012.
 - "New Separations in Zero-error Channel Capacity through Projective Kochen-Specker Sets and Quantum Coloring", by L. Mančinska, the author and S. Severini. IEEE Transactions on Information Theory, June 2013.
 - "Exclusivity structures and graph representatives of local complementation orbits", by A. Cabello, M. G. Parker, the author and S. Severini. Journal of Mathematical Physics, July 2013.
 - "Zero-error source-channel coding with entanglement", by J. Briët, H. Buhrman, M. Laurent, T. Piovesan and the author. Proceedings of Eurocomb'13, September 2013.