Abstract: We study the zero-error communication via quantum channels assisted by noiseless feedback link of unlimited quantum capacity, generalizing Shannon zero-error communication theory with instantaneous feedback. This capacity depends only on the linear span of Kraus operators of the channel, which generalizes the bipartite equivocation graph of a classical channel, and which we dub "non-commutative bipartite graph". We go on to show that the feedback-assisted capacity is non-zero (allowing for a constant amount of activating noiseless communication) if and only if the non-commutative bipartite graph is non-trivial, and give a number of equivalent characterizations. This result involves a far-reaching extension of the "conclusive exclusion" of quantum states [Pusey/Barrett/Rudolph, Nat Phys 8:475, 2012]. We then present an upper bound on the feedback-assisted zero-error capacity, motivated by a conjecture originally made by Shannon and proved by Ahlswede. We demonstrate that this bound is additive and given by a nice minimax formula.

Date: 01 July 2015