Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0611039

Quantum Network Coding for General Graphs

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Published Nov 3, 2006• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0611039

Related papers

Efficient Transmission of Information on the Quantum Network(New Trends in Theory of Computation and Algorithm)

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura +2 more

Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart.A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information.The question in this paper is whether or not quantum network coding is possible.Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow.Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly.In this network, there are two flow paths, $s_{1}$ to $t_{1}$ and $s_{2}$ to $t_{2}$ , which shares a single bottleneck channel of capacity one.In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck.Our results for quantum network coding include: (i) We can send any quantum state $|\psi_{1}\rangle$ from $s_{1}$ to $t_{1}$ and $|\psi_{2}\rangle$ from s2 to $t_{2}$ simultaneously with a fidelity strictly greater than 1/2.(ii) If one of $|\psi_{\mathrm{k}}\rangle$ and $|\psi_{2}\rangle$ is classical, then the fidelity can be improved to 2/3.(iii) Similar improvement is also possible if $\mathrm{C}\mathrm{b}_{\mathrm{i}}\rangle$ and $1\mathrm{C}\mathrm{b}2\rangle$ are restricted to only a finite number of (previously known) states.This allows us to design an interesting protocol which can send two classical bits from $s_{1}$ to $t_{1}$ (similarly from $s_{2}$ to $t_{2}$ ) but only one of them should be recovered.

•May 1, 2006•0 citations

Quantum network coding based on remote state preparation of arbitrary two-qubit states

Jiang Min, Shuai Zhou, MengXiao Ding

As a specific example of network coding, the butterfly network often represents the networks with bottlenecks. In this paper, we propose a typical butterfly quantum network coding scheme based on remote state preparation of arbitrary two-qubit states with the assistance of GHZ channels. Firstly, in a butterfly network, each source node simultaneously performs two appropriate projective measurements under suitable measurement basis on their own qubits. Next, their measurement results would be distributed to mid-side nodes. In the following, midside nodes perform encoded operations and send their encoded information to destination nodes. Finally, two destination nodes obtain the target state according to all information they receive with the success probability 1.

Chinese Control Conference (CCC)•Jul 1, 2017•6 citations

General Scheme for Perfect Quantum Network Coding with Free Classical Communication

Hirotada Kobayashi, François Le, Gall Harumichi +1 more

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. x1 x2 s1 ♠ s2 ♠ ❍❍❍❍ ❥ x1 x2 ✟ n1 x1 x1 ⊕ x2 x2 n2 ♠ x1 ⊕ x2✟ ❍❍❍❍ ❥ x1 ⊕ x2

•Jan 1, 2009•57 citations

Quantum network coding and the current status of its studies

Harumichi Nishimura

Considering extensive studies on network coding and quantum information theory in this century, it was just a matter of time that the study of quantum network coding was initiated. In some sense, it is rather important to ask if the amount of quantum bits communicated on a network can be reduced by allowing encoding at intermediate nodes on the network since quantum communication is much more expensive than classical communication in principle. The first result by Hayashi et al. in 2006 was basically negative for this question - quantum network coding does not give any benefit for reducing the amount of qubits sent on the butterfly network. However, this was just the first step to explore the theory of quantum network coding. After their work, it has been shown that the amount of communicated qubits can be reduced in several changes of the settings such as by allowing extra classical communication, while there has been further negative results. In this paper, we review the basic concept of quantum network coding, and report the currently known positive and negative results on quantum network coding in various settings.

International Symposium on Information Theory and its Applications•Dec 11, 2014•5 citations

Multicast quantum network coding as optimal symmetric universal cloning over a quantum network

Go Kato, Mio Murao, Masaki Owari

We study the problem of perfectly multicasting symmetric universal clones of unknown quantum states over quantum networks with free classical communication. We construct a protocol that multicasts symmetric universal clones of input states from multiple source nodes by extending the quantum network coding protocol proposed by Kobayashi et al. We further establish a sufficient condition for perfect multicast in the single-source setting. Specifically, we show that when a single copy of a $q^r$-dimensional input state is available at the source node, where $q$ is a sufficiently large prime power, perfect multicast of the corresponding symmetric universal clone is achievable using a small amount of entanglement shared among the target nodes. This result holds for quantum networks represented by an undirected graph $G$, where each edge corresponds to a noiseless $q$-dimensional quantum channel, provided that there exists an acyclic directed graph $G'$ obtained by assigning directions to the edges of $G$ such that the minimum cut of $G'$ is at least $r$.

quant-pharXiv:2608.18471•Lecture notes in electrical engineering•Aug 20, 2026•0 citations

Prior entanglement between senders enables perfect quantum network coding with modification

Masahito Hayashi

We find a protocol transmitting two quantum states crossly in the butterfly network only with prior entanglement between two senders. This protocol requires only one qubit transmission or two classical bits (cbits) transmission in each channel in the butterfly network. It is also proved that it is impossible without prior entanglement. More precisely, an upper bound of average fidelity is given in the butterfly network when prior entanglement is not allowed. The presented result concerns only the butterfly network, but our techniques can be applied to a more general graph.

arXiv:0706.0197•Physical Review A•Oct 10, 2007•138 citations
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.
Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart.A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information.The question in this paper is whether or not quantum network coding is possible.Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow.Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly.In this network, there are two flow paths, s1s_{1}s1​ to t1t_{1}t1​ and s2s_{2}s2​ to t2t_{2}t2​ , which shares a single bottleneck channel of capacity one.In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck.Our results for quantum network coding include: (i) We can send any quantum state ∣ψ1⟩|\psi_{1}\rangle∣ψ1​⟩ from s1s_{1}s1​ to t1t_{1}t1​ and ∣ψ2⟩|\psi_{2}\rangle∣ψ2​⟩ from s2 to t2t_{2}t2​ simultaneously with a fidelity strictly greater than 1/2.(ii) If one of ∣ψk⟩|\psi_{\mathrm{k}}\rangle∣ψk​⟩ and ∣ψ2⟩|\psi_{2}\rangle∣ψ2​⟩ is classical, then the fidelity can be improved to 2/3.(iii) Similar improvement is also possible if Cbi⟩\mathrm{C}\mathrm{b}_{\mathrm{i}}\rangleCbi​⟩ and 1Cb2⟩1\mathrm{C}\mathrm{b}2\rangle1Cb2⟩ are restricted to only a finite number of (previously known) states.This allows us to design an interesting protocol which can send two classical bits from s1s_{1}s1​ to t1t_{1}t1​ (similarly from s2s_{2}s2​ to t2t_{2}t2​ ) but only one of them should be recovered.
As a specific example of network coding, the butterfly network often represents the networks with bottlenecks. In this paper, we propose a typical butterfly quantum network coding scheme based on remote state preparation of arbitrary two-qubit states with the assistance of GHZ channels. Firstly, in a butterfly network, each source node simultaneously performs two appropriate projective measurements under suitable measurement basis on their own qubits. Next, their measurement results would be distributed to mid-side nodes. In the following, midside nodes perform encoded operations and send their encoded information to destination nodes. Finally, two destination nodes obtain the target state according to all information they receive with the success probability 1.
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. x1 x2 s1 ♠ s2 ♠ ❍❍❍❍ ❥ x1 x2 ✟ n1 x1 x1 ⊕ x2 x2 n2 ♠ x1 ⊕ x2✟ ❍❍❍❍ ❥ x1 ⊕ x2
Considering extensive studies on network coding and quantum information theory in this century, it was just a matter of time that the study of quantum network coding was initiated. In some sense, it is rather important to ask if the amount of quantum bits communicated on a network can be reduced by allowing encoding at intermediate nodes on the network since quantum communication is much more expensive than classical communication in principle. The first result by Hayashi et al. in 2006 was basically negative for this question - quantum network coding does not give any benefit for reducing the amount of qubits sent on the butterfly network. However, this was just the first step to explore the theory of quantum network coding. After their work, it has been shown that the amount of communicated qubits can be reduced in several changes of the settings such as by allowing extra classical communication, while there has been further negative results. In this paper, we review the basic concept of quantum network coding, and report the currently known positive and negative results on quantum network coding in various settings.
We study the problem of perfectly multicasting symmetric universal clones of unknown quantum states over quantum networks with free classical communication. We construct a protocol that multicasts symmetric universal clones of input states from multiple source nodes by extending the quantum network coding protocol proposed by Kobayashi et al. We further establish a sufficient condition for perfect multicast in the single-source setting. Specifically, we show that when a single copy of a qrq^rqr-dimensional input state is available at the source node, where qqq is a sufficiently large prime power, perfect multicast of the corresponding symmetric universal clone is achievable using a small amount of entanglement shared among the target nodes. This result holds for quantum networks represented by an undirected graph GGG, where each edge corresponds to a noiseless qqq-dimensional quantum channel, provided that there exists an acyclic directed graph G′G'G′ obtained by assigning directions to the edges of GGG such that the minimum cut of G′G'G′ is at least rrr.
We find a protocol transmitting two quantum states crossly in the butterfly network only with prior entanglement between two senders. This protocol requires only one qubit transmission or two classical bits (cbits) transmission in each channel in the butterfly network. It is also proved that it is impossible without prior entanglement. More precisely, an upper bound of average fidelity is given in the butterfly network when prior entanglement is not allowed. The presented result concerns only the butterfly network, but our techniques can be applied to a more general graph.