{'fraction_non_alphanumeric': 0.037215831279101615, 'fraction_numerical': 0.006984387838948234, 'mean_word_length': 4.303013798111837, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stability Analysis of a Quantum Network with Max-Weight Scheduling

We study a quantum network that distributes entangled quantum states to multiple sets of users that are connected to the network. Each user is connected to a switch of the network via a link. All the links of the network generate bipartite Bell-state entangled states in each time-slot with certain probabilities, and each end node stores one qubit of the entanglement generated by the link. To create shared entanglements for a set of users, measurement operations are performed on qubits of link-level entanglements on a set of related links, and these operations are probabilistic in nature and are successful with certain probabilities. Requests arrive to the system seeking shared entanglements for different sets of users. Each request is for the creation of shared entanglements for a fixed set of users using link-level entanglements on a fixed set of links. Requests are processed according to First-Come-First-Served service discipline and unserved requests are stored in buffers. Once a request is selected for service, measurement operations are performed on qubits of link-level entanglements on related links to create a shared entanglement. For given set of request arrival rates and link-level entanglement generation rates, we obtain necessary conditions for the stability of queues of requests. In each time-slot, the scheduler has to schedule entanglement swapping operations for different sets of users to stabilize the network. Next, we propose a Max-Weight scheduling policy and show that this policy stabilizes the network for all feasible arrival rates. We also provide numerical results to support our analysis. The analysis of a single quantum switch that creates multipartite entanglements for different sets of users is a special case of our work.

In this paper we study a quantum network serving entanglement to groups of users. Here a quantum network consists of a collection of quantum switches connected to each other through optical links. Users requesting service are connected to the network as end nodes. They have fixed paths between them (in the case of groups consisting of two users), or a fixed spanning three (in the case of groups of three or more users. Every link in the network generates maximally entangled Bellpairs between two nodes of the link and each of the two nodes stores one qubit of an entanglement of the link in memories. When enough link-level entanglement is accrued (Bell pairs at the links on a path or tree connecting a group of users), the switches perform multi-qubit measurements to provide end-to-end entanglement to the user group. If the switch only has to connect two links, it uses Bell-state measurements (BSMs) and when it must connect three or more links, it uses Greenberger-Horne-Zeilinger (GHZ) basis measurements [18].
We assume that the groups generate entanglement requests at different rates. Within each group, requests are processed according to First-Come-First-Serve service discipline and waiting requests are stored in corresponding infinite size buffers We consider a heterogeneous network, in that different types of requests arrive at different rates, links create link-level entanglements with different probabilities, and the measurement success probabilities at switches can differ across switches. Time is divided into time-slots and each link creates at most one entanglement per time-slot, which decoheres or is assumed to be lost after one timeslot [13]. Although the expectation is that eventually quantum networks will include switches with many long coherence time quantum memories, this will not be the case in the near term. For example, first generation quantum networks are likely to use controllable optical delay line buffers [5] to store single qubitsat a time. Furthermore, such models with small coherence times are useful to study quantum networks that are used for QKD applications [18,25].
In quantum networks of interest, in each time-slot we should associate links with entanglements to requests that can be processed, under the condition that each link can be used by only one request as each link can have at most one entanglement. Then, what is the capacity region, i.e., the set of arrival rates for which there exists a stationary distribution for occupancy of queues and the average waiting times of requests are finite at equilibrium under a scheduling policy? Can we design a scheduling policy that stabilizes the network for all the arrival rates that belong to the capacity region? We address these research questions in this paper. First, we will derive necessary conditions on the set of arrival rates to achieve stability of the network. We then propose a Max-Weight scheduling policy based on link-level entanglement generation success probabilities, measurement success probabilities, and the topology of the network. This policy does not depend on the request arrival rates, but does depend on request queue sizes and other network parameters. Finally, we show that our policy stabilizes the quantum network for all the arrival rates that belong to the capacity region.
Related work: Recent successful experiments on quantum information exchange [21,29] encourage us to develop efficient resource allocation algorithms and their performance analysis that can guide us to implement quantum networks at full-scale in future.
In [22], a quantum network with two users connected by a series of repeaters was studied. Their focus was to compute the expected waiting time required to create an end-to-end entanglement across a path with links, where each link creates link-level entanglement with certain probability and measurement operations are successful probabilistically. They used Markov chain theory to develop a method to compute average waiting times. However, they were able to derive exact expressions for paths with at most four segments.
The analysis of a single quantum switch that is connected to several links was investigated in [17,26,27]. In [26], the authors studied the model under the assumption that the switch's objective is to create bipartite and tripartite entanglements and it has memories with capabilities to store one qubit and two qubits per each link. They derived expressions for the capacity or the rate at which end-to-entanglements are created. They proposed policies that perform better than the policy that uses the time-division-multiplexing to create bipartite and tripartite entanglements. The analysis of a switch that generates end-to-end -partite entanglements was studied in [17], where ≥ 2. Using Lyapunov stability theory of Markov chains, they showed that the switch is stable if and only if the number links attached to the switch is greater than or equal to . Furthermore, they derived closedform expressions for the capacity, the rate at which the switch creates end-o-end entanglements. In [27], the authors studied the capacity region of a switch creating bipartite entanglements under the assumption that it has memories of finite and infinite buffer sizes to store qubits of links. In these works, end-to-end entanglements were created for every set of users of size and they did not consider in modeling of the switch the requests arriving for end-to-end entanglements from different applications. In our model, we create end-to-end entanglements for the set of users that requests ask for. Our objective is to create end-to-end entanglements for requests arriving in the system efficiently using network resources.
In [24], a Max-Weight scheduling policy was first introduced for resource allocation in communication networks and it was shown that the proposed policy stabilizes the network for all feasible arrival rates. Later, this policy was adopted for the analysis of a single classical switch in [15], where they showed that switch is stable for all feasible arrival rates under this policy. The models studied in [15,24] have static network topologies. A salient feature of quantum networks is that they are dynamic in nature, due to the fact that several operations in quantum networks are stochastic in nature. Hence, a Max-Weight scheduling policy for quantum networks must be defined by considering dynamic properties of quantum networks. In a different context, a Max-Weight scheduling policy was studied in [23] for classical networks with varying topologies. We adopt this formulation for analyzing our quantum networks.
Our Contributions: We make the following contributions: • We derive necessary conditions on the request arrival rates for achieving the stability of the network under a scheduling policy. • We propose a Max-Weight scheduling policy as a function of probability of successful creation of link-level entanglements and measurement operations, and dynamic queue sizes of requests. We prove that this policy stabilizes the network for all feasible arrival rates using Lyapunov stability theory of Markov chains. • Finally, we provide numerical results that corroborate our analysis.
The rest of the paper is organized as follows. In Section 2, we introduce the model and demonstrate challenges in analyzing our quantum networks. We then give notation and some preliminary results in Section 3, where we also define our Max-Weight scheduling policy. In Section 4, we give necessary conditions on the request arrival rates for the stability of the network and provide main results along with some proofs. We provide numerical results on the stability of quantum networks under the Max-Weight scheduling policy in Section 5. Finally, we give concluding remarks in Section 6. We give proofs of some supporting results in Appendix.

SYSTEM MODEL
We study a quantum network that creates shared entangled quantum states for several sets of users. We model a quantum network as a graph = ( , ). Here = ∪ where is the set of network nodes and is a set of user nodes. Here is the set of links connecting users and network nodes to network nodes, ⊂ × . Time is assumed to be divided into fixed length time-slots. During each time-slot, we assume each link attempts to generate a Bell-pair entanglement between the two nodes of the link and each succeeds with probability , ∈ . Each node of a link can store up to one qubit of the Bell-pair entanglement generated by the link. This qubit must be used to perform a measurement by the end of the time-slot or it is lost due to decoherence. Network nodes can perform measurements on groups of two or more successfully created neighboring link entanglements. We assume that the network provides shared entangled states for types of requests. Further, a type request seeks creation of shared entanglements for a set of users denoted by ∈ using network nodes and links in a subgraph of , T = ( , ), that connects the users in . When = { , }, T is a path within connecting and ; when | | > 2, T is a tree within connecting users in . For a type request, we assume that all involved entanglement swapping operations succeed with probability = ∈ \ where denotes the measurement success probability at network node ∈ .
During each time-slot, type requests arrive to the system according to a stationary process { ( )}, where, ( ) denotes the number of type requests arrived in time-slot and the average number of requests arrived per time-slot is denoted by . For each application, the system has a buffer with infinite memory to store unserved requests, and requests are served according to the First-Come-First-Served (FCFS) service discipline.
A single quantum switch is an example for a simple quantum network. In Figure 1, we show a quantum switch that connects to three users, where user is connected to the switch via link . There are three types of requests arriving in the system, each type of request seeks a creation of shared entanglement for a pair of users. For type requests, denotes the average number of requests arriving in each time-slot. A type request seeks an end-to-end entanglement for user pair using link level entanglements on links . From Figure 1, the set of user pairs and link pairs for different sets of requests are: In Figure 2, we show a quantum network connected to five users. This network has three switches { 1 , · · · , 3 } and seven links { 1 , · · · , 7 }, where user is connected to the network via link . Suppose that there are two types of requests with 1 = {1, 2, 3}, 2 = {4, 5}, 1 = { 1 , 2 , 3 , 6 }, and 2 = { 4 , 5 , 7 }. Now the objective is to serve requests using qubits of associated links for each type of requests.
Next we use the following simple model to illustrate the key questions that we plan to address. Consider a single switch as in Figure 1 connected to three users via three links. The objective is to create end-to-end entanglements for user pairs. Suppose that all the three links have qubits in a given time-slot. Then the key challenge is, how does the switch decide to serve requests for user pairs in order to stabilize the network? Since each link has only one qubit, out of the three user pairs, a request of only one user pair can be served in the given time-slot as each link can be pairedup with only one other link. In general, how do you select link-pairs in each time-slot such that each link is paired-up with only one other link? More importantly, the switch's goal is to schedule entanglement swappings for link-pairs in each time-slot so that the queues of requests are stable, in that the average number of stored requests for end-to-end entanglements for each link-pair does not scale-up with time. We need to design a policy that governs the switch to make scheduling decisions in each time-slot such that the switch is stable. Similarly, is there any scheduling policy that stabilizes a given quantum network?
In each time-slot, suppose that the quantum nodes provide information regarding the availability of Bell-pair entanglements of attached links and queue sizes of requests to a centralized scheduler and further assume that the scheduler maintains queues for each of the types of requests. The goal of the scheduler is to select a set of requests that can be served in the given time-slot which then provides the details of the scheduling decision to the quantum nodes. We would like to answer the following question. For the system with links and users, for given p = [ 1 , · · · , ] and q = [ 1 , · · · , ], what is the capacity region of request rates? Here, the capacity region is the set of request rates = [ 1 , · · · , ] for which there exists a scheduling policy that achieves the stability of the system.
In the next section, we define our Max-Weight scheduling policy and give some preliminary results.

NOTATION AND PRELIMINARY RESULTS
Throughout the paper we use bold-faced letters for vectors. Next, we introduce some terminology of the paper below: In each time-slot, since each link has at most one entanglement, it can be used to serve at most one request during that time-slot. We need to select a set of requests for service such that each link can be a member of at most one group of links associated with those requests. This is achieved using a notion called matching, that is defined below. (1) .
If the scheduler selects a matching = [ , 1 ≤ ≤ ] to serve requests in a time-slot, then an entanglement swapping operation is performed on qubits of links if = 1. In time-slot , based on Q( ) = ( ( )) and T( ) = ( ( )), the scheduler selects a matching according to a scheduling policy. Suppose that W( ) is the matching used in time-slot , then let (Q( ), T( ), W( )) denote the probability that a type request is successfully served conditioned on the event that the matching W( ) is used to schedule requests for service. Let { } be the indicator function of the event . Then we write Next, we write the dynamics of the process {Q( )}. Let ( ) ∈ {0, 1}} denote whether all the measurement operations required to create a shared entanglement using qubits of links in timeslot succeed or not. Here ( ) = 1 represents that all measurement operations succeed; otherwise, ( ) = 0. We denote the measurement success probability as P( ( ) = 1) = . Now denote by ( ) ∈ {0, 1} the number of requests served for application in time-slot . We write The evolution of the process {Q( )} is described using the following relation Note that the zero vector 0 is also an element of the set D. Now we obtain a necessary condition on the arrival rates that must be satisfied for the system to be stable. For type requests, since a link ∈ generates an entanglement with probability and the joint success probability of the involved measurement operations is , it follows that For a link ∈ we can write Here, we interpret as the average number of arrived type requests per time-slot, conditioned on the event that all the links except link ∈ have entanglements and measurement operations performed on qubits of links are successful. Since each link can belong to at most one group of links that can serve a request, we must have Therefore, a necessary condition is that for each link , Let Λ be defined as as Λ : Now we investigate whether there exists a scheduling policy that achieves the stability of the system for each ∈ Λ. To this end, we present the following example. EXAMPLE 1. Consider a quantum switch as in Figure 1 with three links ( = 3) that provides service to three types of applications ( = 3) requesting end-to-end bipartite entanglements using different sets of link-pairs. Assume that 1 = {1, 2}, 2 = {2, 3}, and 3 = {1, 3}. Suppose that 1 = 2 = 3 = and = 1 for 1 ≤ ≤ 3. Furthermore, let = 1 for all , 1 ≤ ≤ 3. For this model, it is easy to check that only one request can be served in each time-slot under the assumption that qubits decohere after one time-slot. Because of symmetry, each type of requests gets a service rate of 1 3 . Then if ≥ 1 3 , the switch is unstable. From the condition ∈ Λ, we obtain ≤ 1 2 . It shows that the switch is unstable if 1 3 ≤ ≤ 1 2 . Hence, there exists a ∈ Λ for which there is no scheduling policy for which the switch is stable.
From the above example, it is clear that the switch cannot serve more than one request in one time-slot. Since each link has at most one entanglement in each time-slot, a link can be pairedup with only one other link. The condition (11) is derived by considering the traffic arriving at a single link. However, the necessary condition should also be derived based on how many requests of different types can be served simultaneously in one time-slot using qubits of several links. The above example shows that the capacity region is smaller than Λ due to the fact that some sets of requests cannot be served simultaneously in one time-slot. Remark 1. In classical networking, a switch forwards requests from input ports to output ports. Let denotes the average number of arrived requests at the input port for the output port per time-slot. In each time-slot, at most one request can be forwarded from each input port to only one output port, and also, each output port receives at most one request from only one input port. Define Λ ′ as Let M ′ be the set of classical matchings defined as In [15], it was shown that if the switch selects the matching ( ) computed according to the following Max-Weight scheduling policy, then the switch is stable if lies inside Λ ′ . Furthermore, if ∉ Λ ′ , then no scheduling policy achieves the stability of the switch. We can view the quantum switch as the device with input ports and output ports, where each input port is associated with an application and each output port is associated with a link. In each time-slot, input port is either matched to output ports or not matched to any output port. Furthermore, each output port is matched to at most one input port. If the input port is matched to output ports, then it means that the switch attempts to serve a type request.
In the next section, we will derive a final necessary condition on for the stability of the system and show that the proposed Max-Weight scheduling policy achieves the stability of the system.

MAIN RESULTS
In this section, we present the main results of the paper. The process {(Q( ))}, where Q( ) = ( ( ), 1 ≤ ≤ ) is a Markov chain. Our goal is to find necessary conditions on system parameters to achieve stability of the system and also show that the Max-Weight scheduling policy achieves the stability of the system.
We begin by obtaining conditions on that are required to achieve the stability of the system. From (6), we can write Hence, we obtain Here, =1 ( ) denotes the cumulative number of type served requests up to time-slot . Similarly, =1 ( ) denotes the cumulative number of arrived requests of type up to time-slot . We can also write where ( ) defined as denotes the cumulative number of times the vector is served up to time-slot . In the following theorem, we show a relationship between and if the system is stable under a scheduling policy. Let P D be the set of probability distributions on the set D defined as where, R + denotes the set of non-negative real numbers.
where * denotes the probability with which is served in a time-slot at equilibrium.

PROOF. The proof is given in Appendix A.
The probability distribution c * is defined in terms of the stationary distribution of Q( ) and the distribution of T( ).  a u(b, a, ), (22) where Z + denotes the set of non-negative integers.
From (22), if the system is stable, then we obtain the following result.
where (b, a, ) denotes the stationary probability that the vector of queue sizes is b and the selected matching is conditioned on the event that T( ) is equal to a, and b∈Z + ,b≠0 ∈M (b, a, ) < 1 for all a.
PROOF. Since the system is stable, there exists a non-zero probability that the stationary queue sizes of requests satisfies (∞) = 0. As a result, b∈Z + ,b≠0 ∈M (b, a, ) < 1. Next, we use Corollary 1 to conditions on for achieving stability of the network. Define Λ to be PROOF. Suppose there exists a scheduling policy that stabilizes the system. From Corollary 1, using the stationary distribution of the system, we obtain (23). This is a contradiction. Hence, no policy can stabilize the system if ∉ Λ .
It is of interest to check whether Λ = Λ or not. In the next example, we present a ∈ Λ that does not belong to Λ . Hence, Λ ⊂ Λ.

Furthermore, it is not possible to partition such that the sum of coefficients in the partition is less than one. As a result, we conclude that ∉ Λ . Hence, if the requests arrive in the system such that the average number of arrived requests per time-slot is , then the switch is unstable under any scheduling policy.
Next, we establish a preliminary result before presenting the main result on the stability of the network under the Max-Weight scheduling policy. Let c · d be the inner product of two vectors c and d.
Hence, we can write We use the following bound to simplify the above equation By substituting (29) in (28), we obtain Since the first term on the right side of the above equation is negative, we obtain where = min a 1 − b∈Z + ,b≠0 ∈M (b, a, ) > 0. Suppose that * = arg max ( ). Then we can write (32) as  We establish the stability of (Q( ), ≥ 0) using a Lyapunov stability theorem [16]. We use the real valued Lyapunov function ((Q( ))) = =1 2 ( ) to show for sufficiently large Q( ) , where ′ > 0.
Furthermore, we can write Hence, we obtain The first term in the right side of the above equation can be bounded by Next we simplify the second term in the right side of (37). We can write We now obtain the following equation by substituting equations (38) and (39) in (37) Next we take expectation over T( ) in the above equation to obtain Using Lemma 1, we get This completes the proof.

NUMERICAL RESULTS
In this section, we provide numerical results on the analysis of quantum networks. We study the impact of the Max-Weight scheduling policy on queue sizes of requests. For numerical results, we assume that one type request arrives with probability and no type request arrives with probability 1 − in each time-slot. First, we consider a single switch with four links ( = 4) that aims to create bipartite entanglements for user-pairs. There are six types of requests arriving in the system serving user-pairs Hence, the switch should be unstable under any scheduling policy.
In Figures 3 and 4, we simulate the switch under the assumption that it uses our Max-Weight scheduling policy. In Figure 3, we plot the time evolution of average queue sizes of requests denoted by ( ) as a function of , where It is clear that the average queue sizes of requests increase monotonically with , imply that the Hence, the switch should be stable under our Max-Weight scheduling policy. In Figure 4, we plot the average queue sizes of requests ( ) as a function of . We observe that the average queue sizes of requests are finite even at large values of . Hence, the switch is stable. Now we simulate the quantum network shown in Figure 2. Suppose that there are two types of requests with 1 = {1, 2, 3}, 2 = {3, 4, 5}, 1 = { 1 , 2 , 3 , 6 }, and 2 = { 3 , 4 , 5 , 7 }. Note that the link 3 is used by both types of requests, hence, only one type of request can be served in each time-slot. We will compare the performance of the Max-Weight scheduling policy with that of the policy referred to as Policy 2 that chooses the type of the request in each time-slot as the type with maximum queue sizes and ties are broken uniformly at random.
For Figures 5 and 6  This example shows that we should design a scheduling policy by considering dynamic properties of quantum networks into account to have good efficiency.

CONCLUSIONS
In this paper, we studied entanglement distribution on quantum networks that aim to distribute entanglements for different sets of users. First, we investigated stability properties of quantum networks by deriving necessary conditions on request arrival rates for achieving stability of the network. By exploiting the fact that the generation of link-level entanglements and measurement operations are successful with certain probabilities, we proposed a Max-Weight scheduling policy and were able to show that the proposed policy stabilizes the network for all feasible arrival rates. A major drawback of our policy is that it has large implementation cost due to the fact that we need to search over all possible matchings to find the best matching in each time-slot. In the future, it is of interest to find other low complex scheduling policies that can stabilize the network for all feasible arrival rates. We would also like to investigate the model in which links can create multiple entanglements in each time-slot. This model will have larger capacity regions compared to the model addressed in this paper. Finally, in this paper, we assumed that each type of requests can be served by using a single set of links. We plan to extend our analysis to the setting where each type of requests can be served by several sets of links.

A PROOF OF THEOREM 1
The proof uses the existence of the stationary distribution under a scheduling policy. First, we begin with the simple case of = 1 for 1 ≤ ≤ and = 1 for 1 ≤ ≤ . In this section, we assume that every link generates an entanglement in each time-slot and the entanglement measurement operations are always successful. As a consequence, the number of served requests of type in time-slot is given by Furthermore, we have We can also write where ( ) denotes the cumulative number of times the vector is served up to time-slot . Hence, Since E [Q(1)] < ∞, we obtain The elements of the sequence { ( )} are independent and identically distributed (iid) random variables, hence, we have Since the system is assumed to be stable, we have Therefore, we get The above equation shows that the rate of departure of requests at equilibrium coincides with the arrival rate of requests . Hence, we obtain ∈D lim →∞ ( ) = .
It remains to show that the limit lim →∞ ( ) exists. By definition, we have Consider the Markov chain (Q( ), Y( )) where Y( ) is a random variable that is used to break ties if multiple matchings can be chosen according to the Max-Weight scheduling policy. Let C be the set of states of (Q( ), Y( )) for which the switch serves the matching in time-slot . Then we write Then it follows that the following limit exists due to the stability of the system where * denotes the probability with which the matching is served in a time-slot at equilibrium. Since we have We conclude that ∈D * = 1.

A.2 For
Since E [Q(1)] < ∞ and the system is stable, the equations (52), (53), and (54) are valid. As a result, we get The above equation shows that the rate of departure of requests at equilibrium coincides with the arrival rate of requests . Hence, we obtain Then it follows that since the system is stable where * denotes the probability with which the vector is served in a time-slot at equilibrium. Further, we have = ∈D * .
where * ( ) = * ∈ . We can interpret * ( ) as the stationary probability with which is served in a time-slot conditioned on the event that all the links have qubits and all the entanglement measurement operations are successful.