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:1503.07740 · IEEE Transactions on Information Theory

Network Coding for Distributed Quantum Computation Over Cluster and Butterfly Networks

Seiseki Akibue, Mio Murao

Published Aug 30, 2016• 24 citations
arXivHTMLPDF

Abstract

To apply network coding for quantum computation, we study the distributed implementation of unitary operations over all separated input and output nodes of quantum networks. We consider networks where quantum communication between nodes is restricted to sending a qubit, but classical communication is unrestricted. We analyze which N-qubit unitary operations are implementable over cluster networks by investigating transformations of a given cluster network into quantum circuits. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for classical network coding. We also analyze probabilistic implementations of unitary operations over cluster networks.

DOI
10.1109/tit.2016.2604382

Related papers

Entanglement and Causal Relation in distributed quantum computation

Seiseki Akibue

In this thesis, we investigate two different aspects of entanglement and classical communication in distributed quantum computation (DQC). In the first part, we analyze implementable computation over a given quantum network resource by introducing a new concept, quantum network coding for quantum computation. We consider a setting of networks where quantum communication for each edge of a network is restricted to sending one-qubit, but classical communication is unrestricted. Specifically, we analyze implementable $k$-qubit unitary operations over a certain class of networks, called cluster networks. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for network coding. We also obtain necessary and sufficient conditions for the probabilistic implementability of unitary operations over cluster networks. In the second part, we investigate resource tradeoffs in DQC. First, we show that entanglement required for local state discrimination can be substituted by less entanglement by increasing the rounds of classical communication. Second, we develop a new framework of deterministic joint quantum operations by using a causal relation between the outputs and inputs of the local operations without predefined causal order, called "classical communication" without predefined causal order (CC*). We show that local operations and CC* (LOCC*) is equivalent to the separable operation (SEP). This result indicates that entanglement-assisted LOCC implementing SEP can be simulated by LOCC* without entanglement. We also investigate the relationship between LOCC* and another formalism for deterministic joint quantum operations without assuming predefined causal order based on the quantum process formalism. As a result, we construct an example of non-LOCC SEP by using LOCC*.

arXiv:2202.06518•Feb 14, 2022•4 citations

Implementability of two-qubit unitary operations over the butterfly network and the ladder network with free classical communication

Seiseki Akibue, Mio Murao

We investigate distributed implementation of two-qubit unitary operations over two primitive networks, the butterfly network and the ladder network, as a first step to apply network coding for quantum computation.By classifying two-qubit unitary operations in terms of the Kraus-Cirac number, the number of non-zero parameters describing the global part of two-qubit unitary operations, we analyze which class of two-qubit unitary operations is implementable over these networks with free classical communication.For the butterfly network, we show that two classes of two-qubit unitary operations, which contain all Clifford, controlled-unitary and matchgate operations, are implementable over the network.For the ladder network, we show that two-qubit unitary operations are implementable over the network if and only if their Kraus-Cirac number do not exceed the number of the bridges of the ladder.

AIP conference proceedings•Jan 1, 2014•0 citations

Quantum computation over the butterfly network

Akihito Soeda, Yoshiyuki Kinjo, Peter S. Turner +1 more

In order to investigate distributed quantum computation under restricted network resources, we introduce a quantum computation task over the butterfly network where both quantum and classical communications are limited. We consider deterministically performing a two-qubit global unitary operation on two unknown inputs given at different nodes, with outputs at two distinct nodes. By using a particular resource setting introduced by M. Hayashi [Phys. Rev. A 76, 040301(R) (2007)], which is capable of performing a swap operation by adding two maximally entangled qubits (ebits) between the two input nodes, we show that unitary operations can be performed without adding any entanglement resource, if and only if the unitary operations are locally unitary equivalent to controlled unitary operations. Our protocol is optimal in the sense that the unitary operations cannot be implemented if we relax the specifications of any of the channels. We also construct protocols for performing controlled traceless unitary operations with a 1-ebit resource and for performing global Clifford operations with a 2-ebit resource.

arXiv:1010.4350•Physical Review A•Jul 27, 2011•18 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

Quantum Network Coding for General Graphs

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1 more

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.

arXiv:quant-ph/0611039•Nov 3, 2006•21 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
To apply network coding for quantum computation, we study the distributed implementation of unitary operations over all separated input and output nodes of quantum networks. We consider networks where quantum communication between nodes is restricted to sending a qubit, but classical communication is unrestricted. We analyze which N-qubit unitary operations are implementable over cluster networks by investigating transformations of a given cluster network into quantum circuits. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for classical network coding. We also analyze probabilistic implementations of unitary operations over cluster networks.
In this thesis, we investigate two different aspects of entanglement and classical communication in distributed quantum computation (DQC). In the first part, we analyze implementable computation over a given quantum network resource by introducing a new concept, quantum network coding for quantum computation. We consider a setting of networks where quantum communication for each edge of a network is restricted to sending one-qubit, but classical communication is unrestricted. Specifically, we analyze implementable kkk-qubit unitary operations over a certain class of networks, called cluster networks. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for network coding. We also obtain necessary and sufficient conditions for the probabilistic implementability of unitary operations over cluster networks. In the second part, we investigate resource tradeoffs in DQC. First, we show that entanglement required for local state discrimination can be substituted by less entanglement by increasing the rounds of classical communication. Second, we develop a new framework of deterministic joint quantum operations by using a causal relation between the outputs and inputs of the local operations without predefined causal order, called "classical communication" without predefined causal order (CC*). We show that local operations and CC* (LOCC*) is equivalent to the separable operation (SEP). This result indicates that entanglement-assisted LOCC implementing SEP can be simulated by LOCC* without entanglement. We also investigate the relationship between LOCC* and another formalism for deterministic joint quantum operations without assuming predefined causal order based on the quantum process formalism. As a result, we construct an example of non-LOCC SEP by using LOCC*.
We investigate distributed implementation of two-qubit unitary operations over two primitive networks, the butterfly network and the ladder network, as a first step to apply network coding for quantum computation.By classifying two-qubit unitary operations in terms of the Kraus-Cirac number, the number of non-zero parameters describing the global part of two-qubit unitary operations, we analyze which class of two-qubit unitary operations is implementable over these networks with free classical communication.For the butterfly network, we show that two classes of two-qubit unitary operations, which contain all Clifford, controlled-unitary and matchgate operations, are implementable over the network.For the ladder network, we show that two-qubit unitary operations are implementable over the network if and only if their Kraus-Cirac number do not exceed the number of the bridges of the ladder.
In order to investigate distributed quantum computation under restricted network resources, we introduce a quantum computation task over the butterfly network where both quantum and classical communications are limited. We consider deterministically performing a two-qubit global unitary operation on two unknown inputs given at different nodes, with outputs at two distinct nodes. By using a particular resource setting introduced by M. Hayashi [Phys. Rev. A 76, 040301(R) (2007)], which is capable of performing a swap operation by adding two maximally entangled qubits (ebits) between the two input nodes, we show that unitary operations can be performed without adding any entanglement resource, if and only if the unitary operations are locally unitary equivalent to controlled unitary operations. Our protocol is optimal in the sense that the unitary operations cannot be implemented if we relax the specifications of any of the channels. We also construct protocols for performing controlled traceless unitary operations with a 1-ebit resource and for performing global Clifford operations with a 2-ebit resource.
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.
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.
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.