- Quantum entanglement in non-local games, graph parameters and zero-error information theory
- Award date
- 27 November 2013
- Number of pages
- Amsterdam: Institute for Logic, Language and Computation
- Document type
- PhD thesis
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
- Research conducted at: Universiteit van Amsterdam
Series: ILLC dissertation series DS-2013-03
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.