Wang Xiaojun　Shi Lihui　Zhan Haitao　Xiang Ruiqing　Yu Xutao

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2State Key Laboratory of Millimeter Waves, Southeast University, Nanjing 210096, China)



Distribution algorithm of entangled particles for wireless quantum communication mesh networks

Wang Xiaojun1Shi Lihui2Zhan Haitao2Xiang Ruiqing1Yu Xutao2

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2State Key Laboratory of Millimeter Waves, Southeast University, Nanjing 210096, China)

Abstract：With ensured network connectivity in quantum channels, the issue of distributing entangled particles in wireless quantum communication mesh networks can be equivalently regarded as a problem of quantum backbone nodes selection in order to save cost and reduce complexity. A minimum spanning tree (MST)-based quantum distribution algorithm (QDMST) is presented to construct the mesh backbone network. First, the articulation points are found, and for each connected block uncovered by the articulation points, the general centers are solved. Then, both articulation points and general centers are classified as backbone nodes and an MST is formed. The quantum path between every two neighbor nodes on the MST is calculated. The nodes on these paths are also classified as backbone nodes. Simulation results validate the advantages of QDMST in the average backbone nodes number and average quantum channel distance compared to the existing random selection algorithm under multiple network scenarios.

Key words：wireless quantum communication networks; entangled particles distribution; wireless mesh networks; minimum spanning tree

Received 2015-07-09.

Biography：Wang Xiaojun (1975—), male, doctor, professor, wxj@seu.edu.cn.

Foundation item：Prospective Research Project on Future Networks of Jiangsu Province, China ( No.BY2013095-1-18).

Citation：Wang Xiaojun, Shi Lihui, Zhan Haitao, et al. Distribution algorithm of entangled particles for wireless quantum communication mesh networks[J]．Journal of Southeast University (English Edition),2015,31(4):450-456．[doi:10.3969/j.issn.1003-7985.2015.04.004]

In the traditional research of quantum physics, the study of entangled particle distribution focuses on how to produce high quality and high intensity entangled particles, and to distribute them onto two nodes with maximum distance between them[1-4]. During the research of wireless quantum networks[5-10], it is necessary to study the entangled particle distribution in terms of the entire network. Future wireless quantum networks based on entangled states may be large scale, which makes it impossible to distribute high quality entangled particles directly between the source and destination because of the long distance. Instead, the quantum path needs to be constructed with several quantum channels hop by hop via intermediate nodes. Therefore, in order to determine the nodes’ capability of producing entangled particles, investigation on transmission speed and fidelity of entangled particles in the network becomes necessary, which is usually referred to as an entangled particles distribution problem.

For wireless quantum networks, one of the essential requirements for quantum information transmission between two nodes is the existence of the quantum path. The path can be either a direct quantum channel between them or a quantum path between them via entanglement swapping. Generally in the network, the entangled particles can be produced by nodes involved in the communication or by dedicated devices.

In a quantum communication network based on the backbone mesh structure[11-13], each node has the capability of quantum teleportation. They are able to exchange routing information and quantum measurement information with traditional radio communication transceivers. The backbone of the quantum network is composed of backbone nodes with extra capability of producing and distributing entangled particles. While each non-backbone node is connected to one or more backbone nodes, and it has no capability of producing and distributing entangled particles for saving cost and reducing complexity. Thus, the entangled particles distribution issue in large-scale quantum communication networks with the mesh structure can be regarded as a quantum backbone node selection problem while ensuring the network connectivity of quantum channels.

1The Model of QDMST Algorithm

There are two kinds of channels, i.e. quantum channels and radio channels in a wireless quantum communication network. While in a traditional radio communication network, there may be no direct quantum channel between two neighbor nodes, and vice versa, as shown in Fig.1. Due to the variations with entangled particles in quantum channels, the topology of a quantum network varies much more significantly than that of a traditional radio network. Therefore, it is necessary to develop a dedicated algorithm to construct the backbone network for producing and distributing entangled particles. This paper presents a quantum distribution algorithm based on a minimum spanning tree (QDMST) to reconstruct a backbone network when network outage occurs due to topology change.

Fig.1　Wireless quantum communication network based on mesh structure

Assume thatNquantum nodes are randomly distributed within a square region, which includesMbackbone nodes andN-Mnon-backbone nodes. Each non-backbone network node acts as a source and/or a destination node, which is connected to at least one backbone node via a quantum channel and a radio channel. In the case of a fixed number of nodes, fewer nodes in the backbone network means fewer nodes capable of generating and distributing entangled particles. Thus, the algorithm focuses on minimizing the number of backbone nodes in order to reduce network cost and complexity. Also, to directly ensure high-quality, low-cost teleportation[14-16]between the two quantum nodes, the distance between them cannot be too long[16-17]where a threshold is assumed to beR. In order to ensure network connectivity and that each terminal node can transfer quantum information through the backbone network, the distance between each terminal node and at least one backbone node must be less than the effective teleportation distance threshold. The objective of the QDMST algorithm is to minimize the number of backbone nodes:

minM

(1)

s.t.M

(2)

whereriis the shortest distance between the terminal nodeiand backbone nodes, and 1≤i≤N-M.

2Implementation of QDMST Algorithm

In this paper, the mesh network architecture model is constructed based on the graph theory, and the QDMST algorithm is implemented. Assume that the square area of the model is denoted asG(V,E), whereV={v1,v2,…vN} is the quantum node set. Only if the distance between the pair of nodes is less thanR, there is an edge between them, namely the existence of a quantum channel. The edge set is defined asE={e1,e2,…,en} (n

1) First a connected graphG(V,E) is randomly generated.

2) The articulation points (if they exist) of the connected graph are labelled as the initial nodes of the backbone network.

3) If all nodes are covered by backbone nodes, directly go to Step 6).

4) Connected components composed by nodes not belonging to the backbone network are found.

5) The general center of each connected block is obtained and classified as the backbone nodes. Go to Step 3).

6) The minimum spanning tree (MST) of the backbone network is formed according to the distance weights.

7) If there is a quantum channel between any two adjacent nodes on the MST, the algorithm stops; otherwise go to Step 8).

8) The shortest path inGbetween the two nodes is found, and the corresponding nodes on the path are classified as the backbone nodes. Go to Step 6).

The steps concerned in the algorithm include four sub-algorithms: the shortest distance algorithm, the articulation point algorithm, the general center algorithm and the MST algorithm.

First, the algorithm needs to obtain the shortest path between any two nodes in the network. The success probability of single-hop teleportation will decrease exponentially as distance increases due to the loss or distortion of entangled particles caused by environmental noise in free space. Therefore, the shortest distance algorithm is the basis of the QDMST algorithm, and it is used to calculate the articulation points and general centers. The Warshall-Floyd algorithm[18]is a classic shortest distance algorithm which takes advantage of dynamic programming by using an adjacency matrix to describe the topology. Combined with the structure characteristics of the quantum network, the shortest distance algorithm used in this paper is described as follows:

Algorithm 1Shortest distance algorithm

Input: W=(wij)N×Nis the adjacency matrix of graphG;wijis the weight ofeij;k1andk2are the two nodes.

Output:Pis the shortest path betweenk1andk2, and nodes on the path are sorted by sequence order; min D is the distance of the shortest path.

D=(dij);//dijis the shortest distance fromvitovj.

for eachI,j,//Initializedij.

dij=wij,k=1;

for eachi,j//Updatedij．

ifdik+dkj

dij=dik+dkj;

ifk=Nthen

stop;

min D=D(k1,k2);

kx=k2, 0=1,P(s)=k2;

for eachi

ifD(k1,i)=D(k1,kx)-W(i,kx) then

kx=i,P(s+1)=i,s=s+1;

Ifkx=k1then

stop;

A connected graph without articulation points[19]is called a biconnected graph. Deleting any node of the biconnected graph will not damage the network connectivity. If articulation points exist, they are classified as backbone nodes to reduce the number of them and meanwhile ensure network connectivity. According to their characteristics, the steps of the algorithm to determine articulation points are presented in Algorithm 2.

Algorithm 2Articulation point determining algorithm

Input: W=(wij)N×N, the adjacency matrix of graphG;

Output: Articulation pointvi.

for eachi

//Find the adjacency matrix Aiof the subgraphG-vi.

Delete thei-th row and thej-th column from W→Ai;

do Algorithm 1//Find the shortest distance matrix Diof subgraphG-vi.

input Ai;

output Di;

//Determine whetherviis the articulation point by Di.

If there is non-zero element in Diin addition to the main diagonal element then

vi∉Articulation points;

elsevi∈Articulation points;

The initially selected backbone nodes may not be able to cover all nodes in the network. For the uncovered nodes, they are divided into various connected components and their centers are then nominated as backbone nodes for completing the coverage. The object of the QDMST is to construct a mesh quantum network with the minimum number of backbone nodes, each of which can cover more other nodes. The general center is the node that has a minimum distance to the most remote node among all nodes in the network[20]. Therefore, it is appropriate to select general centers as backbone nodes. The general center algorithm is presented as follows:

Algorithm 3General center determining algorithm

Input: W=(wij)N×N, the adjacency matrix of graphG,wherewijis the weight ofeij;

Output: The general centeri0of the graph.

//Find the shortest distance matrix of each node D(di,k), wherei,k=1,2,…,N;

do Algorithm 1

input W

output D(di,k);

//Calculate the farthest distance for each node to each edge, wherek1andk2are two nodes onej;

for eachI,j

//Find the node whose distance to the farthest node is the minimum

for eachi,j

i0←the SN of this node.

After selecting necessary backbone nodes, a connected graph is formed based on these nodes by an MST algorithm. The MST is the tree that the sum of all edge weights is minimized among all of the spanning trees of the connected graph. The Prim algorithm and Kruskal algorithm[21]are the most popular MST algorithms. The Kruskal MST algorithm used in this paper is presented as follows:

Algorithm 4Minimum spanning tree

Input: W=(wij)N×N, adjacency matrix of graphG，wherewijis the weight ofeij;

Output: Adjacency matrix of MSTb.

T=φ//Set the tree empty

for eachi//Join all nodes inT

T=T∪{vi} //Tincludes all nodes without edge

for eachi，j

doei,j(∈E) sorting by the weightswijascending

for eachei,j(∈E)

ifviandvjare not in the same connected component

T=T∪{eij}；//JoineijinT

Combine the two connected component;

b←adjacency matrix ofT

For the MST obtained by Algorithm 4, the constraint in (2) thatri

Based on the above algorithms, the proposed algorithm QDMST can be summarized as follows:

Algorithm 5QDMST algorithm

Randomly generate a connected graphG(V,E)；

F=φ//Set backbone nodes set empty

do Algorithm 2 //Set articulation nodes as initial backbone

input W(G)

output articulation nodes ofG

F=F∪{articulation nodes ofG}

Step 1for eachvi(∈V)

ifviis not covered by backbone nodes then

goto Step 2;

goto Step 3; //All nodes covered by backbone

Step 2do find {Tn}, the connected components composed by the nodes uncovered by backbone；

for eachTn//get general center of connected components into backbone

do Algorithm 3

input W(Tn)

output general center

F=F∪{general center}

goto Step 1;

Step 3do Algorithm 4//get the MST of backbone network

input W(F)

output MSTB(VB,EB)

for eachei,j(∈EB) //determine whether a quantum channel exists between any two adjacent nodes on the MST

if the quantum channel does not exist betweenviandvjthen

goto Step 4;

end //If quantum channels exist for all edge, the algorithm ends

Step 4do Algorithm 1 //Find the shortest path

input W(G)

output nodes on the shortest path

F=F∪{nodes on the shortest path} //Join nodes on shortest path in the backbone

goto Step 3;

3Performance Analysis and Simulation

To demonstrate algorithm procedures and verify their effectiveness, the steps of an exemplified QDMST algorithm are shown in Fig.2 to Fig.5. A connected graph is randomly generated within a square area of 1 000 m×1 000 m, as shown in Fig.2. The quantum teleportation distance thresholdRis 250 m, and the total number of nodesNis 30. Each black line indicates the existence of a reliable quantum channel and a radio channel between two relevant quantum nodes.

Fig.2　Randomly generated connected graph

In the case of a connected graph in Fig.2, the set of articulation points is first determined as {1,10,23,28}, which does not cover all nodes, as shown in Fig.3. The radius of the circle isR, and the small squares denote the backbone nodes. Uncovered nodes {{7,18}, {5,11,12,19,22,24,25}} are separated into two connected components. Subsequently, the general centers {7,12} of two uncovered connected components are added into the backbone nodes set as {1,7,10,12,23,28}. There are still some uncovered nodes, which require the algorithm to further calculate the general centers of the uncovered connected components, and to expand the backbone network to {1,7, 10,12,23,24,28}. Now all the nodes are covered by the backbone network. An MST is formed by these backbone nodes, as shown in Fig.4.

Fig.3　Articulation points as initial backbone nodes

Fig.4　MST formed by backbone nodes

Fig.5　Quantum mesh network obtained by QDMST

Checking the topology in Fig.2, it can be seen that on this tree there may be no quantum channel between two neighbor nodes, such as that between nodes 1 and 10.

The pair of neighbor nodes on the tree without direct quantum channel are connected using the shortest distance algorithm. The results are shown in Fig.5. The dotted lines show the final connection of the backbone network. The final backbone nodes are {1,3,6,7,10,11,12,17,23,24,28,30}, 12 in total. Each non-backbone node can be connected via one or more backbone nodes.

To evaluate the performance of the algorithm, the QDMST is compared with the random selection algorithm, by which a node is chosen to be a backbone node randomly, followed by determining whether the backbone structure mesh network can be composed in ensuring the connectivity currently. If not, one more node is randomly chosen to join the backbone node set until the backbone covers all nodes. One result of random selection is exemplified in Fig.6, where the number of backbone nodes is larger than that of the QDMST.

Fig.6　Wireless quantum communication mesh network obtained by random selection algorithm

To evaluate the performance of the above algorithm more accurately, the average backbone nodes numberABNand average quantum channel distanceAQCDare defined as two performance parameters.

(3)

(4)

The QDMST performance variations vs. node numberNand communication radius thresholdRare presented and compared with that of the random selection algorithm. 100 connected graphs are randomly generated, and the performance curves are shown in the following figures.

Fig.7 shows thatABNincreases with the increasing total node numberNand a fixed communication radiusR. The QDMST obtains more obvious gain with a greaterN. Fig.8 shows thatABNdecreases whileRincreases with a fixedN. The QDMST obtains a more pronounced performance gain with a smallerR.ABNtends to be at the same level whenRis large. It can be seen from both the two figures that the QDMST always performs better than the random selection algorithm.

Fig.7　Influences on ABN with variation of N and fixed R

Fig.8　Influences on ABN with variation of R and fixed N

Fig.9 shows thatAQCDdecreases whileNincreases with a fixedR. Fig.10 shows thatAQCDincreases whileRincreases with a fixedN. By comparing the two configures, it can be seen that communication radiusRis the dominant factor influencing the variation ofAQCD, and the performance of QDMST is superior to that of the random selection algorithm in both cases.

4Conclusion

In summary, the QDMST algorithm can generate a topology for quantum communication networks based on the backbone mesh structure while ensuring the networks connectivity. It makes the distribution of entangled particles effective with cost saving and complexity reduction. Under the same network scenarios, the QDMST algorithm outperforms the random selection algorithm in terms of the backbone nodes numbers and quantum channel distance.

Fig.9　Influences on AQCD with variation of N and fixed R

Fig.10　Influences on AQCD with variation of R and fixed N

References

[1]Lo H K, Ma X, Chen K. Decoy state quantum key distribution [J].PhysicalReviewLetters, 2005, 94(23): 230504.

[2]Chapuran T E, Toliver1 P, Peters N A, et al. Optical networking for quantum key distribution and quantum communications [J].NewJournalofPhysics, 2009, 11(10): 1884-2016.

[3]Guan J Y, Cao Z, Liu Y, et al. Experimental passive round-robin differential phase-shift quantum key distribution [J].PhysicalReviewLetters, 2015, 114(18): 180502.

[4]Ciurana A, Martin V, Martinez-Mateo J, et al. Entanglement distribution in optical networks [J].IEEEJournalofSelectedTopicsinQuantumElectronics, 2015, 21(3): 1-12.

[5]Cheng S T, Wang C Y, Tao M H. Quantum communication for wireless wide-area networks [J].IEEEJournalonSelectedAreasinCommunications, 2005, 23(7): 1424-1432.

[6]Hanzo L, Haas H, Imre S, et al. Wireless myths, realities, and futures: from 3G/4G to optical and quantum wireless [J].ProceedingsoftheIEEE, 2012, 100(Special Centennial Issue): 1853-1888.

[7]Yu X T, Xu J, Zhang Z S. Distributed wireless quantum communication networks [J].ChinesePhysicsB, 2013, 22(9): 090311.

[8]Wang K, Yu X T, Lu S L, et al. Quantum wireless multihop communication based on arbitrary Bell pairs and teleportation [J].PhysicalReviewA, 2014, 89(2): 022329.

[9]Metwally N. Entanglement routers via a wireless quantum network based on arbitrary two qubit systems [J].PhysicaScripta, 2014, 89(12): 125103.

[10]Xu T Y, Zhang Z S, X J. Distributed wireless quantum communication networks with partially entangled pairs [J].ChinesePhysicsB, 2014, 23(1): 010303.

[11]Ju H J, Rubin I. Backbone topology synthesis for multiradio mesh networks [J].IEEEJournalonSelectedAreasinCommunications, 2006, 24(11): 2116-2126.

[12]Ashraf U, Abdellatif S, Juanole G. Gateway selection in backbone wireless mesh networks [C]//2009IEEEWirelessCommunications&NetworkingConference. Budapest, Hungary, 2009: 1-6.

[13]Cao Y, Yu X, Cai Y. Wireless quantum communication networks with mesh structure [C]//2013IEEEInternationalConferenceonInformationScienceandTechnology(ICIST). Yangzhou, China, 2013: 1485-1489.

[14]Bennett C H, Brassard G, Crépeau C, et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels [J].PhysicalReviewLetters, 1993, 70(13): 1895.

[15]Bennett C H, Brassard G, Popescu S, et al. Purification of noisy entanglement and faithful teleportation via noisy channels [J].PhysicalReviewLetters, 1996, 76(5): 722.

[16]Briegel H J, Dür W, Cirac J I, et al. Quantum repeaters: the role of imperfect local operations in quantum communication [J].PhysicalReviewLetters, 1998, 81(26): 5932.

[17]Borregaard J, Kómár P, Kessler E M, et al. Long-distance entanglement distribution using individual atoms in optical cavities [J].PhysicalReviewA, 2015, 92(5): 012307.

[18]Hougardy S. The Floyd-Warshall algorithm on graphs with negative cycles [J].InformationProcessingLetters, 2010, 110(8): 279-281.

[19]Gao S X.Graphtheoryandnetworkflowtheory[M]. Beijing: Higher Education Press, 2009:53-56. (in Chinese)

[20]Wang H Y.GraphtheoryanditsMATLABimplementation[M]. Beijing: Beihang University Press, 2010: 42-46. (in Chinese)

[21]Gao S X.Graphtheoryandnetworkflowtheory[M]. Beijing: Higher Education Press, 2009:20-23. (in Chinese)

doi:10.3969/j.issn.1003-7985.2015.04.004