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.
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.
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.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
This thesis aims to improve our understanding of the structure of quantum entanglement and the limits of information processing with quantum systems. It presents new results relevant to three threads of quantum information: the theory of quantum entanglement, the communication capabilities of quantum channels, and the quantum zero-error information theory. \nIn the first part, we investigate the fundamental features of quantum entanglement and develop quantitative approaches to better exploit the power of entanglement. First, we introduce a computable and additive entanglement measure to quantify the amount of entanglement, which also plays an important role as the improved semidefinite programming (SDP) upper bound of distillable entanglement. Second, we show that the Rains bound is neither additive nor equal to the asymptotic relative entropy of entanglement. Third, we establish SDP lower bounds for the entanglement cost and demonstrate the irreversibility of asymptotic entanglement manipulation under positive-partial-transpose-preserving quantum operations, resolving a major open problem in quantum information theory. \nIn the second part, we develop a framework of semidefinite programs to evaluate the classical and quantum communication capabilities of quantum channels in both the non-asymptotic and asymptotic regimes. In particular, we establish the first general SDP strong converse bound on the classical capacity of an arbitrary quantum channel and give in particular the best known upper bound on the classical capacity of the amplitude damping channel. We further establish a finite resource analysis of classical communication over quantum erasure channels, including the first second-order expansion of classical capacity beyond entanglement-breaking channels. For quantum communication, we establish the best SDP-computable strong converse bound and refine it as the so-called max-Rains information. \nIn the third part, we investigate the quantum zero-error information theory. In contrast to the conventional Shannon theory, there is a very different-looking information theory when errors are required to be precisely zero, where the communication problem reduces to the analysis of the so-called confusability graph (noncommutative graph) of a classical channel (quantum channel). We develop an activated communication model and explore its novel properties. Notably, we separate the quantum Lovász number and the entanglement-assisted zero-error capacity, resolving an intriguing open problem in the area of zero-error information.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.
Abstract The max-relative entropy and the conditional min-entropy of a quantum state plays a central role in one-shot and zero-error quantum information theory. One attractive feature of this quantity is that it can be expressed as an optimization over the cone of positive semidefinite operators. Recently, it was shown that when replacing this cone with the cone of separable operators, a new type of conditional min-entropy emerges that admits an operational interpretation in terms of communicating classical information over a quantum channel. In this work, we explore more deeply the idea of building information-theoretic quantities from different base cones and determine which results in quantum information theory rely upon the positive semidefinite cone and which can be generalized. In terms of asymptotic information processing, we find that the standard equipartition properties break down if a given cone fails to approximate the positive semidefinite cone sufficiently well. We also show that the near-equivalence of the smooth max and Hartley entropies breaks down in this setting. We present parallel results for the extended conditional min-entropy, which requires extending the notion of k-superpositive channels to superchannels. On the other hand, we show that for classical-quantum states the separable cone is sufficient to re-cover the asymptotic theory, thereby drawing a strong distinction between the fully and partial quantum settings. We also present operational uses of this framework. We show that the cone restricted min-entropy of a Choi operator captures a measure of entanglement-assisted noiseless classical communication using restricted measurements. We also introduce a novel min-entropy-like quantity that captures the conditions for when one quantum channel can be transformed into another using bistochastic pre-processing. Lastly, we relate this framework to general conic norms and their non-additivity. Throughout this work, we concretely study generalized entropies in resource theories that capture locality and resource theories of coherence/Abelian symmetries.
This thesis focuses on the intersection of mathematical and computational optimization and quantum information. Main contributions are open-source software code: A hybrid approach mixing "traditional" nonconvex and convex methods can make difficult problems more accessible. A demonstration of how to efficiently implement such an algorithm, avoiding interfacial bottlenecks, is provided, finding optimal protocols to establish entanglement through a lossy channel. The central software package developed addresses polynomial optimization problems. Many problems naturally involve only a polynomial objective and constraint polynomials. Such problems can automatically be cast into semidefinite programs that provide a hierarchy of outer approximations. The resulting problems are often so large and scale so unfavorably with respect to the variable number and degree involved that the boundary of the doable is reached quickly. However, technical progress both in hardware and algorithms has pushed this boundary - but software frameworks for polynomial optimization have not followed in the same manner, often now making them the bottleneck that before was the solver. The package PolynomialOptimization.jl developed during this thesis aims to fill the gap and provide a very resource-efficient intermediate layer together with a wide number of algorithms to reduce the problem size, and naturally supporting complex numbers and semidefinite constraints ubiquitous in quantum information problems. Its application on an entanglement distribution problem is demonstrated, showing that even relaxations with semidefinite matrices of three- and four-digit size can be solved conveniently. Finally, a new way to calculate interior-point barriers for the cone of sums-of-squares matrices in a nearly time-optimal way is developed, whose efficient implementation has the potential of further reducing resource consumption.