Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function

Abstract

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 operator space 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 Lovasz' famous theta function, as the norm-completion (or stabilisation) of a "naive" generalisation of theta. 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 Lovasz' original theta in the classical case, give several applications, and propose to study the operator spaces associated to channels as "non-commutative graphs", using the language of Hilbert modules.

24 pages: v2 has added discussion and more details in section 7.

References in corpus (4)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Zero-error channel capacity and simulation assisted by non-local correlations
• Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function
• Entanglement between Two Uses of a Noisy Multipartite Quantum Channel Enables Perfect Transmission of Classical Information

Cited by in corpus (61)

• On the power of PPT-preserving and non-signalling codes
• Semidefinite programming strong converse bounds for classical capacity
• Lower bounds on the Probability of Error for Classical and Classical-Quantum Channels
• No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number
• Semidefinite programming relaxations for quantum correlations
• A compositional approach to quantum functions
• The Morita theory of quantum graph isomorphisms
• Quantum source-channel coding and non-commutative graph theory
• Approximate Quantum Error Correction Revisited: Introducing the Alpha-bit
• On superactivation of zero-error capacities and reversibility of a quantum channel
• On the mixed-unitary rank of quantum channels
• Semi-definite programming and quantum information
• A semidefinite programming upper bound of quantum capacity
• The quantum-to-classical graph homomorphism game
• Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
• Positivity, Discontinuity, Finite Resources and Nonzero Error for Arbitrarily Varying Quantum Channels
• On zero-error communication via quantum channels in the presence of noiseless feedback
• Sandwich theorems and capacity bounds for non-commutative graphs
• Zoology of Atlas-groups: dessins d'enfants, finite geometries and quantum commutation
• Complexity and capacity bounds for quantum channels
• Quantum Privacy and Schur Product Channels
• Observations on Graph Invariants with the Lovász $\vartheta$-Function
• Quantum graphs: different perspectives, homomorphisms and quantum automorphisms
• On channels with positive quantum zero-error capacity having vanishing n-shot capacity
• Reversibility of a quantum channel: general conditions and their applications to Bosonic linear channels
• Entanglement-assisted zero-error source-channel coding
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• On non-commutative operator graphs generated by reducible unitary representation of the Heisenberg-Weyl group
• Classification of Quantum Graphs on $M_2$ and their Quantum Automorphism Groups
• Random quantum graphs
• Unitary transformations of fibre functors
• Non-commutative graphs based on finite-infinite system couplings: quantum error correction for a qubit coupled to a coherent field
• Uncertainty relations from state polynomial optimization
• Quantum Error Correction and One-Way LOCC State Distinguishability
• Maximum privacy without coherence, zero-error
• On the quantum no-signalling assisted zero-error classical simulation cost of non-commutative bipartite graphs
• On optimal entanglement assisted one-shot classical communication
• Exclusivity structures and graph representatives of local complementation orbits
• Multi-party zero-error classical channel coding with entanglement
• The Extension of Unital Completely Positive Semigroups on Operator Systems to Semigroups on $C^{\ast }$-algebras
• Quantum teleportation in the commuting operator framework
• Vector Representations of Graphs and Distinguishing Quantum Product States with One-way LOCC
• Hereditarily antisymmetric operator algebras
• Covariant quantum combinatorics with applications to zero-error communication
• On n-partite superactivation of quantum channel capacities
• A natural deduction system for orthomodular logic
• On errors generated by unitary dynamics of bipartite quantum systems
• A category of quantum posets
• No quantum Ramsey theorem for stabilizer codes
• Quantum non-signalling assisted zero-error classical capacity of qubit channels
• Information theoretic parameters of non-commutative graphs and convex corners
• An upper bound on quantum capacity of unital channels
• Repeated temperature measurements in quantum thermodynamics
• Operator and Graph Theoretic Techniques for Distinguishing Quantum States via One-Way LOCC
• Quantum Suplattices
• Zero-error communication under discrete-time Markovian dynamics
• Activation of zero-error classical capacity in low-dimensional quantum systems
• Approximating projections by quantum operations
• Algebraic connectedness and bipartiteness of quantum graphs
• Information storage and transmission under Markovian noise
• Complete Classification of Directed Quantum Graphs on M2