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. In Chapter 2 we address the question of how much quantum correlations generated by entanglement 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. We give two games exhibiting quantum-classical separations close to optimal. Remarkably, our results in theoretical physics are inspired by theoretical computer science. Chapter 3 is dedicated to the study of quantum graph parameters. Well-known quantities such as the chromatic number and the independence number of a graph can be interpreted as parameters for non-local games. A definition of quantum graph parameters follows from this fact. We contribute to the field in a number of ways. Among other results, we find a surprising characterization of the quantum chromatic number that relates to the Kochen-Specker theorem, a result in the foundations of quantum mechanics. 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 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 behaviours. To do that, we use results in combinatorics, linear algebra, optimization and number theory.
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. In Chapter 2 we address the question of how much quantum correlations generated by entanglement 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. We give two games exhibiting quantum-classical separations close to optimal. Remarkably, our results in theoretical physics are inspired by theoretical computer science. Chapter 3 is dedicated to the study of quantum graph parameters. Well-known quantities such as the chromatic number and the independence number of a graph can be interpreted as parameters for non-local games. A definition of quantum graph parameters follows from this fact. We contribute to the field in a number of ways. Among other results, we find a surprising characterization of the quantum chromatic number that relates to the Kochen-Specker theorem, a result in the foundations of quantum mechanics. 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 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 behaviours. To do that, we use results in combinatorics, linear algebra, optimization and number theory.
In this PhD thesis we study the effects of quantum entanglement, one of quantum mechanics most peculiar features, in nonlocal games and communication problems in zero-error information theory. A nonlocal game is a thought experiment in which two cooperating players, who are forbidden to communicate, want to perform a certain task. Zero-error information theory is the mathematical field that studies communication problems where no error is tolerated. The unifying link among the various scenarios we consider is their combinatorial nature and in particular their reformulations as graph theoretical problems, mainly concerning the chromatic and stability numbers and some quantum generalizations thereof. In this thesis we propose a novel approach to the study of these quantum graph parameters using the paradigm of conic optimization. For that, we introduce and study the completely positive semidefinite cone, a new matrix cone consisting of all symmetric matrices that admit a Gram representation by positive semidefinite matrices. Furthermore, we investigate whether entanglement allows for better-than-classical communication schemes in some well-known problems from zero-error information theory. For example we study the channel coding problem, which asks a sender to transmit data reliably to a receiver in the presence of noise, as well as some of its generalizations.
Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].
Alice and Bob receive a bipartite state (possibly entangled) from some finite collection or from some subspace. Alice sends a message to Bob through a noisy quantum channel such that Bob may determine the initial state, with zero chance of error. This framework encompasses, for example, teleportation, dense coding, entanglement assisted quantum channel capacity, and one-way communication complexity of function evaluation. With classical sources and channels, this problem can be analyzed using graph homomorphisms. We show this quantum version can be analyzed using homomorphisms on non-commutative graphs (an operator space generalization of graphs). Previously the Lovász ϑ number has been generalized to non-commutative graphs; we show this to be a homomorphism monotone, thus providing bounds on quantum source-channel coding. We generalize the Schrijver and Szegedy numbers, and show these to be monotones as well. As an application, we construct a quantum channel whose entanglement assisted zero-error one-shot capacity can only be unlocked using a non-maximally entangled state. These homomorphisms allow definition of a chromatic number for non-commutative graphs. Many open questions are presented regarding the possibility of a more fully developed theory.
Given one or more uses of a classical channel, only a certain number of messages can be transmitted with zero probability of error. The study of this number and its asymptotic behavior constitutes the field of classical zero-error information theory. We show that, given a single use of certain classical channels, entangled states of a system shared by the sender and receiver can be used to increase the number of (classical) messages which can be sent without error. In particular, we show how to construct such a channel based on any proof of the Kochen-Specker theorem. We investigate the connection to pseudotelepathy games. The use of generalized nonsignaling correlations to assist in this task is also considered. In this case, an elegant theory results and, remarkably, it is sometimes possible to transmit information with zero error using a channel with no unassisted zero-error capacity.
This dissertation contains results on three quite different topics. First, I investigate the entanglement resources required for two parties to jointly implement a unitary operation using local operations and classical communication (LOCC). If this resource is of smallest feasible Schmidt rank then it must be maximally entangled. If the Schmidt rank is higher, less entanglement may suffice. Second, I investigate the source of the “quantum speedup”. I quantify quantum interference and show that in order for a quantum computer to be significantly faster than a classical computer, it must make use of operations capable of producing large amounts of interference (or a large number of operations that can produce small amounts of interference). A quantum computer not making use of such a resource can be efficiently simulated by a classical computer. Third, I investigate zero-error source-channel coding. In this scenario, Alice wishes to convey a message to Bob through a noisy channel, with zero chance of error, in the case where Bob already has some prior knowledge regarding the message that is to be sent. For classical messages and classical channels, it was known that three graph invariants of Lovász, Szegedy, and Schrijver provide necessary conditions for this task. We show that this applies also when Alice and Bob make use of an entangled state, unifying and extending a series of previous results. Finally, I introduce a fully quantum version of source-channel coding where the message to be sent, the channel, and the side information are all quantum. Whereas the classical case makes use of graphs, the quantum case makes use of non-commutative graphs. I generalize the concept of graph homomorphism, as well as the Szegedy and Schrijver numbers, to non-commutative graphs and show that the necessary conditions for the classical case generalize to the quantum case. Using this theory, I construct a quantum channel whose one-shot zero-error entanglement assisted capacity can only be unlocked using a non-maximally entangled state, showing that in this case less is more when it comes to entanglement resources.
We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.