Source-linked AI summary
Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
Runyao Duan, Simone Severini, Andreas Winter
TL;DR
The paper asks how Shannon's zero-error capacity problem extends to quantum channels and how their confusability structure should be represented. It models channels with non-commutative graphs, defines a stabilized quantum Lovász function, and shows that it upper-bounds entanglement-assisted messages while reducing to classical theta. The paper also develops applications and a Hilbert-module framework for non-commutative graph theory.
Problem
Quantum zero-error capacities require a graph-like operator-space formulation that accommodates unassisted, quantum, and entanglement-assisted communication.
Method
The paper represents channels by self-adjoint operator spaces, defines a norm-completed quantum theta function, and develops non-commutative graphs using Hilbert modules.
Results
The stabilized function upper-bounds entanglement-assisted capacity, recovers Lovász theta for classical graphs, and supports exact application results.
Takeaways & Limitations
Non-commutative graphs provide a common operator-space language for quantum zero-error communication and motivate further graph-theoretic structure.
Abstract
from arXiv · showhide
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.
I. CLASSICAL CHANNELS, GRAPHS AND ZERO-ERROR COMMUNICATION
Classical zero-error communication is represented by confusability graphs, where messages correspond to independent sets and asymptotic capacity is governed by graph products. Lovász's theta function provides a multiplicative semidefinite upper bound, motivating the paper's quantum extension.
- Channel graphs: A classical channel's confusability graph connects input symbols that can produce a common output, so zero-error codes are independent sets.Different messages require output distributions with disjoint supports.
- Channel graphs: Parallel channel use induces the strong graph product, and n uses correspond to the n-fold product G^n.The product channel acts on Cartesian-product input and output alphabets.
- Capacity: The zero-error capacity is asymptotic and can exceed the one-shot independence number, as illustrated by the pentagon C5 with capacity 1/2 log 5.Some graphs satisfy C0(G)=log α(G), but not all do.
- Capacity: Computing α(G) is NP-hard, while the computability of zero-error capacity remains unknown.There are graphs for which finite-block independence numbers never attain the asymptotic capacity.
- Lovász theta: Lovász's theta function is a semidefinite relaxation that upper-bounds α(G) and zero-error capacity while being multiplicative under graph products.It remains the best known general upper bound apart from specified exceptional constructions.
- Transition: The paper extends this classical framework to quantum channels, generalized confusability structures, and a quantum theta function.The later sections introduce quantum independence numbers, a semidefinite formulation, applications, and non-commutative graph theory.
II. QUANTUM CHANNELS AND NON-COMMUTATIVE GRAPHS
Quantum channels replace alphabets with finite-dimensional Hilbert spaces and classical confusability graphs with operator subspaces generated by Kraus operators. These non-commutative graphs capture channel structure, though they generally do not uniquely determine the originating channel.
- Quantum channels: A quantum channel is a completely positive trace-preserving map between operator spaces on finite-dimensional Hilbert spaces.States are density operators, and pure states are one-dimensional projectors.
- Non-commutative graphs: The non-commutative confusability graph is the operator subspace generated by products of Kraus operators E_j†E_k.This construction generalizes the zero-pattern information of a classical confusability graph.
- Non-commutative graphs: A subspace represents a non-commutative graph when it contains the identity and is closed under adjoints, and tensor-product channels yield tensor-product operator spaces.These conditions characterize the operator spaces associated with channels.
- Channel interpretation: The graph can be interpreted through the complementary channel: it is the space of operators measurable by the channel environment.The associated space is determined by the adjoint of the complementary channel and is independent of the Kraus representation.
- Scope: The operator space generally does not uniquely determine its channel because it omits transition probabilities and higher-order input-output incidence information.This non-uniqueness already occurs for classical graphs and channels.
- Graph operations: Post-processing enlarges the associated graph, while pre-processing induces a subgraph through the Stinespring isometry.Every non-commutative graph appears as an induced subgraph of a suitable product of empty and complete graphs.
III. ZERO-ERROR COMMUNICATION WITH AND WITHOUT ENTANGLEMENT
The paper defines several quantum independence numbers for unassisted, quantum-error-correcting, entanglement-assisted, and generalized codes. It establishes structural bounds, monotonicity, computability in principle, and severe complexity limitations.
- Independence notions: The ordinary independence number α(S) counts the largest set of mutually distinguishable pure-state messages determined by operator orthogonality to S.Computing α(S) is QMA-complete, paralleling the classical NP-completeness of α(G).
- Independence notions: The quantum independence number αq(S) is the largest dimension of a subspace satisfying the Knill-Laflamme error-correction condition.Such a subspace supports a decoding channel that recovers quantum information.
- Independence notions: The entanglement-assisted independence number eα(S) counts pairwise orthogonal outputs produced using shared entanglement and encoding channels.A unitary-restricted variant eαU(S) and a generalized variant bα(S) are also defined.
- Basic properties: For non-commutative graphs, the independence numbers obey ordering, dimension bounds, and monotonicity under pre- and postprocessing.In particular, dim S⊥<k(k−1) implies α(S)<k, while bα(S)≤1+dim S⊥.
- Complexity: The independence numbers are computable through finite algebraic formulations or semidefinite hierarchies, but the resulting algorithms are extremely inefficient.No runtime upper bound is given for eα and bα, and asymptotic capacities are not known to be decidable.
IV. A QUANTUM LOV ´ASZ FUNCTION
The paper introduces a quantum Lovász function and stabilizes it over tensoring with full matrix spaces. The stabilized quantity recovers classical theta, upper-bounds entanglement-assisted independence, and supports multiplicative and semidefinite-program formulations.
- Quantum theta: The naive quantum theta function ϑ(S) generalizes Lovász theta from graphs to non-commutative graphs and satisfies α(S)≤ϑ(S).It is monotonic under subgraphs and supermultiplicative under tensor products.
- Stabilization: The stabilized function eϑ(S) is defined by taking the supremum over auxiliary matrix dimensions and retains supermultiplicativity.The operator norm is used in the completion.
- Stabilization: The naive function is not multiplicative in general, even when tensoring with a trivial channel.This failure motivates a norm-completion or stabilization over auxiliary full matrix spaces.
- Classical reduction: For classical graphs, eϑ(S)=ϑ(S)=ϑ(G), so the stabilized quantum quantity reduces exactly to Lovász's theta function.The reduction follows from theta's multiplicativity and the matrix-space representation of complete graphs.
- Capacity bounds: The stabilized function upper-bounds entanglement-assisted independence and is monotonic under subgraphs, yielding C0E(S)≤log eϑ(S).This makes eϑ an upper bound on entanglement-assisted zero-error capacity.
V. SEMIDEFINITE FORMULATION AND OTHER PROPERTIES
The paper formulates the quantum Lovász theta function through a bounded-dimension semidefinite programme and an explicit dual. It establishes computability, multiplicativity, and monotonicity properties, including recovery of the classical Lovász theta programme.
- Semidefinite formulation: The extension dimension can be bounded by |A|, yielding a semidefinite optimisation that is efficiently computable.The bounded extension also enables an explicit dual minimisation programme for upper bounds on eϑ(S).
- Semidefinite formulation: Theorem 9 gives an explicit dual semidefinite programme for the same value eϑ(S).The dual objective is determined by the norm of a partial trace under the stated feasibility constraints.
- Multiplicativity: eϑ is multiplicative under the natural tensor product: eϑ(S1 ⊗S2) = eϑ(S1)eϑ(S2).The proof combines supermultiplicativity with submultiplicativity obtained by tensoring dual-feasible solutions.
- Monotonicity: eϑ is non-increasing under enlarging non-commutative graphs, induced subgraphs, and channel pre- and post-processing.For an induced subgraph S′, the paper states eϑ(S′) ≤ eϑ(S).
- Classical reduction: In the classical case, the dual simplifies to a semidefinite programme for Lovász' ϑ.The classical non-commutative graph imposes the condition Yxx′ = 0 whenever x̸∼x′, with J as the all-1 matrix.
VI. APPLICATIONS AND DISCUSSION
The paper applies the quantum Lovasz theta function to entanglement-assisted zero-error capacities, recovering classical results and evaluating several quantum-channel examples. It also identifies open questions about capacity characterisation, multiplicativity, and the relationships among entanglement-assisted independence numbers.
- C0E(S) ≤ log eϑ(S) for every non-commutative graph S, providing an upper bound on entanglement-assisted zero-error capacity.
- For classical graphs, eα(G) ≤ ϑ(G), answering an open question despite entanglement-assisted independence exceeding α(G) in some cases.
- For Bell-Kochen-Specker channels, eα(G) = ϑ(G) = n and C0E(G) = log n.The equality follows from matching lower and upper bounds, including a dual feasible solution.
- The function evaluates key qubit cases: perfect channels achieve C0E(S)=2, complete channels achieve C0E(S)=0, and intermediate dimensions achieve C0E(S)=1.
- For a constructed family with parameter d, eα(S) ≥ d^2 and eϑ(S) ≤ d^2 imply C0E(S)=2 log d.
- Open questions include whether C0E(S)=log eϑ(S), whether theta satisfies an intersection inequality, and how the three entanglement-assisted independence numbers relate.
VII. NON-COMMUTATIVE GRAPH THEORY?
The paper develops non-commutative graph theory by adding algebraic, Hilbert-module, and bipartite structure to operator-space generalizations of confusability graphs. It relates these structures to classical graph skeletons, induced subgraphs, graph parameters, and open problems for quantum communication.
- Definitions: The Hilbert-Schmidt inner product is the default when no inner product is specified, although other inner products exist for trivial S0=C11.The paper assigns the Hilbert-Schmidt choice special status because of its importance for independence questions and its relation to matrix multiplication.
- Definitions: Non-commutative graphs are formalized as operator subspaces with an algebra S0, module structure, and a compatible S0-valued inner product.The paper defines S0 as a unital *-subalgebra contained in S, with S=S† and S0S=SS0=S.
- Classical correspondence: Classical graphs are recovered as diag-graphs, with their graph structure encoded by the skeleton G(S0 < S).The module over the diagonal algebra can also be generated by one element when each block Sjk is at most one-dimensional.
- Bipartite graphs: The framework defines non-commutative bipartite graphs as Hilbert modules Z < L(A →B) over a unital algebra S0, with Z†Z=S and inner product E(X†Y).Every completely positive trace-preserving channel yields such a bipartite graph, and all non-commutative bipartite graphs arise from some cptp channel.
- Graph operations: Complete and empty E-graphs, complements, and disjoint unions extend familiar graph operations, with ϑ and eϑ additive under disjoint unions.The complement depends on the conditional expectation E and its image S0.
- Open questions: The paper identifies open boundaries involving algorithmic complexity, random non-commutative graphs, quantum feedback, graph notions, and the choice of conditional expectation.It specifically asks whether independent-set problems remain QMA-complete for quantum or entanglement-assisted variants and whether classical feedback theory extends to quantum channels.