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:1403.3533 · Leibniz international proceedings in informatics

Quantum Linear Network Coding as One-way Quantum Computation

Niel de Beaudrap, Martin Roetteler

Published Jan 1, 2014• 13 citations
arXivHTMLPDF

Abstract

Network coding is a technique to maximize communication rates within a network, in communication protocols for simultaneous multi-party transmission of information. Linear network codes are examples of such protocols in which the local computations performed at the nodes in the network are limited to linear transformations of their input data (represented as elements of a ring, such as the integers modulo 2). The quantum linear network coding protocols of Kobayashi et al. coherently simulate classical linear network codes, using supplemental classical communication. We demonstrate that these protocols correspond in a natural way to measurement-based quantum computations with graph states over qudits having a structure directly related to the network.

DOI
10.4230/lipics.tqc.2014.217

Related papers

Constructing quantum network coding schemes from classical nonlinear protocols

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura +1 more

The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622-633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which no linear solutions exist to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.

arXiv:1012.4583•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•41 citations

Constructing quantum network coding schemes from classical nonlinear protocols

Hirotada Kobayashi, Francois Le, Gall Harumichi +1 more

The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622--633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which there are no linear solutions to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.

•Jan 1, 2011•53 citations

Quantum Network Coding and Distribution of Maximally Entangled States in Measurement-Based Quantum Computing

Cheeranjiv Pandey, Sanidhya Gupta, Rimon Ranjit Das +1 more

Classical network coding uses encoding of information over networks to achieve secure and high throughput communication with low latency. Its quantum analog, namely Quantum Network Coding (QNC) is a promising protocol to achieve quantum communication over quantum networks. In this paper, we propose a method for establishing QNC in Measurement-Based Quantum Computing (MBQC), which is a universal quantum computational model. We demonstrate that the problem of multiple unicast or multiple multicast of distinct computational basis states over a quantum network can be solved by simulating existing classical networks, with the CNOT implementation in MBQC as a basis for transmitting and encoding of states. We also show how it can be further extended to simultaneously distribute the Bell pairs and Greenberger–Horne–Zeilinger (GHZ) states required for quantum communication between distant transmitter and corresponding receiver nodes of a network.

National Conference on Communications•Feb 23, 2023•5 citations

Precoding-based protocols for entanglement assisted linear computation over a quantum many-to-one network

Ruoyu Meng, Aditya Ramamoorthy

In this work, we consider the problem of computing a linear combination over a noiseless quantum many-to-one network. There are $k$ senders, Alice$_1$, $\ldots$, Alice$_k$, and a single receiver, Bob. Each Alice$_i$ has a data vector $W_i \in \mathbb{F}^{m_i}$, where $\mathbb{F}$ is a finite field. Bob wants to compute the linear combination $Y = V_1 W_1 + V_2 W_2 + \cdots + V_k W_k \in \mathbb{F}^m$, where $V_i$ is an $m \times m_i$ matrix over $\mathbb{F}$. The senders transmit quantum states to Bob through a noiseless many-to-one quantum network, but they are not allowed to communicate with each other. The senders share entanglement among themselves, while Bob does not share this entanglement. They encode their classical information $W_i$, $i=1,\ldots,k$, into their local subsystems and transmit them to Bob so that he can recover $Y$ through a quantum measurement and subsequent post-processing. The N-Sum Box protocol proposed by Allaix et al. (2025) considers this problem under certain constraints on the linear combination and the distribution of the data vectors among the senders. We present protocols that support the computation of a more general class of linear transformations by giving the senders access to more qudits and allowing them to judiciously precode their input symbols. The communication cost of our schemes is at most that of the best-known prior results in this area and is strictly lower in certain cases. Finally, we demonstrate that the communication cost is subadditive across instances. Specifically, we identify two linear functions for which the total cost of computing them individually is strictly larger than the cost of computing them jointly.

cs.ITCross-listedarXiv:2607.13756•Jul 16, 2026•0 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

Quantum network coding for quantum repeaters

Takahiko Satoh, François Le Gall, Hiroshi Imai

This paper considers quantum network coding, which is a recent technique that enables quantum information to be sent on complex networks at higher rates than straightforward routing strategies. Kobayashi et al. have recently showed the potential of this technique by demonstrating how any classical network coding protocol gives rise to a quantum network coding protocol. They nevertheless primarily focused on an abstract model, in which quantum resources such as additional quantum registers can be freely introduced at each node. In this work, we present a protocol for quantum network coding under weaker (and more practical) assumptions: Our new protocol works even for quantum networks where adjacent nodes initially share one Einstein-Podolsky-Rosen pair but cannot add any additional quantum registers or send any quantum information. A typical example of networks satisfying this assumption is quantum repeater networks, which are promising candidates for the implementation of large-scale quantum networks. Our results thus show that quantum network coding techniques can increase the transmission rate in such quantum networks as well.

arXiv:1205.3745•Physical Review A•Sep 24, 2012•78 citations
Network coding is a technique to maximize communication rates within a network, in communication protocols for simultaneous multi-party transmission of information. Linear network codes are examples of such protocols in which the local computations performed at the nodes in the network are limited to linear transformations of their input data (represented as elements of a ring, such as the integers modulo 2). The quantum linear network coding protocols of Kobayashi et al. coherently simulate classical linear network codes, using supplemental classical communication. We demonstrate that these protocols correspond in a natural way to measurement-based quantum computations with graph states over qudits having a structure directly related to the network.
The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622-633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which no linear solutions exist to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.
The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622--633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which there are no linear solutions to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.
Classical network coding uses encoding of information over networks to achieve secure and high throughput communication with low latency. Its quantum analog, namely Quantum Network Coding (QNC) is a promising protocol to achieve quantum communication over quantum networks. In this paper, we propose a method for establishing QNC in Measurement-Based Quantum Computing (MBQC), which is a universal quantum computational model. We demonstrate that the problem of multiple unicast or multiple multicast of distinct computational basis states over a quantum network can be solved by simulating existing classical networks, with the CNOT implementation in MBQC as a basis for transmitting and encoding of states. We also show how it can be further extended to simultaneously distribute the Bell pairs and Greenberger–Horne–Zeilinger (GHZ) states required for quantum communication between distant transmitter and corresponding receiver nodes of a network.
In this work, we consider the problem of computing a linear combination over a noiseless quantum many-to-one network. There are kkk senders, Alice1_11​, …\ldots…, Alicek_kk​, and a single receiver, Bob. Each Alicei_ii​ has a data vector Wi∈FmiW_i \in \mathbb{F}^{m_i}Wi​∈Fmi​, where F\mathbb{F}F is a finite field. Bob wants to compute the linear combination Y=V1W1+V2W2+⋯+VkWk∈FmY = V_1 W_1 + V_2 W_2 + \cdots + V_k W_k \in \mathbb{F}^mY=V1​W1​+V2​W2​+⋯+Vk​Wk​∈Fm, where ViV_iVi​ is an m×mim \times m_im×mi​ matrix over F\mathbb{F}F. The senders transmit quantum states to Bob through a noiseless many-to-one quantum network, but they are not allowed to communicate with each other. The senders share entanglement among themselves, while Bob does not share this entanglement. They encode their classical information WiW_iWi​, i=1,…,ki=1,\ldots,ki=1,…,k, into their local subsystems and transmit them to Bob so that he can recover YYY through a quantum measurement and subsequent post-processing. The N-Sum Box protocol proposed by Allaix et al. (2025) considers this problem under certain constraints on the linear combination and the distribution of the data vectors among the senders. We present protocols that support the computation of a more general class of linear transformations by giving the senders access to more qudits and allowing them to judiciously precode their input symbols. The communication cost of our schemes is at most that of the best-known prior results in this area and is strictly lower in certain cases. Finally, we demonstrate that the communication cost is subadditive across instances. Specifically, we identify two linear functions for which the total cost of computing them individually is strictly larger than the cost of computing them jointly.
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.
This paper considers quantum network coding, which is a recent technique that enables quantum information to be sent on complex networks at higher rates than straightforward routing strategies. Kobayashi et al. have recently showed the potential of this technique by demonstrating how any classical network coding protocol gives rise to a quantum network coding protocol. They nevertheless primarily focused on an abstract model, in which quantum resources such as additional quantum registers can be freely introduced at each node. In this work, we present a protocol for quantum network coding under weaker (and more practical) assumptions: Our new protocol works even for quantum networks where adjacent nodes initially share one Einstein-Podolsky-Rosen pair but cannot add any additional quantum registers or send any quantum information. A typical example of networks satisfying this assumption is quantum repeater networks, which are promising candidates for the implementation of large-scale quantum networks. Our results thus show that quantum network coding techniques can increase the transmission rate in such quantum networks as well.