  Network coding is often explained by using a small network model called
Butterfly. In this network, there are two flow paths, s_1 to t_1 and s_2 to
t_2, 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.
