We initiate the study of zero-error communication via quantum channels when the receiver and the sender have at their disposal a noiseless feedback channel of unlimited quantum capacity, generalizing Shannon's zero-error communication theory with instantaneous feedback. We first show that this capacity is only a function of the linear span of Choi-Kraus operators of the channel, which generalizes the bipartite equivocation graph of a classical channel, and which we dub non-commutative bipartite graph. Then, 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. We then present an upper bound on the feedback-assisted zero-error capacity, motivated by a conjecture originally made by Shannon and proved later by Ahlswede. We demonstrate that this bound to have many good properties, including being additive and given by a 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 Choi-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) 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 have to leave open the question of 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.

%B IEEE Transactions on Information Theory %V 62 %P 5260–5277 %8 09/2016 %R 10.1109/TIT.2016.2562580 %0 Journal Article %J Physical Review Letters %D 2014 %T Graph-Theoretic Approach to Quantum Correlations %A Cabello, Adán %A Severini, Simone %A Winter, Andreas %B Physical Review Letters %V 112 %P 040401 %8 1/2014 %N 4 %! Phys. Rev. Lett. %R 10.1103/PhysRevLett.112.040401 %0 Conference Paper %B 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %D 2014 %T Graph-theoretical Bounds on the Entangled Value of Non-local Games %A Chailloux, André %A Mančinska, Laura %A Scarpa, Giannicola %A Severini, Simone %E Flammia, Steven T. %E Harrow, Aram W. %B 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) %I Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik %C Dagstuhl, Germany %@ 978-3-939897-73-6 %U http://drops.dagstuhl.de/opus/volltexte/2014/4807 %R 10.4230/LIPIcs.TQC.2014.67 %0 Conference Proceedings %B Proc. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) %D 2013 %T The Quantum Entropy Cone of Stabiliser States %A Noah Linden %A Frantisek Matus %A Mary Beth Ruskai %A Winter, Andreas %E Severini, Simone %E Fernando Brandao %B Proc. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) %S LIPICS %I Leibniz International Proceedings in Informatics (LIPICS) %C Guelph, ON %V 22 %P 270 - 284 %8 06/2013 %R 10.4230/LIPIcs.TQC.2013.270 %0 Journal Article %J IEEE Transactions on Information Theory %D 2013 %T Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number %A Duan, Runyao %A Severini, Simone %A Winter, Andreas %B IEEE Transactions on Information Theory %V 59 %P 1164 - 1174 %8 02/2013 %N 2 %! IEEE Trans. Inform. Theory %R 10.1109/TIT.2012.2221677