2006/11/03 by Kazuo Iwama, Harumichi Nishimura, Iwama, Kazuo +5
Computer Science · Physics and Astronomy · #Cooperative Communication and Network Coding #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0611039
14pages, 4figures. Main result and lemma are improved
openalex publication_date 2006/11/03 · arxiv created 2006/12/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Network coding is often explained by using a small network model called Butterfly. In this network, there are two flow paths, s1 to t1 and s2 to t2, which share a single bottleneck channel of capacity one. So, if we consider conventional flow (of liquid, for instance), then the total amount of flow must be at most one in total, say 1/2 for each path. However, if we consider information flow, then we can send two bits (one for each path) at the same time by exploiting two side links, which are of no use for the liquid-type flow, and encoding/decoding operations at each node. This is known as network coding and has been quite popular since its introduction by Ahlswede, Cai, Li and Yeung in 2000. In QIP 2006, Hayashi et al showed that quantum network coding is possible for Butterfly, namely we can send two qubits simultaneously with keeping their fidelity strictly greater than 1/2. In this paper, we show that the result can be extended to a large class of general graphs by using a completely different approach. The underlying technique is a new cloning method called entanglement-free cloning which does not produce any entanglement at all. This seems interesting on its own and to show its possibility is an even more important purpose of this paper. Combining this new cloning with approximation of general quantum states by a small number of fixed ones, we can design a quantum network coding protocol which ``simulates'' its classical counterpart for the same graph.