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.
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.
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 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.
There are various notions of positivity for matrices and linear matrix-valued maps that play important roles in quantum information theory. The cones of positive semidefinite matrices and completely positive linear maps, which represent quantum states and quantum channels respectively, are the most ubiquitous positive cones. There are also many natural cones that can been regarded as "more" or "less" positive than these standard examples. In particular, entanglement theory deals with the cones of separable operators and entanglement witnesses, which satisfy very strong and weak positivity properties respectively. Rather complementary to the various cones that arise in entanglement theory are norms. The trace and operator norms for operators and the diamond and completely bounded norms for superoperators are the typical norms that are seen throughout quantum information theory. In this work our main goal is to develop a family of norms that play a role analogous to the cone of entanglement witnesses. We investigate the basic mathematical properties of these norms, including their relationships with other well-known norms, their isometry groups, and their dual norms. We also make the place of these norms in entanglement theory rigorous by showing that entanglement witnesses arise from minimal operator systems, and analogously our norms arise from minimal operator spaces. Finally, we connect the various cones and norms considered here to several seemingly unrelated problems from other areas. We characterize the problem of whether or not non-positive partial transpose bound entangled states exist in terms of one of our norms, and provide evidence in favour of their existence. We also characterize the minimum gate fidelity of a quantum channel, the maximum output purity and its completely bounded counterpart, and the geometric measure of entanglement in terms of these norms.