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.

VL - 62 ER - TY - JOUR T1 - Graph-Theoretic Approach to Quantum Correlations JF - Physical Review Letters Y1 - 2014 A1 - Cabello, Adán A1 - Severini, Simone A1 - Winter, Andreas VL - 112 IS - 4 JO - Phys. Rev. Lett. ER - TY - CONF T1 - Graph-theoretical Bounds on the Entangled Value of Non-local Games T2 - 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) Y1 - 2014 A1 - Chailloux, André A1 - Mančinska, Laura A1 - Scarpa, Giannicola A1 - Severini, Simone ED - Flammia, Steven T. ED - Harrow, Aram W. JF - 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany SN - 978-3-939897-73-6 UR - http://drops.dagstuhl.de/opus/volltexte/2014/4807 ER - TY - Generic T1 - The Quantum Entropy Cone of Stabiliser States T2 - Proc. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) Y1 - 2013 A1 - Noah Linden A1 - Frantisek Matus A1 - Mary Beth Ruskai A1 - Winter, Andreas ED - Severini, Simone ED - Fernando Brandao JF - Proc. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) T3 - LIPICS PB - Leibniz International Proceedings in Informatics (LIPICS) CY - Guelph, ON VL - 22 ER - TY - JOUR T1 - Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number JF - IEEE Transactions on Information Theory Y1 - 2013 A1 - Duan, Runyao A1 - Severini, Simone A1 - Winter, Andreas VL - 59 IS - 2 JO - IEEE Trans. Inform. Theory ER -