We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.
We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.
We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain subspace of operators (so-called operator systems) as the quantum generalization of the adjacency matrix, in terms of which the zero-error capacity of a quantum channel, as well as the quantum and entanglement-assisted zero-error capacities can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous ϑ function on general operator systems, as the norm-completion (or stabilization) of a “naive” generalization of ϑ. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite program, whose dual we write down explicitly, and that it is multiplicative with respect to the tensor product of operator systems (corresponding to the tensor product of channels). We explore various other properties of the new quantity, which reduces to Lovász' original ϑ in the classical case, give several applications, and propose to study the operator systems associated with channels as “noncommutative graphs,” using the language of Hilbert modules.
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.
We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain linear space operators as the quantum generalisation of the adjacency matrix, in terms of which the plain, quantum and entanglement-assisted capacity can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous υ function, as the norm-completion (or stabilisation) of a “naive” generalisation of υ. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite programme, whose dual we write down explicitly, and that it is multiplicative with respect to the natural (strong) graph product. We explore various other properties of the new quantity, which reduces to Lovász' original υ in the classical case, give several applications, and propose to study the linear spaces of operators associated to channels as “non-commutative graphs”, using the language of operator systems and Hilbert modules.
We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, IEEE Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).
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.
We propose in this note the study of quantum channels from association schemes. This is done by interpreting the (0,1)-matrices of a scheme as the Kraus operators of a channel. Working in the framework of one-shot zero-error information theory, we give bounds and closed formulas for various independence numbers of the relative non-commutative (confusability) graphs, or, equivalently, graphical operator systems. We use pseudocyclic association schemes as an example. In this case, we show that the unitary entanglement-assisted independence number grows at least quadratically faster, with respect to matrix size, than the independence number. The latter parameter was introduced by Beigi and Shor as a generalization of the one-shot Shannon capacity, in analogy with the corresponding graph-theoretic notion.