On quantum network coding

We study the problem of error-free multiple unicast over directed acyclic networks in a quantum setting. We provide a new information-theoretic proof of the known result that network coding does not achieve a larger quantum information flow than what can be achieved by routing for two-pair communication on the butterfly network. We then consider a k-pair multiple unicast problem and for all k >= 2 we show that there exists a family of networks where quantum network coding achieves k-times larger quantum information flow than what can be achieved by routing. Finally, we specify a graph-theoretic sufficient condition for the quantum information flow of any multiple unicast problem to be bounded by the capacity of any sparsest multicut of the network. (C) 2011 American Institute of Physics. [doi:10.1063/1.3555801]