{'fraction_non_alphanumeric': 0.030203327171903882, 'fraction_numerical': 0.008835489833641404, 'mean_word_length': 4.469268095430651, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Teleportation Cost in Distributed Quantum Circuits

The presented work provides a procedure for optimizing the communication cost of a distributed quantum circuit (DQC) in terms of the number of qubit teleportations. Because of technology limitations which do not allow large quantum computers to work as a single processing element, distributed quantum computation is an appropriate solution to overcome this difficulty. Previous studies have applied ad-hoc solutions to distribute a quantum system for special cases and applications. In this study, a general approach is proposed to optimize the number of teleportations for a DQC consisting of two spatially separated and long-distance quantum subsystems. To this end, different configurations of locations for executing gates whose qubits are in distinct subsystems are considered and for each of these configurations, the proposed algorithm is run to find the minimum number of required teleportations. Finally, the configuration which leads to the minimum number of teleportations is reported. The proposed method can be used as an automated procedure to find the configuration with the optimal communication cost for the DQC.


I. INTRODUCTION
Quantum computation [1] is an interesting field of study with great potential to outperform classical computers in certain problems such as integer factorization [2], discrete logarithm finding, and database search [3].
Despite the theoretical advantages of quantum computations, realization of a large-scale quantum system is a real challenge [4]. It is mainly because that quantum computation technologies have limitations in the number of qubits they can process [5] and building a large-capacity quantum computer is hard [6] which makes distributed implementations of quantum technologies necessary [7].
One of the limitations of quantum implementations is due to the interactions of qubits with the environment that leads to the decoherence and when the number of qubits increases, the quantum information becomes more fragile and more susceptible to errors [8]. To overcome the mentioned problems, using distributed nodes or subsystems in a quantum system is a reasonable solution in which fewer qubits are used in each node or subsystem. Therefore, to have a large quantum M computer, one appropriate solution is to build a network of limited-capacity quantum computers which are interconnected through a quantum or classical channel and altogether can implement the behavior of the whole quantum system [9]. This structure is known as distributed quantum computer.
In order to perform a distributed quantum computation, there should be a reliable mechanism for communication between separate nodes of a distributed quantum system. Longdistance quantum communication is a technological challenge for physical realizations of quantum communication [10]. In this regard, teleportation [11] is a primitive protocol for such this communication that uses entangled qubits to distribute quantum information [12]. This protocol has been experimentally implemented in many quantum technologies such as quantum photonics [13], NMR [14], and trapped ions [15].
In teleportation, qubit states are teleported from one node to another, without physically moving them and then computations are performed locally on qubits, which is also known as teledata. There is an alternative approach, called telegate that executes gates remotely using the teleported gate approach without the need for qubits to be nearby [16]. For some applications, like some adder algorithms it has been shown that teledata outperforms telegate and also its performance is independent of the network topology [17]. In this study, teledata is considered for communication between distributed nodes.
Teleportation is a costly operation in a distributed quantum system. Moreover, according to no-cloning theorem [18], when a qubit is teleported to a destination subsystem, it can no longer be used in its own subsystem. Therefore, minimizing the number of teleportationn in a distributed quantum system is an important concern. In this study, this problem is considered and an algorithm is presented to optimize the number of teleportations for a distributed quantum system consisting of two spatially separated and long-distance quantum subsystems.
The paper is organized as follows: Section 2 explains some basic concepts and definitions of quantum computation and distributed quantum computing. Related work is presented in Section 3. Section 4 then establishes some definitions and notation needed for the proposed algorithm. Our proposed algorithm for optimal distributed quantum circuit is described in Section 5. Finally in Section 6, we conclude the paper.

II. BACKGROUND
Quantum bits or qubits are quantum analogues of classical bits. A qubit is a two-level quantum system whose state is represented by a unit vector in a two-dimensional Hilbert space, H 2 , for which an orthonormal basis, denoted by {|0 , |1 }, has been fixed. Unlike classical bits, qubits can be in a superposition of |0 and |1 which is represented as α |0 + β |1 , where α and β are complex numbers such that |α| 2 + |β| 2 = 1. If such a superposition is measured with respect to the {|0 , |1 } basis, then the classical outcome of 0 is observed with the probability of |α| 2 and the classical result of 1 is observed with the probability of |β| 2 . If 0 is obtained, the state of the system after measurement will collapse to |0 and if 1 is obtained, it will be |1 .
There are a number of models for the evolution of quantum computation. The main model to explore quantum computation is the circuit model, based on unitary evolution of qubits by networks of gates [1]. Every n-qubit quantum gate is a linear transformation represented by a unitary matrix defined on an Some useful single-qubit gates are the elements of the Pauli set: Another class of useful unitary gates on a single qubit are rotation operators around x, y and z axis with the angle α in the Bloch sphere, as shown below: Hadamard, H, and T are two other known single-qubit gates where: If U is a gate that operates on a single qubit, then controlled-U is a gate that operates on two qubits, i.e., control and target qubits, and U is applied to the target qubit if the control qubit is |1 and leaves it unchanged otherwise. For example, controlled-NOT (CNOT) gate performs the X operator on the target qubit if the control qubit is |1 . Otherwise, the target qubit remains unchanged. Figure 1 shows the circuit representation of the CNOT gate.
To realize arbitrary quantum gates, they are decomposed to a set of physically implementable gates by quantum technologies, which is called quantum logic synthesis [19], [20], [21], [22]. This set of gates typically consists of CNOT and single-qubit gates, called "basic gate" library [23] or CNOT and single-qubit rotation gates, called "elementary gate" library [24].
A quantum circuit consists of quantum gates interconnected by quantum wires carrying qubits with time flowing from left or right. The unitary matrix of the quantum circuit is evaluated by either dot product or tensor product of the unitary matrices of those quantum gates. The net effect of the gates which are applied to a same subset of qubits in series is computed by the dot product which is the same as the known matrix multiplication. The adjacent gates which act on independent subsets of qubits can be applied in parallel and their overall net effect is computed by their tensor product and defined as follows.
Let A be an m × n matrix and let B be a p × q matrix. Then A⊗B is an (mp)×(nq) matrix called the tensor product (Kronecker product) of A and B and is defined as below: where a ij shows the element in the i th column and the j th row of matrix A.
Entanglement is a quantum mechanical phenomenon that plays a key role in many of the most interesting applications of quantum computation and quantum information. A multiqubit quantum state |ψ is said to be entangled if it cannot be written as the tensor product |ψ = |φ 1 ⊗ |φ 2 of two pure states. For example, the EPR pair [1] shown below is an entangled quantum state: is an extension to the quantum circuit model. To have a distributed quantum computing system, the quantum states have to be moved between computing nodes. Teleportation is a known technique for communication between distributed nodes.
Teleportation allows us to send the state of a qubit from point A to point B by communicating only two classical bits. In this study, it is assumed that data transfer between distributed nodes in the system is performed by teleportation. Figure 2 shows the quantum circuit for a basic quantum teleportation as described in [1]. In this figure, the two top lines represent the sender's system and the bottom line is the receiver's one. The meters represent measurement, and the double lines coming out of them carry classical bits.
As stated in [11] and mathematically proved in [6], it can be concluded that teleporting a quantum state works even if that state is a mixed or an entangled state and so it can be used as communication protocol between distributed quantum systems.

III. RELATED WORK
Distributed quantum computing has been studied for more than fifteen years [6] and the first suggestions were made by Grover [25], Cleve and Buhrman [26] and later by Cirac et.al., [27]. In [25], Grover presented a distributed quantum system Quantum circuit for teleporting a qubit [1].
where there are some particles at remote locations and each one performs its computation and sends the required information to a base station when necessary. He mentioned that the issue in distributed quantum computing is how to optimally divide the problem into the different quantum computing units.
The answer to this question effects the performance of the proposed problem in this work that can be considered in the future. Grover showed that using this distributed approach, the overall computation time is faster proportional to the number of such distributed particles. In the same paper, he also presented a quantum algorithm and adapted it to distributed computation where communication is costly. Beals et.al., [28] assumed a distributed quantum computer with nodes connected according to the hypercube graph and used a few long-range qubits to emulate a quantum circuit with a reasonable overhead. They showed that an arbitrary quantum circuit can be emulated by a distributed quantum circuit with nodes connected using a hypercube graph.
Yepez [29] presented an architecture for distributed quantum computing with two types of communication which were called type I and type II. Type I quantum computer uses quantum communication between subsystems and type II quantum computer exploits classical communication between subsystems of the distributed computer. Using this classification, our distributed quantum circuit is of type I. Related to teleportation cost, Streltsov et.al., [30] posed the question of the cheapest way for distributing entanglement and provided the minimal quantum cost for sending an entangled composite state in a long distance. They showed that regarding the most general distribution protocol, the amount of entanglement sent in the total process of distributed communication cannot be larger than the total entanglement cost for sending the ancilla particle and sending back that particle.
Classical communication cost is the subject of the study in [31]. Authors conjecture that in a two-stage teleportation, each step requires a single bit of classical communication and in general, for an arbitrary N -dimensional pure state, 2log 2 N bits of classical communication is required for remote preparation which is different from the usual teleportation in which the precise state of the qubit to be prepared in the receiver is known to the sender.
Ying and Feng [6] provided some definitions of a distributed quantum computing system and defined an algebraic language to describe quantum circuits for distributed quantum computing. Van Meter et.al., [16] designed a fixed distributed quantum circuit for VBE carry-ripple adder. They evaluated the cost of the teleportation for the designed distributed system. They compared two approaches, namely teledata and telegate topologies of quantum circuits and showed that teleportation of data (the one we use in our work) is better than teleportation of gates. They also compared it to a monolithic machine and showed that as the node sizes are increased the multicomputer architecture has better performance in large problem sizes. But their distributed quantum circuit was a predesigned architecture and they didn't make any specific change in the system to reduce the number of teleportation circuits in the design.
Also in [32], authors used the teleportation communication model for implementing a distributed version of Shor's algorithm. But like the one in [33], their method for assigning logical qubits to distributed nodes is an ad-hoc method specific for implementing Shor's algorithm. In their implementation, each computing node holds n/4 qubits from each register and output of each computing node is teleported to the next computing node. So there is no optimization in the number of teleportations and also the authors did not consider the cost of returning the teleported qubits back into their own subsystems.

IV. DEFINITIONS AND NOTATIONS
In this section, we establish some assumptions and notations before proceeding with the main development of the study. First of all, we assume that there is a quantum circuit, QC as input with width W , size S, and depth D with the following definitions as stated in [34]: The width of a quantum circuit is defined as the total number of qubits in the circuit.
The size of a quantum circuit is the total number of its gates from a set of universal quantum gates.
The depth of a quantum circuit is the number of timesteps, D required for executing the circuit. In each timestep one or more gates can be executed in parallel.
It is assumed that there is an appropriate ordering of gate executions so that the number of timesteps is minimal. In each timestep, a set of gates that can be performed in parallel are executed.
Definition 1: A Distributed Quantum Circuit (DQC) consists of N limited capacity Quantum Circuits (QCs) or partitions which are located far from each other and altogether emulate the functionality of a large quantum circuit. Partitions of a DQC communicate by sending their qubits to each other using a specific quantum communication channel through teleportation.
For simplicity, in this paper it is assumed that there are just two partitions in DQC, each with the size of W/2. Without losing the generality, W is assumed to be an even number. Qubits are numbered from top to bottom from one to n in each partition, where the i th line of the circuit from top to bottom represents the i th qubit, q i .
The gates are numbered in order of their executions in the QC and g i means the i th gate which is executed according to a scheduling algorithm. For gates which can be executed in parallel, the priority of their numbering is arbitrary. The set of all gates in the circuit is represented by G.
There are three kinds of quantum gates in the DQC, namely, single-qubit, local and global CNOT gates and their definitions and representations are as follows: • A single-qubit gates is shown as gate name i (p, j).
p, indicates the index of partition to which the gate gate name i belongs and j indicates the index of the qubit the gate acts on. • A local CNOT gate is the one whose control and target qubits belong to the same partition and is shown as CNOT i (p, j c , j t ). p indicates the index of partition to which the gate CNOT i belongs. j c (j t ) indicates the index of control (target) qubit in its partition. • A global CNOT gate is the one whose control and target qubits belong to different partitions is called a global CNOT gate shown as CNOT i (p c , j c , p t , j t ). j c (j t ) indicates the index of control (target) qubit in its home partition. The partition to which each qubit q of a global CNOT gate belongs is called the home partition of q. p c (p t ) indicates the index of partition to which the control (target) of CNOT i belongs. It is supposed that local gates including single-qubit and local CNOT gates are performed in their local partitions. The total number of gates in a QC and the number of global gates are denoted by m t and m g respectively. Also a subset of G for representing the set of global gates is denoted by G d .
Conf ig-Arr, is an array with the size of m g , whose elements show the partitions each global gate is supposed to be executed. The value of '0' ('1') for the elements of this array means the corresponding gate is assumed to be executed in P 0 (P 1 ). The partition in which the gate g is supposed to be executed based on the Conf ig-Arr array is denoted by g.l.
Definition 2: In order to perform a global CNOT gate, one of its two qubits should be teleported from its home partition to another. This qubit is called a migrated qubit, as long as it is not teleported back to its home partition.
To keep load balancing of quantum subsystems, it is assumed that at each time, the number of migrated qubits is at most one.
For example, in the circuit of Figure 4, the set G is represented as: {CNOT 1 (0, 0, 1) CNOT 2 (1, 0, 0, 0) CNOT 3 (0, 0, 1, 1) H 4 (1, 1) CNOT 5 (1, 1, 0, 1) H 6 (0, 1) CNOT 7 (0, 1, 1, 1) CNOT 8 (0, 0, 1) CNOT 9 (1, 1, 0, 0)} As non-commutativity property of gates is an important concept in our algorithm, it is considered in the following. First we examine the non-commutativity of two CNOT gates. Two CNOT gates do not commute when the index of control qubit of CNOT gate is the same as the index of target qubit of other gate [35] as shown in Figure 3. As shown in this figure, the third output in circuit in the left is |b ⊕ c , while it is |a ⊕ b ⊕ c in the circuit in the right. Now the commutativity relations of two adjacent CNOT and a single-qubit gate are considered.
1) If the single-qubit gate, U is applied to the same qubit of control of the CNOT gate, they commute if: where θ ∈ [0, 2π). Examining (1), θ is obtained 0, and U is a diagonal unitary matrix as follows: Fig. 3: (a) and (b) show when the index of the control qubit of one CNOT is the same as the index of the target of the other, two CNOTs do not commute [35].
. 2) If the single-qubit gate, U is applied to the target qubit of CNOT gate they commute if that the X gate and U gate commute. X gate and a U gate commute if: Examining (2), we found that θ is either 0 or π. In the case of θ = 0, the structure of U is a unitary matrix as follows: and where θ = π, the structure of U is a unitary matrix as follows:

V. PROPOSED APPROACH
In this section, first the proposed algorithm for optimizing the teleportation cost of a given DQC is explained and then, it is performed on a simple running example.

A. The proposed algorithm
In this section, the proposed algorithm to find the optimal number of teleportations and their sequence for a given DQC is presented. The algorithm is motivated by the fact that teleportation is a costly operation and reducing the number of teleportations in a given DQC is of great importance.
We intend to start with a quantum circuit QC, composed of basic gate library, i.e., CNOT and single-qubit gates operating on 2n qubits. It is assumed that QC is already split into two partitions, P 0 and P 1 each with n qubits.
Suppose there are m g global CNOT gates in the given DQC. In general, each of these gates can be executed in either P 0 or P 1 and hence there are 2 mg different configurations for executing m g global gates. In the proposed approach, all of these configurations are considered and for each of which, the minimum number of teleportation and their corresponding sequence are analytically determined. Finally, the configuration which leads to the minimum number of teleportation is reported. This procedure is performed by Algorithms 1 and 2 as explained in the following.
Algorithm 1 is the main algorithm which receives the reported teleportation cost for each configuration from Algorithm 2 and returns the configuration with the minimum cost as output.
Algorithm 2 takes a DQC with the ordered list of gates, G, and Conf ig-Arr as inputs and returns the minimum number of teleportations and their sequence. This algorithm is first called with n t = 0. The subset of global gates, G d is also used in the algorithm for reporting the sequence of teleportations. In different steps of this algorithm, the general and the global gates which are executed are removed from G and G d , respectively. This algorithm starts from the first gate in list G of DQC. If it is a local gate, then no teleportation is needed for it and this gate is removed from G. Otherwise, the qubit is teleported to the destination and the teleportation cost (n t ) is increased by one. Furthermore, to show the sequence of teleportations, G d [0](C/T ) is reported. Based on Conf ig-Arr, C/T determines whether the control/ target qubit of G d [0] should be telepoted to the other partition.
When a qubit of a global gate, temp in algorithm, is teleported to the other partition, the whole circuit is tracked and as much as possible number of gates that can be executed without the need of teleporting back the qubit are executed. This means that the migrated qubit has been used optimally by other gates before it is teleported back to its own partition.
Three characteristics of gates that can not be executed are explained in the N on-Execute function. This function returns TRUE when any of these characteristics occurs. When there is a gate, G[i], for which N on-Execute(temp, G[i]) function returns FALSE, there are possibly some gates before G[i] which have not been executed. In this case, G[i] can be executed just in case that it can commute with all of these gates. The commutativity of gates is checked in the N on-Commute function. The mentioned functions are introduced in the following: • N on-Execute(g, g ), takes two gates, g and g as inputs.
It returns TRUE, if the migrated qubit of g should be returned to its home partition due to the three different cases mentioned below and then g can be performed. It returns FALSE otherwise. 1) g is a local gate whose one of qubits is the same as the migrated qubit of g.
2) g is a global gate with different label of g, i.e., g .l! = g.l.
3) g is a global gate and g .l = g.l, but it requires another teleportation in order to execute g .
• N on-Commute(g, g ), takes two gates, g and g as inputs. It returns TRUE, if the gates g and g do not commute and returns FALSE otherwise. According to discussions in Section IV, the non-commutativity of two gates happens in three cases: 1) The two gates are CNOTs where the index of control qubit of one of them is the same as the index of target qubit of the other.
2) One of the gates is CNOT and the other is a non-diagonal single-qubit gate that acts on the control qubit of CNOT.
3) One of the gates is CNOT and the other is a singlequbit gate which acts on the target qubit of CNOT and does not have any of the structures as explained in (1) or (2). At the end of each run of the algorithm, n t is increased by one once more because another teleportation is required to return the teleported qubit back. Then the algorithm recursively is called with the new existing gates until there is no gate in the set G and the minimum number number of teleportations (n t ) is obtained.

B. Running Example
In this section, the proposed algorithm in Section V-A is explained by a running example. This example is illustrated in Figure 4 and the proposed algorithm is applied to it. The algorithm starts by taking an already two-partite DQC as an input. This circuit consists of nine gates including two single-qubit gates, two local CNOT gates and five global CNOT gates. Since there are five global gates, the Conf ig-Arr has five elements and 2 5 = 32 different configurations. Algorithm 1 for all these configurations calls Algorithm 2 which finds the minimum number of teleportation and their sequence for that configuration. Algorithm 1 finally reports the configuration with the smallest number of teleportations. Therefore, for the given DQC this approach finds the minimum number of teleportations.
Let us consider Conf ig-Arr={0, 1, 0, 0, 1} as a sample configuration. Algorithm 2 starts with the first gate in G, i.e., CNOT 1 (0, 0, 1) which is a local gate. Therefore, it is executed in its own partition and is then removed. The next gate in this array is CNOT 2 (1, 0, 0, 0) which is a global gate and based on the first element of Conf ig-Arr, this gate is executed in P 0 . For executing this gate, qubit #0 in P 1 is teleported to P 0 , the number of teleportations, n t is increased by one and then this gate is removed. In the outer loop of Algorithm 2 (Line 15), for all other gates, they are removed from the list, if they can be executed before teleporting back this migrated qubit.
The steps for the first run of Algorithm 2 are as follows.
For each configuration of global gates of Figure 4, Table I shows the minimum number of teleportations and their corresponding sequence. In this table, the general name g for gates of DQC is used. g k (C/T ) implies that the control/target qubit of g k is teleportated to the other partition. The configuration used in the example is configuration #9 in Table I.
In this example, the minimum number of teleportations, which is 4, occurs for the configuration #24. This configuration corresponds to the Conf ig-Arr={11000} where the first and second global gates are executed in P 1 and other global gates are executed in partition P 0 .
As Table I shows, in the worst case, this example requires 10 teleportations while the optimizations of the proposed approach decrease this value to 4. Therefore, a remarkable improvement, i.e., 60% is obtained for this small circuit by the proposed approach.

VI. CONCLUSION AND FUTURE WORKS
In this study, we presented an algorithm to optimize the number of teleportations for a distributed quantum system consisting of two spatially separated and long-distance quantum subsystems. As teleportation is a costly operation in quantum computation technologies, reducing the number of such operations is very important for designing distributed quantum computers.
As future works, extending the proposed approach to the case when the number of partitions is more than two can be considered. Moreover, an algorithmic approach for the quantum circuit partitioning can be used instead of considering a preassigned partitioning for the subsystems. This step can then be followed by the proposed approach for teleportation cost optimization. Finally, the used library of gates can be extended to include three-qubit quantum gates and hence the proposed algorithm should be modified accordingly.  Figure 4.