# Elastic Entangled Pair and Qubit Resource Management in Quantum Cloud
Computing

Rakpong Kaewpuang, Minrui Xu, Dinh Thai Hoang, Dusit Niyato, Han Yu, Ruidong
Li, Zehui Xiong, and Jiawen Kang

###### Abstract

Quantum cloud computing (QCC) offers a promising approach to efficiently
provide quantum computing resources, such as quantum computers, to perform
resource-intensive tasks. Like traditional cloud computing platforms, QCC
providers can offer both reservation and on-demand plans for quantum resource
provisioning to satisfy users’ requirements. However, the fluctuations in user
demand and quantum circuit requirements are challenging for efficient resource
provisioning. Furthermore, in distributed QCC, entanglement routing is a
critical component of quantum networks that enables remote entanglement
communication between users and QCC providers. Further, maintaining
entanglement fidelity in quantum networks is challenging due to the
requirement for high-quality entanglement routing, especially when accessing
the providers over long distances. To address these challenges, we propose a
resource allocation model to provision quantum computing and networking
resources. In particular, entangled pairs, entanglement routing, qubit
resources, and circuits’ waiting time are jointly optimized to achieve minimum
total costs. We formulate the proposed model based on the two-stage stochastic
programming, which takes into account the uncertainties of fidelity and qubit
requirements, and quantum circuits’ waiting time. Furthermore, we apply the
Benders decomposition algorithm to divide the proposed model into sub-models
to be solved simultaneously. Experimental results demonstrate that our model
can achieve the optimal total costs and reduce total costs at most 49.43% in
comparison to the baseline model.

###### Index Terms:

Quantum networks, entanglement routing, entanglement purification, quantum
cloud computing, stochastic programming.

##  I Introduction

Quantum cloud computing (QCC) [1, 2, 3, 4] has the capability to address
complex simulation and optimization challenges in communication and network
systems at a large scale. By utilizing quantum bits (qubits) and employing
techniques, such as superposition, entanglement, and interference, QCC has the
great potential to surpass the classical cloud computing [25, 26] and the
existing supercomputers by accelerating computations and lowering energy
consumption. The emergence of Noisy Intermediate-Scale Quantum (NISQ)
computing has spurred AWS [3], IBM [1], and Azure [4], offering QCC that is
transforming the fields of finance, machine learning, and security. However,
with the current technologies, quantum resources, such as qubits, are limited
and costly in QCC as opposed to traditional cloud computing. The efficacy of
quantum computing is impacted not just by the quantity of qubits, but also by
the depth of the quantum circuit and the level of noise presenting at various
points within the circuit. The scale, quality, and speed of QCC are all
critical factors that determine the size and complexity of quantum computing
tasks that can be effectively addressed. In addition, these computing tasks
can be considered as random input for QCC.

Similar to the definition in classical cloud computing, QCC operators match
users of quantum cloud applications with quantum computer providers in the
cloud. In QCC, a user can request the necessary quantum computing resources
from a quantum cloud service provider, which is similar to traditional cloud
computing. During execution, the user can specify the amount of resources
required in terms of qubits and quantum circuits to the provider, depending on
the complexity of the computing task. The provider can offer users two
resource provisioning plans, namely reservation and on-demand plans. For the
reservation plans, user reserves the required quantum computing resources from
the operator based on the expected task difficulty and waiting time. Due to
the uncertainties of qubit requirements and minimum waiting time for quantum
circuits, the user can also purchase additional quantum computing resources
from the operator for the execution of the computing tasks.

Recently, as a promising approach to support QCC and distributed QCC, quantum
networks have been created to facilitate groundbreaking applications in
materials science, drug discovery, and cryptography [5, 6, 7] that go beyond
traditional networks. Quantum networks connect quantum nodes through optical
fiber links or free space [7], where the nodes generate and store quantum
information, and also transmit and receive it between each other [8, 9].
However, prior to information exchange, it is necessary for two quantum nodes
to establish an entangled connection between them. This connection allows for
the transmission of quantum information, encoded as qubits. Therefore, the
quantum source node can transmit information to the quantum destination node
using entangled pairs. When the source node and the destination node are
distant from each other, remote entanglement connections are established
according to the assigned routing. Intermediate quantum nodes, known as
quantum repeaters, connect source and destination nodes using entanglement
swapping, which involves joint Bell state measurements, to create a remote
entanglement connection [6]. Therefore, a critical challenge for constructing
quantum networks at a large scale is the efficient utilization of entangled
pairs and the identification of optimal routing strategies for managing
massive entanglement connections.

Meanwhile, maintaining Entanglement fidelity is crucial to ensure high-quality
remote entanglement connections, as the noise in the system [8] may prevent
quantum repeaters from producing entangled pairs with the desired fidelity.
Low-fidelity entangled pairs can adversely impact the quality of services
offered by quantum applications [10]. For example, when the fidelity of
entangled pairs falls below the quantum bit error rate (BER) in quantum
cryptographic protocols, it can lead to the degradation of the security of key
distribution [11]. Fortunately, the entanglement purification techniques [12,
13, 14] can improve the fidelity of entangled pairs by using additional
entangled pairs. These techniques utilize multiple entangled pairs to combine
them in various ways to increase the fidelity of the final purified entangled
pair, such as entanglement distillation, quantum error correction, and
decoherence-free subspaces. However, determining the optimal number of
additional entangled pairs required by the entanglement purification technique
to meet the uncertain requirements of fidelity values needed by quantum
applications is challenging and has been overlooked in the literature.

To overcome the challenges discussed above, in this paper, we propose an
entangled pair and qubit resource management model in QCC. We focus on
entangled pair resource allocation and fidelity-guaranteed entanglement
routing in quantum networks, together with qubit resource allocation for
quantum applications on quantum computers of the QCC providers. Specifically,
we formulate the two-stage stochastic programming model to determine the
optimal number of entangled pairs and the optimal number of qubits that can
fulfill all requests from multiple quantum source nodes (i.e., users) and
quantum destination nodes (i.e., providers). In the optimization problem, the
uncertainties of fidelity requirements, the number of qubits, and the waiting
time for quantum applications are taken into consideration. In addition, we
apply the Benders decomposition algorithm to reduce both the complexity and
execution time of the problem. The goal of the proposed model is to make
optimal decisions for quantum applications in minimizing the total costs
regarding entangled pairs, qubits, and quantum applications’ waiting time. The
main contribution of this paper can be summarized as follows:

  * •

We introduce an innovative model of a joint entangled pair and qubit resource
allocation, and entanglement routing with a fidelity guarantee under
uncertainties related to fidelity requirements, qubit requirements, and
quantum applications’ waiting time in QCC. In addition, we introduce the
dynamic entanglement purification algorithm to enhance the fidelity value at a
link between two quantum nodes.

  * •

We formulate the two-stage stochastic programming (SP) model to determine the
optimal allocation of entangled pairs and qubit resources, as well as the
fidelity-guaranteed entanglement routing and minimum waiting time of quantum
applications in QCC. In the proposed model, both the entangled pair and qubit
resource allocation and the fidelity-guaranteed entanglement routing are
calculated at the first stage using statistical information and then refined
in the second stage with actual realization.

  * •

We apply the Benders decomposition algorithm to divide the proposed model into
smaller models which can be solved concurrently.

  * •

To assess the effectiveness of our proposed model, we conduct extensive
experiments using real-world network topology. We demonstrate the superiority
of our proposed model by conducting experiments on the circuit demands of
quantum Fourier transform (QFT) within practical quantum computing programming
environments. In addition, we compare the outcomes of our proposed model to
those of benchmark models to demonstrate its superior performance.

The remainder of this paper is organized as follows. Section II reviews
related work. Section III describes the system model, network model, and the
case study of quantum Fourier transform. Section IV presents the proposed
stochastic programming model in QCC. Section V further elaborates the Benders
decomposition algorithm. Section VI shows the performance evaluation results.
Section VII concludes the paper.

##  II Related Work

###  II-A Quantum Networks

In [8], the authors proposed two algorithms of fidelity-guaranteed
entanglement routing for quantum networks to ensure the fidelity of the
entangled state between source-destination (S-D) pairs. The first algorithm
(called Q-PATH) was proposed to achieve the optimal routing path and the
minimum cost of the entangled pair while meeting the requirement of a single
S-D pair. To reduce the computational complexity of Q-PATH, the second
algorithm (called Q-LEAP) was introduced to obtain a satisfactory routing path
with minimum fidelity degradation. In addition, the entanglement routing
approach based on the greedy algorithm was proposed for S-D pairs to minimize
the routing path and the number of entangled pairs. Similarly, in [6], the
authors introduced a general routing scheme for generating entanglements on a
quantum lattice network with limited quantum resources, specifically the
quantity of quantum memories in each node. The objective of this scheme was to
allocate quantum resources effectively to meet the requests on entanglement
generations and the desired fidelity thresholds of entanglements.

In [15], the authors proposed an efficient linear programming model to
maximize the entanglement distribution rate between multiple S-D pairs in a
quantum network, while maintaining the desired end-to-end fidelity. Although
this problem was similar to the one addressed in [8], the purification process
was not considered in [15]. In [16], the authors proposed a novel redundant
entanglement provisioning and selection (REPS) scheme to maximize throughput
for multiple S-D pairs in a multi-hop quantum network. REPS was designed to
support multiple entanglement routing and cope with entanglement generation
failures. In [17], the authors presented a dynamic adaptive routing scheme to
handle the potential failure of quantum memories in quantum nodes in the
quantum network. The primary goal of this approach was to determine the
shortest node-disjoint replacement paths in the network of the quantum
Internet and minimize the lost entangled contacts. However, in the event of
quantum memory failures, replacement paths were implemented to temporarily
establish entangled connections and ensure uninterrupted network transmission.
In [18], the author introduced the joint routing protocol design and route
metric table for quantum networks with the objective of identifying the path
with the highest possible end-to-end entanglement rate between the S-D pairs.
The authors of [19] applied graph theoretic tools, specifically graph states,
to minimize the quantity of required measurements and develop a routing
approach for quantum communication between the S-D nodes.

###  II-B Quantum Cloud Computing

In the literature, several studies have proposed resource management schemes
for quantum computing. For example, in [20], a two-stage stochastic
programming approach was used to obtain the minimum deployment cost for
quantum resources while accounting for uncertainties in computational works,
quantum computer availability and computing power, and fidelity of entangled
qubits. Another study, [21], focused on analyzing the computation time of
works and resource utilization in IBM quantum cloud systems. They analyzed
waiting times, computation time of quantum machines and circuits, and machine
utilization. In [22], the authors introduced an optimized adaptive job
scheduling approach for IBM quantum cloud systems, which reduced waiting times
and improved fidelity. Quantum resource scheme for distributed quantum
computing was introduced in [23]. The objective of the scheme was to compute
traffic flows for all paths of applications in advance, and then allocate
resources (e.g., gross rates) to applications by using the round-robin
strategy. In [24], the authors proposed a stochastic quantum resource
management scheme for QCC systems, where the allocation of qubit resources and
minimum waiting time for quantum circuits were jointly calculated to minimize
the total cost of quantum circuits while accounting for uncertainties in the
required qubits and minimum waiting time.

However, the existing work fails to address the challenge of simultaneously
optimizing the allocation of entangled pairs, the routing of entanglement with
guaranteed fidelity, and the allocation of qubit resources for quantum
circuits in QCC. Moreover, current approaches overlook the uncertainties
associated with fidelity requirements, the number of required qubits, and the
waiting time for quantum circuits, which can significantly impact the overall
cost of quantum circuits in QCC.

##  III System Model

We first introduce the QCC environment, the quantum network, and the
relationship among quantum components. Then, we describe the components and
entanglement operations in a quantum network. Finally, we present the QFT
circuit, which is the case study for the computing application.

Figure 1: The QCC environment.

We consider the QCC environment illustrated in Fig. 1. The system model
consists of users, QCC providers, quantum computers, a quantum network, and a
quantum resource operator. Users possess quantum circuits that they want to
execute on the quantum computers provided by QCC providers. Users request
fidelity requirements (i.e., quality of entanglement qubits), a number of
qubits for executing quantum circuits, and a waiting time for quantum circuits
to be completed. QCC providers provide quantum computing resources, such as
qubits in quantum computers, to users.

We consider fidelity requirements, the number of qubits, and the waiting time
for quantum circuits as uncertain demands. The fidelity requirement, the
number of qubits, and the waiting time for quantum circuit $c$ are denoted by
$\tilde{\theta_{c}}$, $\tilde{\beta_{c}}$ and $\tilde{\alpha_{c}}$,
respectively. QCC providers offer both reservation and on-demand plans to
users for quantum computing resource provision, which are similar to the
pricing plans used in conventional cloud computing [25, 26]. The cost of the
on-demand plan is practically higher than that of the reservation plan. Three
phases [25, 26] are introduced to provision computing resources: reservation,
utilization, and on-demand. During the reservation phase, computing resources
are allocated to users without information about their specific requirements,
and then the reserved computing resources are used during the utilization
phase. However, if the reserved computing resources are insufficient, the
computing resources during the on-demand phase are allocated for satisfying
the remaining requirements. From users’ perspectives, quantum circuits are
successfully executed as fast as possible. Therefore, for the specific waiting
time, the QCC providers will incur a penalty cost of over-waiting time if the
circuits cannot be completed in the specified waiting time.

For the quantum network, the entangled pair resource allocation and
entanglement routing with fidelity guarantee are crucial to ensure the
fidelity requirements of users for quantum applications, specifically quantum
circuits. In Fig. 1, quantum nodes are interconnected in the network through
optical links and have the capability to create, exchange, store, and process
quantum information [8, 9], as depicted in Figs. 2(a) and (b). Figures 2(a)
and (b) illustrate the process of transmitting information from a quantum
source node to a quantum destination node in the quantum network. To create
the entanglement connection between distant quantum source and destination
nodes, entangled pairs of intermediate quantum nodes are generated. Quantum
repeaters, which are intermediate quantum nodes, perform entanglement swapping
to create long-distance entanglement connections between source and
destination nodes. Taking Fig. 2(b) as an example, when source 2 transmits one
qubit (information) to destination 2, quantum repeater entangles with both
nodes and performs entanglement swapping to establish a connection between
them to achieve such transmission. The quantum network is represented by a
graph [19, 18, 17], consisting of quantum nodes and edges. Sets of quantum
nodes and edges (links) are defined as $\mathcal{N}$ and $\mathcal{L}$,
respectively. Each quantum node has limited quantum memories and a restricted
number of entangled pairs. To ensure the fidelity of information transmission,
entanglement purification will function on the specific nodes to meet the
fidelity requirement and the fidelity threshold. The entanglement purification
operation utilizes the entangled pairs to improve the fidelity values on
edges. The fidelity value on the same edge is the same, while the fidelity
value on different edges is likely different [6].

(a)

(b)

Figure 2: (a) One qubit is sent by short-distance quantum teleportation, (b)
One qubit is sent via entanglement swapping by long-distance quantum
teleportation, and (c) The interactions of the quantum resource operator,
quantum network, and QCC providers.

To achieve the lowest possible cost associated with entangled pair resources,
guaranteed-fidelity entanglement routings, qubit computing resources, and the
penalty cost of waiting too long while meeting uncertainties of fidelity and
user requirements, the quantum resource operator is designed to provide the
optimal entangled pair resources and routings in QCC. In addition, the
operator efficiently provisions the quantity of qubit computing resources and
the minimum waiting time for quantum circuits. The quantum resource operator
is formulated using the two-stage SP.

Figure 2(c) illustrates the sequence of interactions among the quantum
resource operator, quantum network, and QCC providers. In the operator, the
entangled pair resource allocation assigns the entanglement routing that meets
users’ fidelity requirements and provides the number of entangled pairs. The
qubit resource allocation provides the quantity of quantum computing
components, e.g., qubits and quantum gates, that satisfy users’ qubit
requirements. These quantum computing resources, e.g., qubits, are related to
the quantum computing application provisioning of QCC providers. In the
quantum network, quantum nodes are selected and utilized to establish
connections from source nodes (i.e., users) to destination nodes (i.e.,
providers) with the assigned entanglement routing and qubits. For providers,
the provider and its quantum computers are allocated according to the assigned
qubits. If quantum computing takes longer than the expected execution time to
run the quantum circuit, the provider has to pay a penalty cost for the excess
waiting time. Notification is then sent to the operator through the network.
If the entangled pairs and qubits are insufficient, the entangled pair and
qubit resource allocation are recalculated. Otherwise, the entangled pair and
qubit resource allocation stop.

###  III-A Network Model

The components of the quantum network are quantum node, quantum source,
quantum destination, quantum repeater, and quantum channel.

####  III-A1 Quantum node, quantum source, quantum destination, and quantum
repeater

The quantum node performs various functions such as generating and processing
quantum information, establishing quantum networks, and supporting quantum
applications [9]. It also contains a quantum repeater function, which involves
entanglement generation, purification, and swapping [8]. The quantum node is
often referred to as the quantum repeater. In quantum networks, quantum nodes
have limited computing and storage capacities, and are connected via classical
networks [8]. The quantum nodes are controlled by the network controller that
has all information about the network, e.g., network topology and available
resources. A quantum source node establishes an entanglement connection with a
quantum destination node based on the requirements of the quantum application.

####  III-A2 Quantum channel

The quantum channel is established between adjacent quantum nodes to transmit
qubit information via optical fibers [8, 9] or free space [29]. Each channel
shares entangled pairs of adjacent quantum nodes, and its capacity is
determined by the quantity of entangled pairs generated through the
entanglement generation process (e.g., nitrogen-vacancy centers [27]). The
fidelity of the entangled pair is calculated using a deterministic equation
without noise [27], [28].

The entanglement routing process consists of three steps. Firstly, entangled
pairs are generated between quantum source and destination nodes, and adjacent
nodes connecting with the quantum channel. Then, the routing and entangled
pair resources are allocated by the network controller in the network,
respectively. Finally, the corresponding quantum nodes operate entanglement
purification to enhance the fidelity of the entangled pairs and meet
applications’ requirements, which are instructed by the network controller.

For multi-hop entanglement connections, entanglement swapping is used to
establish remote-distance entanglement. Entanglement generation, swapping, and
purification are crucial for establishing entanglement connections in quantum
networks.

####  III-A3  Entanglement generation and distribution

To create entangled pairs for two quantum nodes, a heralding station, such as
nitrogen-vacancy centers in diamond [30], is used to perform the physical
entanglement generation over optical fibers. The generated entangled pairs are
distributed and stored in the memories of two quantum nodes as resources for
entanglement communication and qubit transmission.

####  III-A4 Entanglement swapping

Entanglement swapping is employed to establish remote entanglement connections
according to the routing when the quantum source node and quantum destination
node are located far apart. By repeating the swapping operations, a multi-hop
entanglement connection along the path of repeaters containing entangled pairs
is established.

Figure 3: The example of three-round purification operations to improve a
fidelity value.

####  III-A5 Entanglement purification

Entanglement purification is applied to enhance the fidelity of a Bell pair by
merging two lower-fidelity Bell pairs into a higher-fidelity Bell pair, which
are implemented by using a polarizing beam splitter [14] or C-NOT (controlled-
NOT) gates. The entanglement purification operation [8] yields an improved
fidelity presented as follows:

$\displaystyle\mathbf{F}^{\mathrm{ep}}(b_{1},b_{2})=\frac{b_{1}b_{2}}{b_{1}b_{2}+(1-b_{1})(1-b_{2})}.$
(1)

$b_{1}$ and $b_{2}$ are the measured fidelity of two Bell pairs. In this
paper, we propose an entanglement purification algorithm to dynamically
calculate the operation above. In the proposed algorithm, each round of the
operation applies an extra entangled pair [13] to improve the pair’s fidelity.
For instance, by implementing three rounds of entanglement purification
operations with utilization of entangled pairs, the fidelity can improve from
0.79 to 0.995 as shown in Fig. 3. The entanglement purification algorithm is
presented in Algorithm 1.

Algorithm 1 Entanglement purification $\mathbf{F}^{\mathrm{dep}}(\;\cdot\;)$

1: Input: $y^{\mathrm{eep}}_{i,n,r,\psi}$ and $y^{\mathrm{oep}}_{i,n,r,\psi}$

2: Output: The enhanced fidelity ($ef$)

3: $M^{\mathrm{ep}}$ = maximum number of entangled pairs

4: $ef$ = 0

5: for $pr$ = $1$ to $M^{\mathrm{ep}}-1$ do

6: if $pr$ == 1 then

7: $b_{1}$ = the first pair’s fidelity

8: $b_{2}$ = the second pair’s fidelity

9: $ef=\mathbf{F}^{\mathrm{ep}}(b_{1},b_{2})$

10: else

11: $ef$ = $ef$ of $pr-1$

12: $b_{2}$ = the next pair’s fidelity

13: $ef=\mathbf{F}^{\mathrm{ep}}(ef,b_{2})$

14: end if

15: $pr=pr+1$

16: end for

###  III-B Computing Model: The Case Study of QFT Circuit

Next, we present an introduction to QFT, one of the most commonly used quantum
algorithms with numerous applications in signal processing and statistical
analysis. We offer a concise introduction to QFT, encompassing the necessary
quantum gates and circuits needed for its implementation. Our goal is to
indicate that different QFT settings demand varying numbers of qubits and
computational time, both of which are essential for our proposed QCC. We
mention that our proposed approach for quantum resource allocation is
versatile and can be utilized in other quantum algorithms.

####  III-B1 Fundamental concept of QFT

The QFT is a quantum transformation that applies the discrete Fourier
transform to the amplitudes of a wave function [31, 33, 34]. This
transformation generates a quantum state that is similar to the result of the
discrete Fourier transform. Mathematically, the mapping of quantum state
$\ket{U}$ to quantum state $\ket{V}$ in QFT is expressed as follows:

$\displaystyle\ket{U}=\sum_{h=0}^{M-1}u_{h}\ket{h}\mapsto\ket{V}=\sum_{h^{\prime}=0}^{M-1}v_{h^{\prime}}\ket{h^{\prime}}.$
(2)

The amplitude $v_{h^{\prime}}$ in QFT represents the discrete Fourier
transform of the amplitudes $u_{h}$. QFT can transform a quantum state between
the computational basis and the Fourier basis by utilizing quantum gates. The
QFT’s transformation between the states in the Fourier basis and computational
basis is expressed mathematically in Eq. (3) as

$\displaystyle\ket{\tilde{u}}=\frac{1}{\sqrt{M}}\sum_{v_{1}=0}^{1}\dots\sum_{v_{l}=0}^{1}\Pi_{k=1}^{l}e^{2\pi
i\frac{uv_{k}}{2^{k}}}\ket{v_{1},v_{2},\dots,v_{l}}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$
$\displaystyle\quad\quad\quad\quad\quad=\frac{1}{\sqrt{M}}(\ket{0}+e^{(2\pi
iu)/2^{1}}\ket{1})\otimes(\ket{0}+e^{(2\pi
iu)/2^{2}}\ket{1})\otimes\dots\otimes(\ket{0}+e^{(2\pi iu)/2^{l}}\ket{1}),$
(3)

where $\tilde{u}$ and $v$ represent the quantum states in the Fourier basis
and the computational basis, respectively, and $l$ denotes the number of
qubits and $M$ is defined as $2^{l}$. The symbol $\otimes$ indicates the
tensor product operation between qubits. For instance,
$\ket{1}\otimes\ket{1}\otimes\ket{1}\otimes\ket{1}=\ket{1111}=\ket{15}$. In
order to provide an illustration, we assume $l=4$ and $M=2^{4}$, and suppose
the quantum state $\ket{\tilde{u}}$ is represented by $\ket{\tilde{15}}$
(i.e., $\ket{1111}$). Thus, in this case, the QFT can be expressed in Eq.(4).
The graphical representation of the QFT for $\ket{\tilde{15}}$ with 4 qubits,
which maps between the computational basis and the Fourier basis, is depicted
in Fig. 4(a).

$\displaystyle\ket{\tilde{15}}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{16}}(\ket{0}+e^{(2\pi
i15)/2}\ket{1})\otimes(\ket{0}+e^{(2\pi
i15)/4}\ket{1})\otimes(\ket{0}+e^{(2\pi i15)/8}\ket{1})$ (4)
$\displaystyle\otimes(\ket{0}+e^{(2\pi i15)/16}\ket{1}).$

(a) QFT mapping.

(b)

Figure 4: (a) QFT mapping with 4 qubits, (b) 4-qubit circuit of QFT, and (c)
5-qubit quantum circuit of QFT.

####  III-B2 QFT circuits by Qiskit

In Fig. 4(b), we present two quantum circuits that implement QFT using 4 and 5
qubits. These circuits are created and visualized using Qiskit [31]. The
circuits consist of qubits (i.e., $q_{0}$, $q_{1}$, $\dots$, $q_{l}$) and use
several types of quantum gates: single-qubit Hadamard gate (a blue square with
$\mathbf{H}$), two-qubit controlled rotation gate (a purple line), and SWAP
gate (a blue line). For instance, in Fig. 4(b), there is a quantum circuit
that operates on 4 qubits ($q_{0}$ to $q_{3}$). The 4-qubit circuit performs a
series of operations as follows. First, the $q_{3}$ qubit undergoes an
$\mathbf{H}$-gate operation. Then, two $\mathbf{CROT}$-gates are used from
$q_{3}$ to $q_{0}$, $q_{1}$ to $q_{3}$, and $q_{2}$ to $q_{3}$. Next, the
$q_{2}$ qubit undergoes an $\mathbf{H}$-gate operation, followed by
$\mathbf{CROT}$-gates from $q_{2}$ to $q_{0}$ and from $q_{1}$ to $q_{2}$. The
$q_{1}$ qubit then undergoes an $\mathbf{H}$-gate operation, followed by a
$\mathbf{CROT}$-gate from $q_{0}$ to $q_{1}$. Finally, the $q_{0}$ qubit
undergoes an $\mathbf{H}$-gate operation, and SWAP gates apply for $q_{1}$ and
$q_{2}$, and $q_{0}$ and $q_{3}$.

Referring to Fig. 4(b), it can be observed that as the number of qubits in a
quantum circuit implementing QFT increases when the depth of the circuit and
the number of quantum gates are used, resulting in increased computational
time. This implies that the computational time required to execute QFT is
directly proportional to the number of qubits and quantum gates involved, as
described by Eq. (3) and illustrated in Fig. 4(b).

TABLE I: List of key notations for the SP model.

Notations | Definitions
---|---
${\mathcal{N}}$ | Set of all quantum nodes in the QCC
${\mathcal{O}}_{n}$ |  Set of outgoing links from node $n\in{\mathcal{N}}$
${\mathcal{I}}_{n}$ |  Set of incoming links to node $n\in{\mathcal{N}}$
${\mathcal{R}}$ | Set of quantum requests
$\mathcal{S}^{\mathrm{qc}}$ |  Set of quantum circuits, $\mathcal{S}^{\mathrm{qc}}=\\{1,\dots,c,\dots,C\\}$
$\mathcal{S}^{\mathrm{qp}}$ |  Set of QCC providers, $\mathcal{S}^{\mathrm{qp}}=\\{1,\dots,\rho,\dots,P\\}$
$\mathcal{S}^{\mathrm{qm}}_{\rho}$ |  Set of quantum computers in quantum provider $\rho$, $\mathcal{S}^{\mathrm{qm}}_{\rho}=\\{1,\dots,m,\dots,M\\}$
$P^{\mathrm{wt}}_{c,\rho}$ |  Penalty cost of over-waiting time of circuit $c$ in provider $\rho$
$F^{\mathrm{fts}}_{i,n}$ | Fidelity threshold
$R^{\mathrm{ep}}_{n,r}$ |  Reservation cost of entangled pair of node $n$
$U^{\mathrm{ep}}_{n,r}$ |  Utilized cost of entangled pair of node $n$
$O^{\mathrm{ep}}_{n,r}$ |  On-demand cost of entangled pair of node $n$
$R^{\mathrm{cq}}_{c,\rho}$ |  Reservation cost of qubit charged by provider $\rho$
$U^{\mathrm{cq}}_{c,\rho}$ |  Utilized cost of qubit charged by provider $\rho$
$O^{\mathrm{cq}}_{c,\rho}$ |  On-demand cost of qubit for circuit $c$ charged by provider $\rho$
$w_{i,j,r}$ |  Binary variable that determines whether request $r\in\mathcal{R}$ will utilize the link
|  between nodes $i$ and $j$ as part of its route or not
$y^{\mathrm{rep}}_{i,j,r}$ | Decision variable that represents the number of entangled pairs between
|  nodes $i$ and $j$ in the reservation phase
$y^{\mathrm{eep}}_{i,j,r,\psi}$ | Decision variable that represents the number of entangled pairs between
|  nodes $i$ and $j$ under scenario $\psi$ in the utilization phase
$y^{\mathrm{oep}}_{i,j,r,\psi}$ | Decision variable that represents the number of entangled pairs between
|  nodes $i$ and $j$ under scenario $\psi$ in the on-demand phase
$x^{\mathrm{rqt}}_{c,\rho,m,r}$ |  Non-negative integer variable that represents the number of qubits for circuit $c$ of
|  request $r$ executing on computer $m$ of provider $\rho$ in the reservation
phase
$x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}$ |  Non-negative integer variable that represents the number of qubits used by circuit $c$ of
|  request $r$ executing on computer $m$ of provider $\rho$ under scenario
$\psi$ in the utilization phase
$x^{\mathrm{oqt}}_{c,\rho,r,\psi}$ |  Non-negative integer variable that represents the number of qubits used by circuit $c$ of
|  request $r$ in provider $\rho$ under scenario $\psi$ in the on-demand phase
$y^{\mathrm{owt}}_{c,\rho,m,r,\psi}$ |  Positive real variable that represents the over-waiting time for circuit $c$ of request $r$
|  executing on computer $m$ in provider $\rho$ under scenario $\psi$

##  IV Entangled Pair and Qubit Resource Allocation Formulation

In this section, we first introduce the sets, constants, and decision
variables of the SP model. Next, we present the entangled pair and qubit
resource allocation based on the two-stage SP [35], and provide the
deterministic equivalent formulation for solving the SP model.

###  IV-A Model Description

The sets, constants, and decision variables of the SP model are described in
Table I. We consider fidelity requirements, the number of qubits, and the
expected execution time as uncertain parameters in the SP model. Let
$\tilde{\psi}$ denote the composite random variable representing the
requirements, which is expressed as follows:
$\tilde{\psi}=\\{(\tilde{\delta}_{r,c},\tilde{\beta}_{r,c},\tilde{\alpha}_{r,c})|\tilde{\delta}_{r,c}\in\mathcal{F}_{r,c},\tilde{\beta}_{r,c}\in\mathcal{Q}_{r,c},\tilde{\alpha}_{r,c}\in\mathcal{E}_{r,c}\\}.$,
where $\tilde{\delta}_{r,c},\tilde{\beta}_{r,c}$, and $\tilde{\alpha}_{r,c}$
are the random variables of fidelity value for circuit $c$ of request $r$,
number of qubits required by circuit $c$ of request $r$, and expected
execution time of circuit $c$ of request $r$, respectively.

###  IV-B Stochastic Programming Formulation

Our proposal is the two-stage SP model, which aims to provide entangled pair
resources, ensure fidelity entanglement routing, and allocate qubit resources
for running quantum circuits in the QCC, which is expressed as follows:

$\displaystyle\min_{w_{i,n,r},y^{\mathrm{rep}}_{i,n,r},x^{\mathrm{rqt}}_{c,\rho,m,r}}$
$\displaystyle\sum_{r\in{\mathcal{R}}}\Big{(}\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}((E^{\mathrm{cc}}_{n}+S^{\mathrm{cs}}_{n})w_{i,n,r}y^{\mathrm{rep}}_{i,n,r}+R^{\mathrm{ep}}_{n,r}y^{\mathrm{rep}}_{i,n,r})$
(5)
$\displaystyle+\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}x^{\mathrm{rqt}}_{c,\rho,m,r}R^{\mathrm{cq}}_{c,\rho}\Big{)}+{\mathbb{E}}_{\Phi}\left[{\mathscr{C}}(w_{i,n,r},y^{\mathrm{rep}}_{i,n,r},x^{\mathrm{rqt}}_{c,\rho,m,r},\tilde{\psi})\right].$

Theoretically, the SP model with the random variable $\tilde{\psi}$ in Eq. (5)
can be transformed into the deterministic equivalent formulation [35] which is
expressed in Eqs. (8) - (24). Let $\mathcal{F}_{r,c}$ denote the set of the
possible fidelity values for quantum circuit $c$ of request $r$, which is
defined as
$\mathcal{F}_{r,c}=\\{\delta_{r,c,\varrho}|\delta_{r,c,\varrho}\in[0.0,1.0]\\}$.
Let $\mathcal{Q}_{r,c}$ denote the set of the potential number of qubits that
a request $r$’s quantum circuit $c$ may require, which is defined as
$\mathcal{Q}_{r,c}=\\{\beta_{r,c,1},\beta_{r,c,2},\dots,\beta_{r,c,{\iota}}\\}$.
Let $\mathcal{E}_{r,c}$ denote the set of the expected execution time for the
quantum circuit $c$ of request $r$, which is defined as
$\mathcal{E}_{r,c}=\\{\alpha_{r,c,1},\alpha_{r,c,2},\dots,\alpha_{r,c,\iota^{{}^{\prime}}}\\}$.
$\iota$ and $\iota^{{}^{\prime}}$ refer to the final indexes of the elements
within the finite sets $\mathcal{Q}_{r,c}$ and $\mathcal{E}_{r,c}$,
respectively. Let $\psi$ denote a scenario of request $r$. The scenario is a
realization of the random variable $\tilde{\psi}$. Therefore, the potential
value of the random variable can be selected from a set of scenarios. We use
the term $\Phi$ to denote the collection of all scenarios, which we refer to
as the _scenario space_. The set of all scenarios of request $r$ is denoted as
$\Psi_{r}$. The set of all scenarios is expressed as follows:

$\displaystyle\Phi={\displaystyle\prod_{r\in\mathcal{R}}}\Psi_{r}=\Psi_{1}\times\Psi_{2}\times\dots\times\Psi_{|\mathcal{R}|},\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;$
(6)
$\displaystyle\mbox{where}\;\;\Psi_{r}=\mathcal{F}_{r,c}\times\mathcal{Q}_{r,c}\times\mathcal{E}_{r,c}=\\{(\delta_{r,c},\beta_{r,c},\alpha_{r,c})|\delta_{r,c}\in\mathcal{F}_{r},\beta_{r,c}\in\mathcal{Q}_{r,c},\alpha_{r,c}\in\mathcal{E}_{r,c}\\}.$
(7)

$\times$ and $|\mathcal{R}|$ are the Cartesian product and the cardinality of
the set $\mathcal{R}$, respectively. Therefore, $\psi$ is the scenario space
of request $r$ (i.e., $\psi\in\Psi_{r}$). The probability that requirements of
fidelity, qubit and expected execution time of circuit $c$ of request $r$ are
realized is denoted as $\mathbf{P}_{r}(\psi)$. The expectation
$\mathbb{E}_{\Phi}[\;\cdot\;]$ of the SP model in Eq. (5) can be represented
by the weighted sum of scenarios and their probabilities
$\mathbf{P}_{r}(\psi)$.

The objective function presented in Eq. (8) is to minimize the overall cost of
entangled pairs across all quantum nodes for entanglement establishment, the
number of required qubits, and circuits’ over-waiting time. The decision
variables
$y^{\mathrm{eep}}_{i,n,r,\psi},y^{\mathrm{oep}}_{i,n,r,\psi},x^{\mathrm{uqt}}_{c,\rho,m,r,\psi},x^{\mathrm{oqt}}_{c,\rho,m,r,\psi}$,
and $y^{\mathrm{owt}}_{c,\rho,m,r,\psi}$ rely on $\psi\in\Psi_{r}$ which means
that demands’ values are available when $\psi$ is observed.

Equations (24) and (24) guarantee that source node $S^{\mathrm{q}}_{r}$ of
request $r$ and destination node $D^{\mathrm{q}}_{r}$ of request $r$ have only
one outgoing route and one incoming route, respectively. Equation (24) ensures
that the number of outgoing routes can be equal to the number of incoming
routes for all quantum nodes of request $r$ except source and destination
nodes. Equation (24) ensures that there is only one outgoing route for the
request $r$ of any node. Equation (24) defines that the number of entangled
pairs reserved at a link between nodes $i$ and $n$ in the reservation phase
can be less than or equal to the maximum capacity of entangled pairs
($R^{\mathrm{etp}}_{i,j}$).

Equation (24) ensures that the entangled pair utilization is not more than the
entangled pair reservation at a link between nodes $i$ and $n$ of request $r$.
Equations (24) and (24) guarantee that the sum of entangled pairs used in
utilization and on-demand phases satisfies the fidelity requirement and the
fidelity threshold, respectively. $\mathbf{F}^{\mathrm{dep}}(\cdot)$ in Eqs.
(24) and (24) is the entanglement purification algorithm that is applied to
enhance the entanglement fidelity based on the numbers of entangled pairs.
Equation (24) defines the maximum capacity constraint of the on-demand phase
($C^{\mathrm{oep}}_{i,j}$) for utilizing the entangled pairs at a link between
nodes $i$ and $j$.

Equation (24) guarantees that the number of qubits used in the utilization
phase can be less than or equal to the qubits reserved in the reservation
phase. Equation (24) guarantees that the number of qubits in the utilization
and on-demand phases can satisfy the qubit demands of quantum circuit $c$ for
request $r$ ($\beta_{r,c,\psi}$). The requirement in Eq. (24) is that quantum
circuit $c$’s waiting time for request $r$ ($\alpha_{r,c,\psi}$) can be
fulfilled. If quantum computer $m$ of provider $\rho$ takes more time to
execute quantum circuit $c$ for request $r$ ($E^{\mathrm{exe}}_{c,\rho,m,r}$)
than the waiting time of quantum circuit $c$, the additional waiting time of
quantum circuit $c$ ($y^{\mathrm{owt}}_{c,\rho,m,r,\psi}$) will be charged.
Equation (24) limits the number of qubits in the reservation phase for quantum
circuits to be less than the maximum number of qubits of quantum machine $m$
of provider $\rho$ ($C^{\mathrm{qbt}}_{\rho,m}$). Equation (24) defines that
the decision variable is the binary integer. Equations (24) and (24) define
that all decision variables are non-negative integers excluding
$y^{\mathrm{owt}}_{c,\rho,m,r,\psi}$ that is the positive real number.

$\displaystyle\min_{w_{i,n,r},y^{\mathrm{rep}}_{i,n,r},y^{\mathrm{eep}}_{i,n,r,\psi},y^{\mathrm{oep}}_{i,n,r,\psi},x^{\mathrm{rqt}}_{c,\rho,m,r},x^{\mathrm{uqt}}_{c,\rho,m,r,\psi},x^{\mathrm{oqt}}_{c,\rho,m,r,\psi},y^{\mathrm{owt}}_{c,\rho,m,r,\psi}}$
(8)
$\displaystyle\sum_{r\in{\mathcal{R}}}\Big{(}\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}((E^{\mathrm{cc}}_{n}+S^{\mathrm{cs}}_{n})w_{i,n,r}y^{\mathrm{rep}}_{i,n,r}+R^{\mathrm{ep}}_{n,r}y^{\mathrm{rep}}_{i,n,r})+\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}x^{\mathrm{rqt}}_{c,\rho,m,r}R^{\mathrm{cq}}_{c,\rho}\Big{)}$
$\displaystyle+\sum_{r\in{\mathcal{R}}}\Big{(}\mathbf{P}_{r}(\psi)\big{(}\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}(U^{\mathrm{ep}}_{n,r}y^{\mathrm{eep}}_{i,n,r,\psi}+O^{\mathrm{ep}}_{n,r}y^{\mathrm{oep}}_{i,n,r,\psi})$
$\displaystyle+\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}(x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}U^{\mathrm{cq}}_{c,\rho}+x^{\mathrm{oqt}}_{c,\rho,m,r,\psi}O^{\mathrm{cq}}_{c,\rho}+y^{\mathrm{owt}}_{c,\rho,m,r,\psi}P^{\mathrm{wt}}_{c,\rho})\big{)}\Big{)},$
s.t.
$\displaystyle\sum_{k^{\prime}\in{\mathcal{O}}_{S^{\mathrm{q}}_{r}}}w_{S^{\mathrm{q}}_{r},k^{\prime},r}-\sum_{h^{\prime}\in{\mathcal{I}}_{S^{\mathrm{q}}_{r}}}w_{h^{\prime},S^{\mathrm{q}}_{r},r}=1,r\in{\mathcal{R}},$
(24)
$\displaystyle\sum_{h^{\prime}\in{\mathcal{I}}_{D^{\mathrm{q}}_{r}}}w_{h^{\prime},D^{\mathrm{q}}_{r},r}-\sum_{k^{\prime}\in{\mathcal{O}}_{D^{\mathrm{q}}_{r}}}w_{D^{\mathrm{q}}_{r},k^{\prime},r}=1,r\in{\mathcal{R}},$
$\displaystyle\sum_{k^{\prime}\in{\mathcal{O}}_{n}}w_{n,k^{\prime},r}-\sum_{h^{\prime}\in{\mathcal{I}}_{n}}w_{h^{\prime},n,r}=0,r\in{\mathcal{R}},n\in{\mathcal{N}}\setminus\\{S^{\mathrm{q}}_{r},D^{\mathrm{q}}_{r}\\},$
$\displaystyle\sum_{k^{\prime}\in{\mathcal{O}}_{n}}w_{n,k^{\prime},r}\leq
1,n\in{\mathcal{N}},r\in{\mathcal{R}},$
$\displaystyle\sum_{r\in{\mathcal{R}}}y^{\mathrm{rep}}_{i,n,r}w_{i,n,r}\leq
R^{\mathrm{etp}}_{i,j},i,j,n\in{\mathcal{N}},$ $\displaystyle
y^{\mathrm{eep}}_{i,n,r,\psi}w_{i,n,r}\leq
y^{\mathrm{rep}}_{i,n,r}w_{i,n,r},i,j,n\in{\mathcal{N}},r\in{\mathcal{R}},\forall\psi\in\Psi_{r},$
$\displaystyle\mathbf{F}^{\mathrm{dep}}\big{(}(y^{\mathrm{eep}}_{i,n,r,\psi}w_{i,j,r})+y^{\mathrm{oep}}_{i,n,r,\psi}\big{)}\geq\delta_{r,c,\psi},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\psi\in\Psi_{r},$
$\displaystyle\mathbf{F}^{\mathrm{dep}}\big{(}(y^{\mathrm{eep}}_{i,n,r,\psi}w_{i,j,r})+y^{\mathrm{oep}}_{i,n,r,\psi}\big{)}\geq
F^{\mathrm{fts}}_{i,n},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\psi\in\Psi_{r},$
$\displaystyle\sum_{r\in{\mathcal{R}}}\big{(}y^{\mathrm{oep}}_{i,j,r,\psi}w_{i,j,r}\big{)}\leq
C^{\mathrm{oep}}_{i,j},i,j\in{\mathcal{N}},\forall\psi\in\Psi_{r},$
$\displaystyle x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}\leq
x^{\mathrm{rqt}}_{c,\rho,m,r},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r},$ $\displaystyle
x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}+x^{\mathrm{oqt}}_{c,\rho,m,r,\psi}\geq\beta_{r,c,\psi},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r},$ $\displaystyle
E^{\mathrm{exe}}_{c,\rho,m,r}\leq\alpha_{r,c,\psi}+y^{\mathrm{owt}}_{c,\rho,m,r,\psi},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r},$ $\displaystyle
x^{\mathrm{rqt}}_{c,\rho,m,r}\leq
C^{\mathrm{qbt}}_{\rho,m},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},$ $\displaystyle
w_{i,n,r}\in\\{0,1\\},i,n\in{\mathcal{N}},r\in{\mathcal{R}},$ $\displaystyle
y^{\mathrm{rep}}_{i,n,r},y^{\mathrm{eep}}_{i,n,r,\psi},y^{\mathrm{oep}}_{i,n,r,\psi}\in\mathbb{Z}^{\ast},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\forall\psi\in\Psi_{r},$
$\displaystyle
x^{\mathrm{rqt}}_{c,\rho,m,r},x^{\mathrm{uqt}}_{c,\rho,m,r,\psi},x^{\mathrm{oqt}}_{c,\rho,m,r,\psi}\in\mathbb{Z}^{\ast},y^{\mathrm{owt}}_{c,\rho,m,r,\psi}\in\mathbb{R}^{+},$
$\displaystyle r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r}.$

##  V Benders Decomposition

In this section, given the entanglement routing ($w^{\ast}_{i,n,r}$) for
request $r$, we apply the Benders decomposition algorithm [36] to solve the SP
problem proposed in Section IV. The objective of the algorithm is to divide
the SP problem into multiple smaller SP problems that can be solved
independently and concurrently. Note that this is solved on classical
computers, while the algorithm is also applicable to quantum computers to
solve, but we leave it as future work to optimize the solution algorithm for
quantum computers. As a result, the complexity of the problem is reduced and
the computational time to achieve the solution of the problem is shortened.
The Benders decomposition algorithm can divide the SP problem presented in
Eqs. (8) - (24) with complicating variables into master problem and
subproblem. In the problem, we separately apply the Benders decomposition
algorithm to the entangled pair resource allocation and the qubit resource
allocation.

###  V-A Entangled Pair Resource Allocation

In the entangled pair resource allocation, decision variables
$y^{\mathrm{eep}}_{i,n,r,\psi}$ are the complicating variables. If variables
$y^{\mathrm{eep}}_{i,n,r,\psi}$ are the fixed values and denoted as
$y^{\mathrm{eepfix}}_{i,n,r,\psi}$, the entangled pair resource allocation can
be decomposed into a master problem and two subproblems. Let $M^{\mathrm{ep}}$
denote the master problem which is presented as follows:

$\displaystyle z^{\mathrm{eep}}_{\nu}$
$\displaystyle=\min_{y^{\mathrm{eep}}_{i,n,r,\psi,\nu}}\sum_{r\in{\mathcal{R}}}\mathbf{P}_{r}(\psi)\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}(U^{\mathrm{ep}}_{n,r}y^{\mathrm{eep}}_{i,n,r,\psi,\nu})+\alpha_{\nu},$
(25) s.t. $\displaystyle\alpha_{\nu}\geq\alpha^{\mathrm{lwb}}_{\nu},$ (30)
$\displaystyle\mathbf{F}^{\mathrm{dep}}(y^{\mathrm{eep}}_{i,n,r,\psi,\nu}w^{\ast}_{i,j,r})\leq\delta_{r,c,\psi},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\psi\in\Psi_{r},$
$\displaystyle\mathbf{F}^{\mathrm{dep}}(y^{\mathrm{eep}}_{i,n,r,\psi,\nu}w^{\ast}_{i,j,r})\leq
F^{\mathrm{fts}}_{i,n},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\psi\in\Psi_{r},$
$\displaystyle\sum_{r\in{\mathcal{R}}}\sum_{\psi\in\Psi_{r}}y^{\mathrm{eep}}_{i,n,r,\psi,\nu}w^{\ast}_{i,n,r}\leq
R^{\mathrm{etp}}_{i,j},i,j,n\in{\mathcal{N}},$ $\displaystyle
y^{\mathrm{eep}}_{i,n,r,\psi,\nu}\in\mathbb{Z}^{\ast},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\forall\psi\in\Psi_{r}.$

The objective function in Eq. (25) is derived from Eq. (8). Let $\alpha_{\nu}$
denote the minimum costs of reservation and on-demand phases. $\alpha_{\nu}$
is updated in each iteration $\nu$. Let $\alpha^{\mathrm{lwb}}_{\nu}$ in Eq.
(30) denote the lower bound of the minimum costs of reservation and on-demand
phases. Let $\nu$ denote the iteration counter and initially set $\nu=1$.
Constraints in Eqs. (30) - (30) are the boundary of
$y^{\mathrm{eep}}_{i,n,r,\psi,\nu}$. Let $S^{\mathrm{ep}}_{1}$ and
$S^{\mathrm{ep}}_{2}(\psi)$ denote the subproblems 1 and 2, respectively. The
subproblem $S^{\mathrm{ep}}_{1}$ is presented as follows:

$\displaystyle z^{\mathrm{rep}}_{\nu}$
$\displaystyle=\min_{y^{\mathrm{rep}}_{i,n,r}}\sum_{r\in{\mathcal{R}}}\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}(E^{\mathrm{cc}}_{n}+S^{\mathrm{cs}}_{n})w_{i,n,r}y^{\mathrm{rep}}_{i,n,r}+R^{\mathrm{ep}}_{n,r}y^{\mathrm{rep}}_{i,n,r},$
(31) s.t.
$\displaystyle(\ref{eq:sp_const5}),(\ref{eq:def_const6}),\;\mbox{and}\;(\ref{eq:def_const11}),$
(33) $\displaystyle
w_{i,n,r}=w^{\ast}_{i,n,r},i,n\in{\mathcal{N}},r\in{\mathcal{R}},$
$\displaystyle
y^{\mathrm{eep}}_{i,n,r,\psi}=y^{\mathrm{eepfix}}_{i,n,r,\psi},i,n\in{\mathcal{N}},r\in{\mathcal{R}},\forall\psi\in\Psi_{r}.$

The subproblem $S^{\mathrm{ep}}_{2}(\psi)$ is presented as follows:

$\displaystyle z^{\mathrm{oep}}_{\nu}(\psi)$ $\displaystyle=$
$\displaystyle\min_{y^{\mathrm{oep}}_{i,n,r,\psi}}\sum_{r\in{\mathcal{R}}}\mathbf{P}_{r}(\psi)\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}U^{\mathrm{ep}}_{n,r}y^{\mathrm{eep}}_{i,n,r,\psi}+O^{\mathrm{ep}}_{n,r}y^{\mathrm{oep}}_{i,n,r,\psi},$
(34) s.t.
$\displaystyle(\ref{eq:def_const7}),(\ref{eq:def_const8}),(\ref{eq:def_const9}),(\ref{eq:sub1_const1}),\;\mbox{and}\;(\ref{eq:sub_entangled_pair_cost_fix}).$

###  V-B Qubit Resource Allocation

In qubit resource allocation, decision variables
$x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}$ are the complicating variables. If
variables $x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}$ have fixed values and denoted
as $x^{\mathrm{uqtfix}}_{c,\rho,m,r,\psi}$, the qubit resource allocation can
be decomposed into two subproblems, namely, $S^{\mathrm{qt}}_{1}$ and
$S^{\mathrm{qt}}_{2}$. Let $M^{\mathrm{qt}}$ denote the master problem which
is presented as follows:

$\displaystyle z^{\mathrm{uqt}}_{\acute{\nu}}$ $\displaystyle=$
$\displaystyle\min_{x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}}\sum_{r\in{\mathcal{R}}}\mathbf{P}_{r}(\psi)\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}(x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}U^{\mathrm{cq}}_{c,\rho})+\theta_{\acute{\nu}},$
(35) s.t.
$\displaystyle\theta_{\acute{\nu}}\geq\theta^{\mathrm{lwb}}_{\acute{\nu}},$
(39) $\displaystyle
x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}\leq\beta_{r,c,\psi},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r},$ $\displaystyle
x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}\leq
C^{\mathrm{qbt}}_{\rho,m},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r},$ $\displaystyle
x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}\in\mathbb{Z}^{\ast},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r}.$

The objective function in Eq. (35) is derived from that in Eq. (8). Let
$\theta_{\acute{\nu}}$ denote the minimum costs of reservation and on-demand
phases. $\theta_{\acute{\nu}}$ is updated in each iteration $\acute{\nu}$. Let
$\theta^{\mathrm{lwb}}_{\acute{\nu}}$ in Eq. (39) denote the lower bound of
the minimum costs of reservation and on-demand phases. Let $\acute{\nu}$
denote the iteration counter and initially set $\acute{\nu}=1$. Constraints in
Eqs. (39) - (39) are the boundary of
$x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}$. The subproblem
$S^{\mathrm{qt}}_{1}$ is presented as follows:

$\displaystyle z^{\mathrm{rqt}}_{\acute{\nu}}$ $\displaystyle=$
$\displaystyle\min_{x^{\mathrm{rqt}}_{c,\rho,m,r}}\sum_{r\in{\mathcal{R}}}\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}x^{\mathrm{rqt}}_{c,\rho,m,r}R^{\mathrm{cq}}_{c,\rho},$
(40) s.t.
$\displaystyle(\ref{eq:sp_const15})\;\mbox{and}\;(\ref{eq:def_const12}),$ (42)
$\displaystyle
x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}=x^{\mathrm{uqtfix}}_{c,\rho,m,r,\psi},r\in{\mathcal{R}},\forall
c\in\mathcal{S}^{\mathrm{qc}}_{r},\forall\rho\in\mathcal{S}^{\mathrm{qp}},\forall
m\in\mathcal{S}^{\mathrm{qm}}_{\rho},\forall\psi\in\Psi_{r}.$

The subproblem $S^{\mathrm{qt}}_{2}(\psi)$ is presented as follows:

$\displaystyle z^{\mathrm{oqt}}_{\acute{\nu}}(\psi)$ $\displaystyle=$
$\displaystyle\min_{x^{\mathrm{oqt}}_{c,\rho,m,r,\psi},y^{\mathrm{owt}}_{c,\rho,m,r,\psi}}\sum_{r\in{\mathcal{R}}}\mathbf{P}_{r}(\psi)\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}(x^{\mathrm{uqt}}_{c,\rho,m,r,\psi}U^{\mathrm{cq}}_{c,\rho}+x^{\mathrm{oqt}}_{c,\rho,m,r,\psi}O^{\mathrm{cq}}_{c,\rho}$
(43)
$\displaystyle+y^{\mathrm{owt}}_{c,\rho,m,r,\psi}P^{\mathrm{wt}}_{c,\rho}),$
s.t.
$\displaystyle(\ref{eq:def_const13}),(\ref{eq:def_const14}),\;\mbox{and}\;(\ref{eq:sub_qubit_const_fix}).$

###  V-C Benders Decomposition Algorithm

The algorithm outlines a four-step approach for addressing the challenges of
entangled pair resource allocation and qubit resource allocation problems.

Step 1: Initialization of master problems. This step initializes the master
problems and performs only one time while steps 2, 3, and 4 repeat in the
algorithm. In this step, the master problems of the entangle pair resource
allocation and qubit resource allocation, which are respectively expressed in
Eqs. (25) - (30) and Eqs. (35) - (39) are the alternative form of the
deterministic equivalent formulation represented in Eqs. (8) - (24).

Step 2: Subproblem solutions. The subproblems $S^{\mathrm{ep}}_{1}$,
$S^{\mathrm{ep}}_{2}(\psi)$, $S^{\mathrm{qt}}_{1}$, and
$S^{\mathrm{qt}}_{2}(\psi)$ are formulated and solved. We assign solution
$y^{\mathrm{eep}}_{i,n,r,\psi,\nu}$ obtained from the master problem in Eqs.
(25) - (30) to $y^{\mathrm{eepfix}}_{i,n,r,\psi}$ (i.e.,
$y^{\mathrm{eepfix}}_{i,n,r,\psi}=y^{\mathrm{eep}}_{i,n,r,\psi,\nu}$). Then,
we assign solution $x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}$ obtained
from the master problem in Eqs. (35) - (39) to
$x^{\mathrm{uqtfix}}_{c,\rho,m,r,\psi}$ (i.e.,
$x^{\mathrm{uqtfix}}_{c,\rho,m,r,\psi}=x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}$).
Therefore, given the fixed solutions $y^{\mathrm{eepfix}}_{i,n,r,\psi}$ and
$x^{\mathrm{uqtfix}}_{c,\rho,m,r,\psi}$, the subproblems
$S^{\mathrm{ep}}_{1}$, $S^{\mathrm{ep}}_{2}(\psi)$, $S^{\mathrm{qt}}_{1}$, and
$S^{\mathrm{qt}}_{2}(\psi)$ can be solved concurrently.

The objective of subproblem $S^{\mathrm{ep}}_{1}$ in Eqs. (31)- (33) is to
minimize the reservation cost regarding the entangled pairs. Let
$\lambda^{\mathrm{rep}}_{i,n,r,\nu}$ denote the solution of the dual problem
of $S^{\mathrm{ep}}_{1}$ in iteration $\nu$ associated with Eq. (33). The
objective of subproblem $S^{\mathrm{ep}}_{2}(\psi)$ in Eq. (34) is to minimize
the on-demand cost regarding the entangled pairs. Let
$\lambda^{\mathrm{oep}}_{i,n,r,\nu}(\psi)$ denote the solution of the dual
problem of $S^{\mathrm{ep}}_{2}(\psi)$ when the fidelity value (i.e.,
$\delta_{r,c,\varrho}$) is observed and set to $\psi$. The subproblem
$S^{\mathrm{ep}}_{2}(\psi)$ associates with the number of scenarios
$|\Psi^{\mathrm{ep}}_{r}|,\psi\in\Psi^{\mathrm{ep}}_{r}$ where
$|\Psi^{\mathrm{ep}}_{r}|$ is the Cardinality of set $\Psi^{\mathrm{ep}}_{r}$,
and therefore $|\Psi^{\mathrm{ep}}_{r}|$ is generated. Let
$\lambda^{\mathrm{oep}}_{i,n,r,\nu}(\psi)$ denote the solution of the dual
problem of $S^{\mathrm{ep}}_{2}(\psi)$ in iteration $\nu$ associated with Eq.
(33).

The objective of subproblem $S^{\mathrm{qt}}_{1}$ is to minimize the
reservation cost of the qubit allocation. Let
$\lambda^{\mathrm{qrt}}_{c,\rho,m,r,\acute{\nu}}$ denote the solution of the
dual problem of $S^{\mathrm{qt}}_{1}$ in iteration $\acute{\nu}$ associated
with Eq. (42). The objective of subproblem $S^{\mathrm{qt}}_{2}(\psi)$ is to
minimize the on-demand cost of the qubit allocation. Let
$\lambda^{\mathrm{oqt}}_{c,\rho,m,r,\acute{\nu}}(\psi)$ denote the solution of
the dual problem of $S^{\mathrm{qt}}_{2}(\psi)$ when the number of required
qubits (i.e., $\beta_{r,c,{\iota}}$), and the waiting time for quantum
circuits (i.e., $\alpha_{r,c,\iota^{{}^{\prime}}}$) are observed and set to
$\psi$. The subproblem $S^{\mathrm{qt}}_{2}(\psi)$ associates with the number
of scenarios $|\Psi^{\mathrm{qt}}_{r}|,\psi\in\Psi^{\mathrm{qt}}_{r}$ where
$|\Psi^{\mathrm{qt}}_{r}|$ is the Cardinality of set $\Psi^{\mathrm{qt}}_{r}$,
and therefore $|\Psi^{\mathrm{qt}}_{r}|$ is generated. Let
$\lambda^{\mathrm{oqt}}_{c,\rho,m,r,\acute{\nu}}(\psi)$ denote the solution of
the dual problem of $S^{\mathrm{qt}}_{2}(\psi)$ in iteration $\acute{\nu}$
associated with Eq. (42). The solutions of
$\lambda^{\mathrm{rep}}_{i,n,r,\nu}$,
$\lambda^{\mathrm{oep}}_{i,n,r,\nu}(\psi)$,
$\lambda^{\mathrm{qrt}}_{c,\rho,m,r,\acute{\nu}}$, and
$\lambda^{\mathrm{oqt}}_{c,\rho,m,r,\acute{\nu}}(\psi)$ will be applied in
step 4.

Step 3: Convergence checking. The convergence of lower and upper bounds of
solutions from master problems and subproblems are checked. Let
$z^{\mathrm{lwb}}_{\nu}$ denote the lower bound in iteration $\nu$ obtained
from the master problem in Eq. (25), which is $z^{\mathrm{lwb}}_{\nu}$ =
$z^{\ast\mathrm{eep}}_{\nu}$. Let $z^{\mathrm{upb}}_{\nu}$ denote the upper
bound in iteration $\nu$ that is obtained from
$z^{\mathrm{upb}}_{\nu}=z^{\ast\mathrm{eep}}_{\nu}-\alpha_{\nu}+z^{\mathrm{rep}}_{\nu}+z^{\mathrm{oep}}_{\nu}$.
Let $z^{\mathrm{lwb}}_{\acute{\nu}}$ denote the lower bound in iteration
$\acute{\nu}$ obtained from the master in Eq. (35), which is
$z^{\mathrm{lwb}}_{\acute{\nu}}$ = $z^{\ast\mathrm{uqt}}_{\acute{\nu}}$. Let
$z^{\mathrm{upb}}_{\acute{\nu}}$ denote the upper bound in iteration
$\acute{\nu}$ that is obtained from
$z^{\mathrm{upb}}_{\acute{\nu}}=z^{\ast\mathrm{uqt}}_{\acute{\nu}}-\theta_{\acute{\nu}}+z^{\mathrm{rqt}}_{\acute{\nu}}+z^{\mathrm{oqt}}_{\acute{\nu}}$.
Let $\epsilon$ and $\varepsilon$ denote the small tolerance values to verify
the convergence of lower and upper bounds for entangled pair resource
allocation and qubit resource allocation, respectively. If
$z^{\mathrm{upb}}_{\nu}-z^{\mathrm{lwb}}_{\nu}<\epsilon$ and
$z^{\mathrm{upb}}_{\acute{\nu}}-z^{\mathrm{lwb}}_{\acute{\nu}}<\varepsilon$,
the Benders decomposition algorithm stops and the optimal solutions achieve.
Otherwise, the algorithm performs to step 4.

Step 4: Master problem solutions.

$\displaystyle\alpha_{\nu}$ $\displaystyle\geq$
$\displaystyle\sum_{r\in{\mathcal{R}}}\sum_{\psi\in\Psi}\sum_{n\in{\mathcal{N}}}\sum_{i\in{\mathcal{I}}_{n}}\Big{(}(\lambda^{\mathrm{rep}}_{i,n,r,\bar{\nu}}+\lambda^{\mathrm{oep}}_{i,n,r,\bar{\nu}}(\psi))(y^{\mathrm{eep}}_{i,n,r,\psi,\nu}-y^{\mathrm{eep}}_{i,n,r,\psi,\bar{\nu}})\Big{)}$
(44) $\displaystyle+z^{\mathrm{\ast
rep}}_{\bar{\nu}}+\sum_{\psi\in\Psi}z^{\mathrm{\ast
oep}}_{\bar{\nu}}(\psi),\bar{\nu}\in\\{1,\dots,\nu-1\\},$
$\displaystyle\theta_{\acute{\nu}}$ $\displaystyle\geq$
$\displaystyle\sum_{r\in{\mathcal{R}}}\sum_{\psi\in\Psi}\sum_{c\in\mathcal{S}^{\mathrm{qc}}_{r}}\sum_{\rho\in\mathcal{S}^{\mathrm{qp}}}\sum_{m\in\mathcal{S}^{\mathrm{qm}}_{\rho}}\Big{(}(\lambda^{\mathrm{qrt}}_{c,\rho,m,r,\ddot{\nu}}+\lambda^{\mathrm{oqt}}_{c,\rho,m,r,\ddot{\nu}}(\psi))(x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}-x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\ddot{\nu}})\Big{)}$
(45) $\displaystyle+z^{\mathrm{\ast
rqt}}_{\ddot{\nu}}+\sum_{\psi\in\Psi}z^{\mathrm{\ast
oqt}}_{\ddot{\nu}}(\psi),\ddot{\nu}\in\\{1,\dots,\acute{\nu}-1\\}.$

The iteration counters $\nu$ and $\acute{\nu}$ are respectively incremented by
$\nu=\nu+1$ and $\acute{\nu}=\acute{\nu}+1$. Then, the master problems of the
entangled pair resource allocation in Eqs. (25) - (30) and qubit resource
allocation in Eqs. (35) - (39) can be relaxed by additional constraints (i.e.,
_Bender cuts_ [36]). The solutions of the master problems update the costs
$\alpha_{\nu}$ and $\theta_{\acute{\nu}}$ and the utilizing costs according to
the solutions of $y^{\mathrm{eep}}_{i,n,r,\psi,\nu}$ and
$x^{\mathrm{uqt}}_{c,\rho,m,r,\psi,\acute{\nu}}$. Benders cuts as shown in
Eqs. (44) and (45) are created from the optimal costs obtained from master
problems and subproblems in the previous iterations. Once the master problems
are solved, step 2 is executed, and the iterative process is repeated.

##  VI Performance Evaluation

###  VI-A Parameter Setting

We evaluate the QCC system as illustrated in Fig. 1. The system consists of
three QCC providers ($\mathcal{S}^{\mathrm{qp}}=\\{1,2,3\\}$), each of which
has two quantum computers ($\mathcal{S}^{\mathrm{qm}}_{\rho}=\\{1,2\\}$) [24].
For each provider $\rho$, we establish a maximum limit of 30 qubits [24] per
quantum computer ($C^{\mathrm{qbt}}_{\rho,m}$). Initially, we assign the
penalty cost of $10 [24] for the waiting time of circuit program $c$ when
processed by provider $\rho$ ($P^{\mathrm{wt}}_{c,\rho}$). For qubit cost
values charged by provider $\rho$ for circuit $c$, we set the reservation
($R^{\mathrm{cq}}_{c,\rho}$), utilization ($U^{\mathrm{cq}}_{c,\rho}$), and
on-demand costs ($O^{\mathrm{cq}}_{c,\rho}$) to be $1.68 [1], $0.1 [24], $7
[24], respectively. We consider quantum circuits of quantum discrete Fourier
transform (QDFT) [31] with different numbers of qubits, which we exemplify and
perform. We consider that circuit program $c$ requires a random number of
qubits between 10 and 22 [24], denoted by
$\beta_{r,c,\psi}\in\\{10,\dots,22\\}$, and has a random waiting time between
0.001 and 0.009 seconds [24], denoted as
$\alpha_{r,c,\psi}\in\\{0.001,\dots,0.009\\}$. Both of these random variables
are assumed to follow a uniform distribution. We conduct experiments on the
NSFNET network connected via optical fibers [7]. The initial values of
fidelity between nodes $i$ and $j$ in the network are presented in Fig. 5(a).
The initial fidelity threshold ($F^{\mathrm{fts}}_{i,n}$) is 0.8 [8]. The
largest quantity of entangled pairs between nodes $i$ and $j$ in the
reservation ($R^{\mathrm{etp}}_{i,j}$) and the on-demand
($C^{\mathrm{oep}}_{i,j}$) phases are 9 and 60, respectively. The random
quantity of fidelity requirements is set between 0.55 to 1.0 (i.e.,
$\delta_{r,c,\psi}\in\\{0.55,\dots,1.0\\}$) with uniform distribution. We also
set the cost of an entangled pair for reservation ($R^{\mathrm{ep}}_{n,r}$),
utilization ($U^{\mathrm{ep}}_{n,r}$), and on-demand ($O^{\mathrm{ep}}_{n,r}$)
phases to $10, $1, and $200, respectively [32]. Additionally, energy
consumption cost of node $n$ ($E^{\mathrm{cc}}_{n}$) is $5 while energy
consumption cost to establish repeater node $n$ ($S^{\mathrm{cs}}_{n}$) is
$151. For Benders decomposition, we set the small tolerance values to verify
the convergence of lower and upper bounds for entangled pair resource
allocation ($\epsilon$) and qubit resource allocation ($\varepsilon$) to be
0.05. We use the GAMS/CPLEX solver [37] to implement and solve the stochastic
programming formulation.

###  VI-B Numerical Results

We divide the experiment into two parts: entangled pair resource allocation
and qubit resource allocation. In the entangled pair resource allocation part,
we conduct networking experiments based on the allocation of entangled pairs.
This includes considerations such as entanglement routing, fidelity
requirements, and entanglement purification. In the qubit resource allocation
part, we perform computing experiments based on the allocation of computing
qubits, quantum circuits, quantum computers, and QCC providers.

####  VI-B1 Entangled pair resource allocation

(a) Route solutions for three requests.

(b) Utilization of the entangled pairs in SP model.

(c) The total and two-stage costs.

Figure 5: (a) Requests $r_{1}$, $r_{2}$, and $r_{3}$ in NSFNET topology, (b)
Comparison of entangled pair utilization of 3 phases, and (c) The optimal
solution in SP model.

Figure 5(a) shows the solutions generated by the proposed model that meet the
fidelity requirements of three distinct requests, namely $r_{1}$, $r_{2}$, and
$r_{3}$. For each request, the SP model determines the optimal route and the
number of entangled pairs needed to comply with the fidelity requirement in
the network. For example, the route for request $r_{1}$ is nodes $2\rightarrow
3\rightarrow 6\rightarrow 14$ and the SP model allocates 9 entangled pairs to
satisfy its fidelity requirement. Additionally, we observe that the number of
entangled pairs between nodes 2 and 3 (i.e., $2\rightarrow 3$) is utilized at
7 since the fidelity value between these nodes (i.e., $0.55$) is less than the
fidelity requirement (i.e., $0.80$). Therefore, the entangled pairs are more
utilized for entanglement purification to enhance the fidelity value and
satisfy the fidelity requirement.

Figure 5(b) illustrates the number of entangled pairs in three different
phases (reservation, utilization, and on-demand) across various fidelity
requirements. As depicted in the figure, the quantity of reserved and utilized
entangled pairs rises gradually in the reservation and utilization phases
until the fidelity requirement reaches 0.87. Once this value is reached, the
reserved and utilized entangled pairs reach their peak capacity of 9 pairs and
are unable to accommodate higher fidelity requirements. Hence, to fulfill more
demanding fidelity requirements, the entangled pairs in the on-demand phase
are used. In this phase, the utilization of entangled pairs begins at a
fidelity requirement of 0.88, as the reservation phase has limited capacity
for entangled pairs.

Figure 5(c) demonstrates the effectiveness of the SP model in achieving the
optimal solution. We vary the quantity of reserved entangled pairs and show
the optimal outcome achieved through the model, along with the influence of
reserved entangled pairs on the solution. As shown in Fig. 5(c), the first-
stage cost rises significantly as the number of reserved entangled pairs
increases. However, the second-stage cost decreases significantly after the
fidelity requirements are met. This is because the number of entangled pairs
in the reservation phase is constrained to be maximum due to the lower cost,
while the number of entangled pairs in the on-demand phase is constrained to
be minimum. Therefore, the optimal solution is reached at 24 reserved
entangled pairs, with a cost of $12,272.399 and the second-stage cost of $0,
since the reserved entangled pairs meet the fidelity requirements, and there
is no need to utilize on-demand entangled pairs in the second stage. After 24
reserved entangled pairs, both the total cost and the first-stage cost
slightly rise because of the penalty for reserving excess entangled pairs.
Therefore, we can conclude that the over- and under-provision of entangled
pairs can significantly impact the total cost.

(a) The optimal total cost.

(b) Fidelity value comparison.

(c) The total costs.

Figure 6: (a) The optimal solution under different reservation costs and
number of entangled pairs, (b) Comparison of entangled pair utilization of 4
fidelity values, and (c) Comparison of total cost of 3 fidelity requirements.

In addition, we investigate the performance of the proposed model in obtaining
the optimal solution by varying the number of reserved entangled pairs and
reservation costs. As shown in Fig. 6(a), the optimal cost can be attained
when both the number of reserved entangled pairs and reservation cost
increase, with the optimal solution achieved at 12 reserved entangled pairs
and a reservation cost of $10.

Figure 6(b) illustrates the performance of the proposed model in achieving the
optimal number of entangled pairs for different fidelity requirements. The
main observation is that the number of applied entangled pairs increases if
the fidelity requirement exceeds the fidelity value between quantum nodes $i$
and $j$. This is due to the fact that higher fidelity requirements demand more
entangled pairs to be used for entanglement purification in order to meet the
required fidelity. Moreover, if the fidelity value between quantum nodes $i$
and $j$ is equal to or greater than the fidelity requirement, only one
entangled pair is applied, which indicates that no entanglement purification
is needed to enhance the fidelity value between those nodes.

We consider that, under different reservation costs, all fidelity values
between quantum nodes $i$ and $j$ are 0.60 in the NSFNET topology to show the
solution of the proposed model. As shown in Fig. 6(c), the total cost rises
significantly when the reservation cost increases. Particularly, in the case
of the fidelity requirement (FR) that is higher than the fidelity value (FV),
the total cost in this case is higher than in the other two cases. This is
because the number of entangled pairs is more utilized to perform the
entanglement purification required to satisfy the fidelity requirement,
resulting in a higher total cost. Therefore, from the aforementioned results
shown in Figs. 6(b) and 6(c), we can conclude that fidelity values and
fidelity requirements have a significant effect not only on the number of
entangled pairs but also on the total cost.

####  VI-B2 Qubit resource allocation

To demonstrate the varying execution times of quantum circuits with different
numbers of qubits, we conduct experiments using Qiskit [31] to implement the
QFT quantum circuits.

Figure 7(a) demonstrates how the execution time of QDFT, implemented using
Qiskit [31], varies depending on the encoded numbers. As depicted in Fig.
7(a), the execution time of QDFT is highest for an encoded number of 16383,
due to the large number of qubits needed to represent and calculate the number
in the transformation. Specifically, 14 qubits are required to represent the
number 16383 in binary (i.e., 11111111111111) and the 14-qubit quantum circuit
for the encoded number 16383 has a long depth. Thus, we can conclude that both
the high encoded number and the long-depth quantum circuit have a direct
impact on the execution time of the QDFT.

(a) QDFT execution times.

(b) The total and two-stage costs.

(c) The minimum total cost.

(d) The total costs.

Figure 7: (a) Comparison of QDFT’s execution times with different encoded
numbers, (b) The optimal solution in SP model, (c) The optimal solution under
various arranged waiting times and number of reserved qubits, and (d)
Comparison of total costs of 5 penalty costs.

Figure 7(b) illustrates that the cost in the first stage increases slightly as
the number of reserved qubits increases, whereas the cost in the second stage
gradually declines when the number of required qubits is observed in this
stage. This is because the reservation qubit cost in the first stage is lower
than the on-demand qubit cost in the second stage. Thus, to minimize costs,
the qubit utilization in the second stage can be minimized while the qubit
utilization in the first stage can be maximized. At the optimal solution with
10 reserved qubits, the first-stage cost and the total cost are $12,272.399,
but the second-stage cost becomes $0. This is because the reserved qubit
utilization meets the qubit demands while the on-demand qubit utilization
remains unused. After reserving 12 qubits, both the total cost and the first-
stage cost continue to rise slightly due to the penalty cost incurred for
reserving more qubits than necessary. Thus, under-provisioning and over-
provisioning of qubits have a notable impact on both the total cost and the
first-stage cost. Figure 7(c) shows the optimal solution when the numbers of
reserved qubits and arranged waiting times required by quantum circuits are
varied. The optimal solution in Fig. 7(c) is achieved by the SP model, which
consists of 10 reserved qubits and 0.01 seconds of waiting time, i.e., (10,
0.01).

We consider a scenario where the time it takes for a quantum computer from a
provider to execute the QDFT circuit program ($E^{\mathrm{exe}}_{c,\rho,m,r}$)
is longer than the time it takes for the program to wait
($\alpha_{r,c,\psi}$). To examine the impact on total cost, we explore the
cost of qubits during the reservation phase and the cost of additional waiting
time for quantum circuits. Figure 7(d) shows the total costs at different
penalty costs of over-waiting time. The graph shows that the total cost
increases rapidly as the reservation cost goes up until it reaches $6.68. This
is because two factors contribute to the total cost: the cost of qubits during
the reservation phase, and the cost of over-waiting time for quantum circuits
($y^{\mathrm{owt}}_{c,\rho,m,r,\psi}P^{\mathrm{wt}}_{c,\rho}$). During the
reservation phase, qubits are used to meet the qubit demands, as the cost of
qubits during the reservation phase is the lowest. The cost of over-waiting
time is charged when quantum circuits have to wait longer than expected. Once
the reservation cost reaches $6.68, the total cost remains constant regardless
of any penalty costs due to no waiting time. This is because, at this point,
the number of qubits used during the on-demand phase is sufficient to meet the
qubit demand, and the cost of using qubits during this phase is less than the
cost of using qubits during the reservation phase. Therefore, raising the
reservation cost has no effect on the total costs.

(a) The qubit utilization.

(b) Quantum circuit comparison.

(c) The convergence.

(d) The performance comparison.

Figure 8: (a) Comparison of qubit utilization in the reservation and on-demand
phases, (b) Comparison of total costs of quantum circuits with different
qubits, (c) The convergence of the upper and lower bounds by applying Benders
decomposition algorithm, and (d) The performance comparison between the
proposed model with two other models.

Based on the findings presented in Fig. 7(d), Fig. 8(a) shows the number of
qubits used during the reservation and on-demand phases. As expected, the
qubits in reservation phase are utilized when the reservation cost falls
between $1.68 and $6.68. However, when the reservation cost increases to
$7.68, the qubits in on-demand phase are used instead of the reserved ones and
all total costs become constant.

To determine the total cost of the QDFT, we analyze the impact of the waiting
time of quantum circuits. Specifically, we manipulate the waiting time of
these circuits while keeping the encoded number 31 (which is represented as
11111 in binary) fixed. Figure 8(b) illustrates the total costs of running the
QFT circuits under varying waiting times. The figure clearly shows that the
24-qubit quantum circuit has the highest total cost, while the 16-qubit
quantum circuit has the smallest total cost, as the waiting time of the
quantum circuits raises. Notably, for waiting times between 0.001 and 0.006
seconds, the total costs of all the circuits decrease significantly with an
increase in the waiting time. This is because the penalty cost incurred due to
the extra waiting time (i.e.,
$y^{\mathrm{owt}}_{c,\rho,m,r,\psi}P^{\mathrm{wt}}_{c,\rho}$) declines since
the quantum computer of the provider is capable of completing quantum circuits
before the time that quantum circuits require. In addition, the total costs
become stable when it does not have additional waiting time for the quantum
circuits. Specifically, the total costs of 16-qubit and 20-qubit quantum
circuits are stable at waiting times of 0.007 seconds while the total cost of
24-qubit quantum circuit is stable at 0.01 seconds. Thus, we can conclude that
the waiting time of quantum circuits is a critical factor affecting the total
costs, as indicated in Fig. 8(b).

####  VI-B3 Benders decomposition and cost comparison

Figure 8(c) illustrates the convergence of the bounds obtained through the
Benders decomposition algorithm. In each iteration, the lower and upper bounds
are adjusted. The algorithm converges at iteration 55. The optimal solution
obtained from the Benders decomposition algorithm is the same as the one
obtained by solving the SP model without decomposition. We observe that while
the subproblems can be solved efficiently due to their smaller number of
variables and parallelization, the master problem requires a substantial
amount of time as more Benders cuts need to be added.

We compare the performance of the proposed model with two models: the expected
entangled pair model and the deterministic model. For the expected entangle
pair model, we consider the fidelity demands as expected values
($\bar{\delta}_{r,c}$) and solve the model in Eqs. (8)-(24) using these
expected values. For the deterministic model, we consider the fidelity demands
as exact values ($\hat{\delta_{r,c}}$) and solve the model in Eqs. (8)-(24)
using these exact values. From Fig. 8(d), it is clear that the proposed model
achieves the minimum cost compared to the expected entangled pair model as the
number of requests increases. In particular, the proposed model can decrease
the total cost by 45.85%, 49.43%, 18.77%, 36.12%, and 39.10% for the number of
requests 1, 2, 3, 4, and 5, respectively. This demonstrates the significant
cost savings that can be achieved by using the proposed model. Nevertheless,
the proposed model performs worse than the deterministic model since the
latter uses exact fidelity demands to achieve the solution, while the former
uses statistical fidelity demands. Nevertheless, the proposed model is more
practical than the deterministic model since, in reality, it is difficult to
know the exact entangled pair demands, which are necessary inputs for the
deterministic model to yield the solution.

##  VII Conclusion

In QCC, users will require quantum computing resources as well as entanglement
routing with a fidelity guarantee for the communication between users and
providers. Therefore, the quantum resource operator, implemented by the
proposed model, can provide quantum computing resources and fidelity-
guaranteed entanglement routing, jointly optimizing them to minimize the
overall cost. We have proposed the joint entangled pair and qubit resource
allocation, and entanglement routing with a fidelity guarantee in the QCC. Our
model is to provision entangled pairs and fidelity-guaranteed entanglement
routing to the quantum network, while qubit resources are provisioned to QCC
providers. We have formulated the resource allocation based on the two-stage
SP model for entangled pairs, fidelity-guaranteed entanglement routing, qubit
resources for quantum circuits, and the minimum waiting time of quantum
circuits, which considers uncertainties of fidelity requirements, qubit
requirements, and circuit waiting time to achieve the optimal total cost. In
addition, we have applied Benders decomposition algorithm to break down the
resource allocation model into sub-models that are solved simultaneously. The
experimental results have indicated that the proposed model achieves the
optimal total cost in terms of entangled pairs, entanglement routing, qubits,
and minimum circuit waiting time, surpassing the expected entangled pair model
by at least 18.77%.

## References

  * [1] IBM Quantum, https://quantum-computing.ibm.com/.
  * [2] Google Quantum AI, https://quantumai.google/.
  * [3] Amazon Braket, https://aws.amazon.com/braket/.
  * [4] Azure Quantum, https://azure.microsoft.com/en-us/products/quantum/.
  * [5] C. H. Bennett and G. Bassard, “Quantum cryptography: public key distribution and coin tossing”, International Conference on Computers, Systems & Signal Processing, pp. 175-179, 1984.
  * [6] C. Li et al., “Effective routing design for remote entanglement generation on quantum networks,” NPJ Quantum Inf., vol. 7, no. 1, pp. 1-12, 2021.
  * [7] Y. Cao, et al., “Hybrid Trusted/Untrusted Relay-Based Quantum Key Distribution Over Optical Backbone Networks,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 9, pp. 2701-2718, 2021.
  * [8] J. Li et al., “Fidelity-Guaranteed Entanglement Routing in Quantum Networks,” in IEEE Transactions on Communications, vol. 70, no. 10, pp. 6748-6763, 2022.
  * [9] S. Shi and C. Qian, “Concurrent entanglement routing for quantum networks: Model and designs,” in Proc. ACM SIGCOMM Conf. Appl., Technol., Architectures, Protocols, 2020, pp. 62–75.
  * [10] A. S. Cacciapuoti et al., “Quantum Internet: Networking Challenges in Distributed Quantum Computing,” in IEEE Network, vol. 34, no. 1, pp. 137-143, 2020.
  * [11] Q. Jia et al., “An improved QKD protocol without public announcement basis using periodically derived basis,” Quantum Inf. Process, vol. 20, no. 2, pp. 1–11, 2021.
  * [12] A. S. Cacciapuoti et al., “When Entanglement Meets Classical Communications: Quantum Teleportation for the Quantum Internet,” in IEEE Transactions on Communications, vol. 68, no. 6, pp. 3808-3833, 2020.
  * [13] R. Van Meter, T. D. Ladd, W. J. Munro and K. Nemoto, “System Design for a Long-Line Quantum Repeater,” in IEEE/ACM Transactions on Networking, vol. 17, no. 3, pp. 1002-1013, 2009.
  * [14] X.-M. Hu et al., “Long-distance entanglement purification for quantum communication,” Phys. Rev. Lett., vol. 126, no. 1, 2021.
  * [15] K. Chakraborty et al., “Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach,” in IEEE Transactions on Quantum Engineering, vol. 1, pp. 1-21, 2020.
  * [16] Y. Zhao and C. Qiao, “Redundant Entanglement Provisioning and Selection for Throughput Maximization in Quantum Networks,” IEEE INFOCOM 2021 - IEEE Conference on Computer Communications, pp. 1-10, 2021.
  * [17] L. Gyongyosi and S. Imre, “Adaptive routing for quantum memory failures in the quantum internet,” Quantum Inf. Process, vol. 18, no. 2, pp. 1–21, 2019.
  * [18] M. Caleffi, “Optimal Routing for Quantum Networks,” IEEE Access, vol. 5, pp. 22299-22312, 2017.
  * [19] F. Hahn, A. Pappa, and J. Eisert, “Quantum network routing and local complementation,” NPJ Quantum Inf., vol. 5, no. 1, pp. 1–7, 2019.
  * [20] N. Ngoenriang et al., “Optimal Stochastic Resource Allocation for Distributed Quantum Computing”, arXiv preprint arXiv:2210.02886, 2022.
  * [21] G. S. Ravi et al., “Quantum computing in the cloud: Analyzing job and machine characteristics,” in IEEE International Symposium on Workload Characterization (IISWC), pp. 39–50, 2021.
  * [22] G. S. Ravi et al., “Adaptive job and resource management for the growing quantum cloud,” in IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 301–312, 2021.
  * [23] C. Cicconetti, M. Conti, and A. Passarella, “Resource allocation in quantum networks for distributed quantum computing,” in IEEE International Conference on Smart Computing (SMARTCOMP), pp. 124–132, 2022.
  * [24] R. Kaewpuang et al., “Stochastic Qubit Resource Allocation for Quantum Cloud Computing”, in Proceedings of IEEE/IFIP Network Operations and Management Symposium, Miami, FL, USA, 8-12 May 2023.
  * [25] S. Chaisiri, B. -S. Lee, and D. Niyato, “Optimization of Resource Provisioning Cost in Cloud Computing,” in IEEE TSC, vol. 5, no. 2, pp. 164-177, 2012.
  * [26] S. Chaisiri, Bu-Sung Lee and D. Niyato, “Optimal virtual machine placement across multiple cloud providers,” 2009 IEEE APSCC, pp. 103-110, 2009.
  * [27] P. C. Humphreys et al. ”Deterministic delivery of remote entanglement on a quantum network.” Nature, vol. 558, no. 7709, pp. 268-286, 2018.
  * [28] M. Caleffi and A. S. Cacciapuoti, “Quantum Switch for the Quantum Internet: Noiseless Communications Through Noisy Channels,” in IEEE Journal on Selected Areas in Communications, vol. 38, no. 3, pp. 575-588, 2020.
  * [29] J.-G. Ren et al., “Ground-to-satellite quantum teleportation,” Nature, vol. 549, no. 7670, pp. 70–73, 2017.
  * [30] A. Dahlberg et al., “A link layer protocol for quantum networks,” in Proc. ACM SIGCOMM Conf. Appl., Technol., Architectures, Protocols, pp. 159–173, 2019.
  * [31] Quantum Fourier Transform by Qiskit, https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html.
  * [32] R. Kaewpuang, M. Xu, S. J. Turner, D. Niyato, H. Yu, D. I. Kim, “Entangled Pair Resource Allocation under Uncertain Fidelity Requirements”, in 2023 Biennial Symposium on Communications (BSC 2023), accepted, 2023.
  * [33] Y. S. Weinstein, M. A. Pravia, E. M. Fortunato, S. Lloyd, and D. G. Cory, “Implementation of the Quantum Fourier Transform,” in Phys. Rev. Lett., vol. 86, pp. 1889-1891, 2001.
  * [34] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information: 10th Anniversary Edition”. in Cambridge: Cambridge University Press, 2010.
  * [35] J. R. Birge, and F. Louveaux, “Introduction to Stochastic Programming,” 2nd ed. Springer, 2011.
  * [36] A.J. Conejo et al., “Decomposition in Linear Programming: Complicating Variables”, in Decomposition Techniques in Mathematical Programming: Engineering and Science Applications, Springer Berlin Heidelberg, 2006, ch. 3, pp. 107-139.
  * [37] General Algebraic Modeling System (GAMS), https://www.gams.com/, 2022.