This paper considers the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general -- indeed, it is impossible even for the simple butterfly network. As additional resource we allow free classical communication between any pair of network nodes. It is shown that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities. More precisely, it is proved that perfect quantum network coding using free classical communication is possible over a network with k source-target pairs if there exists a classical linear (or even vector-linear) coding scheme over a finite ring. Our proof is constructive in that we give explicit quantum coding operations for each network node. This paper also gives an upper bound on the number of classical communication required in terms of k , the maximal fan-in of any network node, and the size of the network.
As mentioned in Ref. @cite_19 , free classical communication essentially makes the underlying directed graph of the quantum network undirected since quantum teleportation enables one to send a quantum message to the reverse direction of a directed edge. In this context, our result gives a lower bound of the rate of quantum network coding that might not be optimal even if its corresponding classical coding is optimal in the directed graph. However, even in the classical case, network coding over an undirected graph is much less known than that over a directed one. In the multicast network, the gap between the rates by network coding and by routing is known to be at most two @cite_7 , while there is an example for which the min-cut rate bound cannot be achieved by network coding @cite_7 @cite_8 . Also notice that, in the @math -pair problem, it is conjectured that fractional routing achieves the optimal rate for any undirected graph (see for example Ref. @cite_1 ). However, this conjecture has been proved only for very few families of networks, and remains one of the main open problems in the field of network coding.
@cite_19 @cite_1 @cite_7 @cite_8
2157846543 2121205191 2160348245 2011560054
We study the problem of k-pair communication (or multiple unicast problem) of quantum information in networks of quantum channels. We consider the asymptotic rates of high fidelity quantum communication between specific sender-receiver pairs. Four scenarios of classical communication assistance (none, forward, backward, and two-way) are considered. (I) We obtain outer and inner bounds of the achievable rate regions in the most general directed networks. (II) For two particular networks (including the butterfly network), routing is proved optimal, and the free assisting classical communication can at best be used to modify the directions of quantum channels in the network. Consequently, the achievable rate regions are given by counting edge avoiding paths, and precise achievable rate regions in all four assisting scenarios can be obtained. (III) Optimality of routing can also be proved in classes of networks. The first class consists of directed unassisted networks in which (1) the receivers are information sinks, (2) the maximum distance from senders to receivers is small, and (3) a certain type of 4-cycles are absent, but without further constraints (such as on the number of communicating and intermediate parties). The second class consists of arbitrary backward-assisted networks with two sender-receiver pairs. (IV) Beyond the k-pair communication problem, observations are made on quantum multicasting and a static version of network communication related to the entanglement of assistance. An outer bound on the rate region of noise-free information networks is given. This outer bound combines properties of entropy with a strong information inequality derived from the structure of the network. This blend of information theoretic and graph theoretic arguments generates many interesting results. For example, the capacity of directed cycles is characterized. Also, a gap between the sparsity of an undirected graph and its capacity is shown. Extending this result, it is shown that multicommodity flow solutions achieve the capacity in an infinite class of undirected graphs, thereby making progress on a conjecture of Li and Li. This result is in sharp contrast to the situation with directed graphs, where a family of graphs is presented in which the gap between the capacity and the rate achievable using multicommodity flows is linear in the size of the graph. Recent research in network coding shows that, joint consideration of both coding and routing strategies may lead to higher information transmission rates than routing only. A fundamental question in the field of network coding is: how large can the throughput improvement due to network coding be? In this paper, we prove that in undirected networks, the ratio of achievable multicast throughput with network coding to that without network coding is bounded by a constant ratio of 2, i.e., network coding can at most double the throughput. This result holds for any undirected network topology, any link capacity configuration, any multicast group size, and any source information rate. This constant bound 2 represents the tightest bound that has been proved so far in general undirected settings, and is to be contrasted with the unbounded potential of network coding in improving multicast throughput in directed networks. "Eligible for the student paper award." In this work we improve on the bounds presented in Z. Li and B. Li (2004) for network coding gain in the undirected case. A tightened bound for the undirected multicast problem with three terminals is derived. An interesting result shows that with fractional routing, routing throughput can achieve at least 75 of the coding throughput. A tighter bound for the general multicast problem with any number of terminals shows that coding gain is strictly less than 2. Our derived bound depends on the number of terminals in the multicast network and approaches 2 for arbitrarily large number of terminals.