We initiate the study of zero-error communication via quantum channels assisted by noiseless feedback link of unlimited quantum capacity, generalizing Shannon's 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. We also prove a coding theorem showing that this quantity is the entanglement-assisted capacity against an adversarially chosen channel from the set of all channels with the same Kraus span, which can also be interpreted as the feedback-assisted unambiguous capacity. The proof relies on a generalization of the "Postselection Lemma" (de Finetti reduction) [Christandl/Koenig/Renner, PRL 102:020503, 2009] that allows to reflect additional constraints, and which we believe to be of independent interest. This capacity is a relaxation of the feedback-assisted zero-error capacity; however, we do not know whether they coincide in general.
We illustrate our ideas with a number of examples, including classical-quantum channels and Weyl diagonal channels, and close with an extensive discussion of open questions.