# Quantum-Assisted Joint Caching and Power Allocation for Integrated
Satellite-Terrestrial Networks

Yu Zhang, Yanmin Gong, Lei Fan, Yu Wang, Zhu Han, , and Yuanxiong Guo Y. Zhang
and Y. Gong are with the Department of Electrical and Computer Engineering,
University of Texas at San Antonio, Texas, 78249, USA. (e-mail<EMAIL_ADDRESS>yanmin.gong@}utsa.edu).L. Fan is with the Department of Engineering
Technology, University of Houston, Houston, TX 77204 USA (e-mail:
lfan8@central.uh.edu).Y. Wang is with Department of Computer and Information
Sciences, Temple University, Philadelphia, Pennsylvania 19122, USA. (e-mail:
wangyu@temple.edu).Z. Han is with the Department of Electrical and Computer
Engineering, University of Houston, Houston, TX 77004 USA, and also with the
Department of Computer Science and Engineering, Kyung Hee University, Seoul
446-701, South Korea. (e-mail: zhan2@uh.edu).Y. Guo is with the Department of
Information Systems and Cyber Security, University of Texas at San Antonio,
Texas, 78249, USA. (e-mail: yuanxiong.guo@utsa.edu).

###### Abstract

Low earth orbit (LEO) satellite network can complement terrestrial networks
for achieving global wireless coverage and improving delay-sensitive Internet
services. This paper proposes an integrated satellite-terrestrial network
(ISTN) architecture to provide ground users with seamless and reliable content
delivery services. For optimal service provisioning in this architecture, we
formulate an optimization model to maximize the network throughput by jointly
optimizing content delivery policy, cache placement, and transmission power
allocation. The resulting optimization model is a large-scale mixed-integer
nonlinear program (MINLP) that is intractable for classical computer solvers.
Inspired by quantum computing techniques, we propose a hybrid quantum-
classical generalized Benders’ decomposition (HQCGBD) algorithm to address
this challenge. Specifically, we first exploit the generalized Benders’
decomposition (GBD) to decompose the problem into a master problem and a
subproblem and then leverage the state-of-art quantum annealer to solve the
challenging master problem. Furthermore, a multi-cut strategy is designed in
HQCGBD to accelerate the solution process by leveraging the quantum advantages
in parallel computing. Simulation results demonstrate the superiority of the
proposed HQCGBD algorithm and validate the effectiveness of the proposed
cache-enabled ISTN architecture.

###### Index Terms:

Integrated satellite-terrestrial network, cache placement, content delivery,
quantum computing, generalized Benders’ decomposition.

##  I Introduction

With the explosion of Internet-of-Things (IoT) devices, it is estimated that
the global mobile data traffic will grow by a factor of nearly 4, reaching 325
EB per month in 2028 [1]. These data will cause an enormous burden on
networks. Furthermore, emerging content-centric communications, such as full-
motion video streaming and online live shows, typically require vast network
throughput [2]. It is challenging for traditional terrestrial networks to meet
these demands due to their limited backhaul capacity. Content caching at the
network edge has been considered as a promising solution that could
significantly alleviate backhaul pressure. Popular contents are proactively
cached at the base stations (BSs), which are close to ground users, and
delivered to the users directly without fetching from the content server via
backhaul link [3]. However, the traditional cache-enabled terrestrial network
is still infeasible in some signal-blocked or shadowed environments due to the
immobility of infrastructure-based BSs [4].

In recent years, low earth orbit (LEO) satellite communication has attracted
growing attention. Since LEO satellites operate from 500 m to 2000 km [5], LEO
satellites can break through geographical restrictions. Consequently, several
major LEO projects have been launched. For example, SpaceX Starlink plans to
launch more than 12,000 LEO satellites to provide seamless global service for
terrestrial users [6]. However, there are two major challenges in the
satellite networks. One challenge is that satellite connections might
experience interruptions due to various factors like atmospheric conditions or
solar interference. The other challenge is that transmitting data over
satellite links is costly. To address these challenges, we not only integrate
caching into satellite networks but also integrate the satellite networks with
terrestrial networks. This cache-enabled integrated satellite-terrestrial
network (ISTN) is envisioned to play an essential role in 6G mobile
communication systems [7]. Resource management becomes a critical problem in
ISTNs due to the limited resources of satellites and edge base stations
compared to remote clouds. There is a rich literature on resource management
in ISTN with the goal of optimizing network throughput [8, 9, 10], energy
efficiency [11, 12, 13], and system latency [14, 15]. Different from the
terrestrial networks, ISTNs comprise not only terrestrial but also satellite
segments. Specifically, satellites serve as the space base stations to
complement the terrestrial edge networks, which are capable of attaining full
coverage. These result in a higher level of collaboration and coordination
among the various components in ISTNs. Thus, resource management optimization
in the area of ISTN needs to be formulated as large-scale mixed-integer
nonlinear programs (MINLPs), which are NP-hard. It is difficult to utilize
classical computing techniques to solve them.

Quantum computing (QC) techniques provide a new promising approach to tackling
this challenge. QC differs from classical computing in that it encodes
information using qubits, representing a superposition of states, rather than
binary bits [16]. Besides, QC utilizes entanglement and quantum tunneling to
find the solution. These features enable quantum computers to simultaneously
explore exponentially large combinations of states, which can solve large-
scale real-world optimization problems more efficiently and faster [16]. There
are two major paradigms in quantum computing: gate-based quantum computing and
adiabatic quantum computing. The gate-based quantum computing utilizes
discrete quantum gate operations to evolve the qubits so that the final state
of the qubits is the desired result. In gate-based quantum computing, we need
to map the problem to an effective quantum algorithm and convert the
instructions into a sequence of low-level quantum gates to operate the qubits.
The main drawback of gate-based quantum computing is that the number of
provided qubits is insufficient for real-world applications. We can only
obtain less than 150 qubits for gate-based quantum computing [17, 18]. Unlike
gate-based quantum computing, we encode the problem into the Hamiltonian of
the quantum system in adiabatic quantum computing. After evolution, we can
obtain the desired solution through the ground state of the quantum system.
Implementing adiabatic quantum computing is hard since the quantum physical
systems are susceptible to non-ideal conditions. Quantum annealing (QA) can be
regarded as a relaxed adiabatic quantum computing that does not necessarily
require universality or adiabaticity [19]. Currently, we can obtain about 5000
qubits for QA from D-wave [20]. With these large numbers of qubits, QA has the
potential to enhance practical applications such as car manufacturing
scheduling [21], RNA folding [22, 23, 24], and portfolio optimization [25].

In this paper, we propose the first QC approach for improving the network
performance in cache-enabled ISTNs. Specifically, we jointly optimize the
content delivery policy, cache placement, and transmission power allocation
aiming at maximizing the network throughput. The formulated optimization
problem is a large-scale MINLP that is NP-hard and difficult for classical
computers to solve. To solve the problem efficiently, we propose a hybrid
quantum-classical generalized Benders’ decomposition (HQCGBD) algorithm. In
particular, we first utilize the generalized Benders’ decomposition (GBD)
algorithm to decompose the MINLP into a master problem with the binary
decision variables (i.e., content delivery policy and cache placement) and a
subproblem with the continuous decision variables (i.e., transmission power).
The subproblem is a convex problem that can be efficiently solved by classical
computers. However, the master problem becomes more time- and memory-consuming
with more Benders’ cuts added to the constraints over iterations for classical
computers [26]. Thus, we further convert the master problem into a quadratic
unconstrained binary optimization (QUBO) formulation that is solvable by QA.
Then, these two problems are iteratively solved until their solutions
converge. Inspired by the parallel processing capability of QC, we further
design a specialized quantum multi-cut strategy to accelerate HQCGBD. Finally,
we evaluate the performance of HQCGBD algorithm for the cache-enabled ISTN on
the D-Wave’s real-world quantum annealer computer [20].

The main contributions of this paper are stated as follows.

  * •

We formulate an optimization problem to maximize the network throughput for a
cache-enabled ISTN system.

  * •

As the formulated model is a large-scale MINLP, which is generally intractable
to classical computers, we propose a HQCGBD algorithm to solve the problem
efficiently by leveraging GBD and QA.

  * •

Motivated by the parallel processing capability of QC, we design a multi-cut
strategy to accelerate the convergence of the proposed HQCGBD algorithm.

  * •

We conduct extensive experiments to demonstrate the superiority of the
proposed solution algorithm compared with the classical computing algorithm
and show the proposed cache-enabled ISTN scheme largely outperforms the
baseline schemes.

The rest of this paper is organized as follows. The related works are
discussed in Section II. In Section III, we introduce the system model and
describe a network throughput maximization formulation for the cache-enabled
ISTN. In Section IV, we present the HQCGBD algorithm to solve the formulated
problem. Section V shows the simulation results. Finally, the conclusion is
given in Section VI.

##  II Related Works

In this section, we discuss the most related prior works from two aspects:
ISTN system and quantum annealing.

###  II-A ISTN System

ISTN is considered as a compelling technology for extending the coverage area
of the existing terrestrial networks, which has attracted increasing attention
from both academia and industry. There is various literature on resource
management in ISTN that aims at optimizing network throughput [8, 9, 10],
energy efficiency [11, 12, 13], and system latency [14, 15]. Han et al. [8]
studied the joint cache placement, LEO satellite and BS clustering, and
multicast beamforming problem aiming at maximizing the network utility. Tran
et al. [9] investigated cache placement, the UAV’s resource allocation, and
trajectory problem in LEO satellite- and cache-assisted unmanned aerial
vehicle (UAV) communications aiming at maximizing the minimum achievable
throughput per ground user. Alsharoa et al. [10] jointly optimized the
resource allocations and the locations of high-altitude platforms (HAPs) to
maximize the users’ throughput. Li et al. [11] formulated a block placement,
power allocation, and cache-sharing decision optimization problem to optimize
the ISTN system energy efficiency. Tang et al. [12] optimized the computation
offloading decisions to minimize the sum energy consumption of ground users.
Ding et al. [13] investigated a joint user association, multi-user multiple
input and multiple output (MU-MIMO) transmit precoding, computation task
assignment, and resource allocation optimization problem to minimize the
weighted sum energy consumption of the ISTN system. Han et al. [14] proposed a
two-timescale learning-based scheme to minimize the overall task offloading
delay by jointly optimizing offloading link selection and bandwidth allocation
decisions for BSs and users. Cui et al. [15] studied a joint task offloading,
communication, and computing resources allocation problem aiming at minimizing
the latency of task offloading and processing. However, most of these studies
in the ISTN systems usually formulate their problems as MINLPs, which are hard
to solve. Thus, they either use heuristics or complex optimization techniques
to tackle them. Inspired by QC, we propose a HQCGBD algorithm to solve these
MINLPs efficiently.

###  II-B Quantum Annealing

Extensive research efforts have been made recently to utilize QA for solving
practical optimization problems [27]. However, QA only accepts a quadratic
polynomial over binary variables, and the cost of using a large number of
ancillary qubits to represent the discretized variables is expensive. Most
prior works formulate the real-world application as a binary quadratic model
(BQM) problem [21, 22, 23, 24, 25] or mixed-integer linear programming (MILP)
problem [28, 29] that is easily converted to the QUBO formulation for QA to
optimize. For instance, Yarkoni et al. [21] minimized the number of color
switches between cars in a paint shop queue by formulating a BQM problem. Fox
et al. [22] optimized codon through a BQM. Mulligan et al. [23] found amino
acid side chain identities and conformations to stabilize a fixed protein
backbone. Fox et al. [24] formulated a BQM to maximize the number of
consecutive base pairs and the average length of the stems. Mugel et al. [25]
proposed a hybrid quantum-classical algorithm for dynamic portfolio
optimization with a minimum holding period. Doan et al. [28] studied MILP
problem in robust fitting by leveraging QA. Dinh et al. [29] formulated the
beam placement in satellite communication as an MILP and designed an efficient
Hamiltonian Reduction method for QA to address this problem efficiently.
However, the BQM and MILP formulations can not capture the complexity of the
actual problem in the ISTN field. To the best of our knowledge, this is the
first work to formulate a MINLP to optimize the network throughput in the
cache-enabled ISTN system and solve it using QC technologies.

##  III System Model And Problem Formulation

In this section, we first introduce the system models. After that, we
formulate an optimization model to jointly optimize the optimal content
delivery policy, cache placement, and transmission power allocation in the
cache-enabled ISTN.

###  III-A System Architecture

As illustrated in Fig. 1, we consider a cache-enabled ISTN that consists of a
content server, a set of single-antenna users
$n\in\mathcal{N}=\\{1,\dots,N\\}$, and a set of base stations (BSs). We denote
the set of BSs as $\mathcal{M}=\mathcal{S}\cup\mathcal{B}$, in which the index
$m\in\mathcal{S}=\\{1,\dots,S\\}$ represents a satellite, and
$m\in\mathcal{B}=\\{S+1,\dots,M\\}$ represents a terrestrial base station
(TBS). The satellites and TBSs, which have limited cache storage onboard,
cooperatively provide content delivery services to the ground users through
satellite-to-user (S2U) and TBS-to-user (T2U) links, respectively. The content
server contains a set of potential user-desired content
$f\in\mathcal{F}=\\{1,\dots,F\\}$. For simplicity, we assume the required
content can be successfully downloaded for each user during the satellite
visibility period. The BSs are connected to the content server via the
limited-capacity backhaul links and proactively cache a portion of the popular
content from the content server and then efficiently serve the ground users.

###  III-B Cache Model

When each user $n\in\mathcal{N}$ submits its content request
$f_{n}\in\mathcal{F}$ to the BS, there are two ways for it to download its
desired content $f_{n}$: if the requested content $f_{n}$ is available in the
cache, the associated BS $m$ will deliver it to user $n$ directly; otherwise,
the associated BS $m$ will fetch the requested content $f_{n}$ from the
content server via the backhaul link and then deliver it to user $n$.

We denote the cache placement matrix for the BSs as
$\mathbf{X}=\\{x_{f,m}\\}^{F\times M}$, where $x_{f,m}\in\\{0,1\\}$.
$x_{f,m}=1$ indicates the content $f$ is placed at the $m$-th BS; otherwise
$x_{f,m}=0$. Considering the limited cache storage capability of each BS, we
have

$\sum_{f\in\mathcal{F}}x_{f,m}d_{f}\leq F_{m},\quad\forall m\in\mathcal{M},$
(1)

where $F_{m}$ is the cache storage capability of BS $m$, and $d_{f}$ is the
data size of content $f$.

Figure 1: The integrated satellite-terrestrial network system

###  III-C Communication Model

Let $\mathbf{Z}=\\{z_{n,m}\\}\in\\{0,1\\}^{N\times M}$ denote the BS service
matrix in which $z_{n,m}=1$ indicates that BS $m$ serves user $n$ and
$z_{n,m}=0$ otherwise. Thanks to the software-defined networking (SDN) and
cloud radio access network technologies, each user can be cooperatively served
by multiple BSs simultaneously [8], which is described as

$\displaystyle\sum_{m\in\mathcal{M}}z_{n,m}\geq 1,\quad\forall
n\in\mathcal{N}.$ (2)

Moreover, we make the assumption that the OFDMA technique is adopted. The
available spectrum of BSs is divided into multiple resource blocks. Each
resource block for BS $m$ has a bandwidth of $B_{m}$ [10, 30]. We also assume
that a user uses only one resource block of an associated BS, and ignore
intra-cell and inter-cell interference since users associated with the same BS
use a different set of orthogonal resource blocks. The maximum number of
associated users for BS $m$ should satisfy

$\displaystyle\sum_{n\in\mathcal{N}}z_{n,m}\leq
I_{m}^{\text{max}}.\quad\forall m\in\mathcal{M},$ (3)

where $I_{m}^{\text{max}}$ is the maximum number of resource blocks for BS
$m$.

The transmission power matrix from BSs to users is denoted as
$\mathbf{P}=[p_{n,m}]_{n\in\mathcal{N},m\in\mathcal{M}}$. When BS $m$ does not
serve user $n$, the corresponding transmission power should be $0$. This can
be modeled as the following constraint:

$\displaystyle z_{n,m}P_{n}^{\text{min}}\leq p_{n,m}\leq
z_{n,m}P_{n}^{\text{max}},\quad\forall n\in\mathcal{N},m\in\mathcal{M},$ (4)

where $P_{n}^{\text{max}}$ and $P_{n}^{\text{min}}$ are the maximum and
minimum transmission power of BS $n$ for each connected device, respectively.

T2U channel model: We model the T2U channel as a Rayleigh channel with
shadowing effect. Let $h_{n,m}$ denote the channel coefficients of the T2U
link from TBS $m\in\mathcal{B}$ to user $n\in\mathcal{N}$. According to [31],
$h_{n,m}$ can be modeled as

$\displaystyle h_{n,m}=\gamma_{n,m}\beta_{n,b}(d_{n,m})^{-\alpha},\quad\forall
n\in\mathcal{N},m\in\mathcal{B},$ (5)

where $\gamma_{n,m}\sim\mathcal{CN}(0,1)$ is a complex Gaussian variable
representing Rayleigh fading, $\beta_{n,m}$ follows log-normal distribution
representing shadowing fading, $d_{n,m}$ is the distance between the TBS and
user, and $\alpha$ represents the path-loss exponent.

S2U channel model: We consider both the large-scale fading and the shadowed-
Rician fading for the S2U channel [32]. We denote the coefficient of S2U
channel connecting satellite $m\in\mathcal{S}$ and user $n\in\mathcal{N}$ as
$h_{n,m}$, which is modeled as

$\displaystyle h_{n,m}=A\exp{(j\psi_{n,m})}+Z\exp{(j\phi_{n,m})},\forall
n\in\mathcal{N},m\in\mathcal{S},$ (6)

where $\psi_{n,m}\in[0,2\pi)$ indicates the stationary random phase and
$\phi_{n,m}$ is the deterministic phase of the LOS component. Here $A$ and $Z$
denote the amplitudes of the scattering and the LOS components, which are
independent stationary random processes following Rayleigh and Nakagami-$m$
distributions, respectively.

Based on Shannon’s theorem, the achievable data transmission rate from BS $m$
to user $n$ can be expressed as

$\displaystyle R_{n,m}=z_{n,m}B_{m}\log_{2}(1+$
$\displaystyle\frac{p_{n,m}G_{n,m}|h_{n,m}|^{2}}{\sigma^{2}}),$
$\displaystyle\quad\forall n\in\mathcal{N},m\in\mathcal{M},$ (7)

where $G_{n,m}$ is the channel gain of BS $m$ towards user $n$, and
${\sigma^{2}}$ represents the additive white Gaussian noise (AWGN). The
instantaneous transmission rate for BS $m$ to deliver content $f_{n}$ to user
$n$ via cache can be calculated as

$\displaystyle Q_{n,m}^{C}=x_{f_{n},m}R_{n,m},\quad\forall
n\in\mathcal{B},m\in\mathcal{M}.$ (8)

On the other hand, the instantaneous transmission rate for BS $m$ to deliver
content $f_{n}$ to user $n$ via backhaul can be written as

$\displaystyle Q_{n,m}^{B}=(1-x_{f_{n},m})R_{n,m},\quad\forall
n\in\mathcal{B},m\in\mathcal{M}.$ (9)

As a result, the total network throughput can be modeled as

$\displaystyle
Q^{T}=\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\left(Q_{n,m}^{C}+\lambda
Q_{n,m}^{B}\right),$ (10)

where $\lambda$ is the trade-off parameter to balance the priorities of
maximizing the total cache and backhaul throughput. Particularly, a small
$\lambda$ implies that maximizing total cache throughput has more priority
than maximizing the total backhaul throughput. In practice, we set
$0<\lambda<1$ to reduce the backhaul pressure.

###  III-D Problem Formulation

In order to maximize the total network throughput that takes into account both
cache and backhaul throughput, we jointly optimize the content delivery
policy, cache placement, and transmission power allocation as

$\displaystyle\max_{\mathbf{X},\mathbf{Z},\mathbf{P}}\quad$ $\displaystyle
Q^{T}$ s.t.
$\displaystyle(\text{C}_{1}):~{}\sum_{f\in\mathcal{F}}x_{f,m}d_{f}\leq
F_{m},\quad\forall m\in\mathcal{M},$
$\displaystyle(\text{C}_{2}):~{}\sum_{n\in\mathcal{N}}p_{n,m}\leq
P_{m}^{\text{max}},\quad\forall m\in\mathcal{M},$
$\displaystyle(\text{C}_{3}):~{}p_{n,m}\leq
z_{n,m}P_{n}^{\text{max}},\quad\forall n\in\mathcal{N},m\in\mathcal{M},$
$\displaystyle(\text{C}_{4}):~{}z_{n,m}P_{n}^{\text{min}}\leq
p_{n,m},\quad\forall n\in\mathcal{N},m\in\mathcal{M},$
$\displaystyle(\text{C}_{5}):~{}\sum_{m\in\mathcal{M}}z_{n,m}\geq
1,\quad\forall n\in\mathcal{N},$
$\displaystyle(\text{C}_{6}):~{}\sum_{n\in\mathcal{N}}z_{n,m}\leq
I_{m}^{\text{max}},\quad\forall m\in\mathcal{M},$
$\displaystyle(\text{C}_{7}):~{}p_{n,m}\geq 0,\quad\forall
n\in\mathcal{N},m\in\mathcal{M},$
$\displaystyle(\text{C}_{8}):~{}x_{f,m}\in\\{0,1\\},\quad\forall
f\in\mathcal{F},m\in\mathcal{M},$
$\displaystyle(\text{C}_{9}):~{}z_{n,m}\in\\{0,1\\},\quad\forall
n\in\mathcal{N},m\in\mathcal{M}.$ (11)

Constraint $(\text{C}_{1})$ ensures that the placed caches for each BS can not
exceed the maximum cache storage. Constraints $(\text{C}_{2})$,
$(\text{C}_{3})$, $(\text{C}_{4})$, and $(\text{C}_{7})$ guarantee the valid
power allocation. Constraint $(\text{C}_{5})$ ensures each user is served by
at least one BS. Constraint $(\text{C}_{6})$ represents the number of
associated users can not exceed the maximum number of resource blocks for each
BS. Finally, constraints $(\text{C}_{8})$ and $(\text{C}_{9})$ show
$\mathbf{X}$ and $\mathbf{Z}$ are binary matrices.

##  IV Solution Methodology

The formulated problem (11) is a large-scale MINLP, which is NP-hard [33]. To
tackle this problem, we propose a novel HQCGBD algorithm. Specifically in
HQCGBD, we first utilize GBD to decompose the problem into a master problem
and a subproblem. On the one hand, the subproblem is a convex problem, which
can be solved efficiently on the classical computer. On the other hand, the
master problem is a large-scale MILP that is intractable for classical
computers. Thus, we convert the master problem into the QUBO formulation,
which can be efficiently solved by the state-of-art quantum annealer.
Moreover, we design a specialized quantum multi-cut strategy to accelerate the
optimization process.

###  IV-A Hybrid Quantum-classical Generalized Benders’ Decomposition

Problem (11) is hard to solve due to the coupling of continuous decision
variables $\mathbf{P}$ with integer decision variables $\mathbf{X}$ and
$\mathbf{Z}$. We first decompose (11) into a master problem and a subproblem.
The master problem only involves the binary optimization decision variables,
while the subproblem only involves the continuous optimization decision
variables. We can obtain a performance upper bound of problem (11) by solving
the subproblem and a performance lower bound of problem (11) by solving the
master problem. Then, problem (11) is iteratively solved until the lower and
upper bounds converge. In order to apply HQCGBD, we first reformulate problem
(11) as

$\displaystyle\min_{\mathbf{X},\mathbf{Z},\mathbf{P}}\quad$
$\displaystyle-Q^{T}$ s.t. $\displaystyle(\text{C}_{1})-(\text{C}_{9}).$ (12)

We describe the details of the subproblem and master problem in the following.

####  IV-A1 Classical Optimization for Subproblem

For the given and fixed binary variables $\mathbf{X}^{(l)}$ and
$\mathbf{Z}^{(l)}$ generated by the master problem at the $(l-1)$-th
iteration, the subproblem can be written as

$\displaystyle\text{(Subproblem)}:\min_{\mathbf{P}}\quad$
$\displaystyle-Q^{T}$ s.t.
$\displaystyle(\text{C}_{2})-(\text{C}_{4}),(\text{C}_{7}).$ (13)

As we can see above, the subproblem has a convex objective function and linear
constraints, so it is convex. Besides, it also satisfies Slater’s conditions
[34], strong duality holds between the subproblem and its dual problem. Thus,
solving its dual problem is equivalent to solving the subproblem. We formulate
its dual problem as

$\displaystyle\max_{\bm{\delta}}~{}\min_{\mathbf{P}}\mathcal{L}$
$\displaystyle(\mathbf{P},\bm{\delta},\mathbf{X}^{(l)},\mathbf{Z}^{(l)})=-Q^{T}-\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\delta_{1,n,m}p_{n,m}$
$\displaystyle+\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\delta_{2,n,m}\big{(}p_{n,m}-z_{n,m}^{(l)}P_{n}^{\text{max}}\big{)}$
$\displaystyle+\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\delta_{3,n,m}\big{(}z_{n,m}^{(l)}P_{n}^{\text{min}}-p_{n,m}\big{)}$
$\displaystyle+\sum_{m\in\mathcal{M}}\delta_{4,m}\big{(}\sum_{n\in\mathcal{N}}p_{n,m}-P_{m}^{\text{max}}\big{)},$
(14)

where $\mathcal{L}$ is the Largangian function of problem (13), $\mathbf{P}$
is the primal variables, and $\bm{\delta}$ is the dual variables associated
with constraints $(\text{C}_{2})-(\text{C}_{4}),(\text{C}_{7})$. This problem
can be efficiently solved by the classical convex programming numerical
solvers such as Mosek [35]. The optimal solutions of the primal variables
$\mathbf{P}$ and dual variables $\bm{\delta}$ are then used as input to the
master problem. Besides, the optimal objective value of problem (13) can be
regarded as the performance upper bound of problem (12).

####  IV-A2 Quantum Optimization for Master Problem

With obtained primary variables $\mathbf{P}^{(l)}$ and dual variables
$\bm{\delta}^{(l)}$ of problem (IV-A1) at the $l$-th iteration, we can
formulate the master as

$\displaystyle\text{(Master problem)}:\min_{\mathbf{X},\mathbf{Z},\phi}\quad$
$\displaystyle\phi$ s.t.
$\displaystyle(\text{C}_{1}),(\text{C}_{5}),(\text{C}_{6}),(\text{C}_{8}),(\text{C}_{9}),$
$\displaystyle(\text{C}_{10}):~{}\phi\geq\mathcal{L}(\mathbf{P}^{(l)},\bm{\delta}^{(l)},\mathbf{X},\mathbf{Z}).$
(15)

Here, $(\text{C}_{10})$ is the Benders’ cut [36]. By adding the Benders’ cut
at each iteration, the search region for the globally optimal solution is
gradually reduced, which accelerates the searching speed [37]. Besides, the
objective value of problem (15) is the performance lower bound of problem (12)
at the $l$-th iteration.

The constructed master problem is a large-scale MILP, which is difficult for
the classical computer to solve. QA technology is a promising approach to
address this challenge. A quantum annealer solves optimization problems
through energy minimization of a physical system. The energy profile of a
quantum system is defined by its Hamiltonian. The system’s initial state is
set to the lowest energy state of the initial Hamiltonian and then annealed
until the system’s final state corresponds to the desired solution. The
Hamiltonian at the end of the annealing process can be derived from the
following model:

$\displaystyle
f_{Q}(\mathbf{x})=\sum_{i=1}^{K}Q_{ii}x_{i}+\sum_{i=1}^{K}\sum_{j=1}^{K}Q_{ij}x_{i}x_{j}=\mathbf{x}^{\intercal}\mathbf{Q}\mathbf{x},$
(16)

where $f_{Q}:\\{0,1\\}^{k}\rightarrow\mathbb{R}$ represents a quadratic
polynomial over binary variables, $\mathbf{x}=[x_{1},\dots,x_{k}]$ are binary
variables, and $\mathbf{Q}\in\mathbb{R}^{K\times K}$ is an upper triangular
matrix representing the corresponding cost coefficient of $x_{i}x_{j}$ [38].

A well-known approach for representing optimization problems in quantum
annealing is to use the QUBO, which solves a problem of the formulation:

$\displaystyle\min_{\mathbf{x}\in\\{0,1\\}^{K}}f_{Q}(\mathbf{x}).$ (17)

Note that the master problem (15) has a structure similar to an integer linear
program (ILP) but is not in the QUBO format. In order to leverage the state-
of-art QA, we convert the master problem into the QUBO formulation as follows
[39]:

Objective function reformulation: Since the QA only accepts a quadratic
polynomial over binary variables, we first approximate the continuous variable
$\phi$ using a binary vector $\mathbf{w}$ with the length of $U$ bits. The
QUBO formulation of objective function (15) can be written as

$\displaystyle\bar{\phi}=$
$\displaystyle\sum_{i=-\underline{u}_{+}}^{\overline{u}_{+}}w_{(i+\underline{u}_{+})}2^{i}w_{(i+\underline{u}_{+})}-$
$\displaystyle\sum_{j=0}^{\overline{u}_{-}}w_{(j+1+\underline{u}_{+}+\overline{u}_{+})}2^{j}w_{(j+1+\underline{u}_{+}+\overline{u}_{+})}=\bar{\phi}(\mathbf{w}),$
(18)

where $U=1+\underline{u}_{+}+\overline{u}_{+}+\overline{u}_{-}$. Here,
$\overline{u}_{-},\overline{u}_{+},\underline{u}_{+}$ represent the number of
bits that are assigned to represent the negative integer, positive integer,
and positive decimal part of $\phi$, respectively.

Constraints reformulation: After reformulating the objective function in (15),
we can obtain a constraint ILP master problem, which is still not the QUBO
formulation. We need to further reformulate the constrained ILP master problem
as unconstrained QUBO by using penalties. According to the constraint-penalty
pair principle in [39], we convert the constraints
$(\text{C}_{1})$,$(\text{C}_{5})$,$(\text{C}_{6})$, and $(\text{C}_{10})$ as
follows:

$\displaystyle
f_{Q}^{(\text{C}_{1})}(\mathbf{X},\mathbf{s})=\sum_{m\in\mathcal{M}}\xi_{1,m}(\sum_{f\in\mathcal{F}}x_{f,m}d_{f}-F_{m}+\sum_{l=0}^{\overline{l}_{1,m}}2^{l}{s}_{1,m})^{2},$
(19)

where
$\overline{l}_{1,m}=\big{\lceil}\log_{2}\big{(}\min_{\mathbf{X}}(F_{m}-\sum_{f\in\mathcal{F}}x_{f,m}d_{f})\big{)}\big{\rceil}$.

$\displaystyle
f_{Q}^{(\text{C}_{5})}(\mathbf{Z},\mathbf{s})=\sum_{n\in\mathcal{N}}\xi_{2,n}\big{(}1-\sum_{m\in\mathcal{M}}z_{n,m}+\sum_{l=0}^{\overline{l}_{2,n}}2^{l}{s}_{2,n}\big{)}^{2},$
(20)

where
$\overline{l}_{2,n}=\big{\lceil}\log_{2}\big{(}\min_{\mathbf{Z}}(\sum_{m\in\mathcal{M}}z_{n,m}-1)\big{)}\big{\rceil}.$

$\displaystyle
f_{Q}^{(\text{C}_{6})}(\mathbf{Z},\mathbf{s})=\sum_{m\in\mathcal{M}}\xi_{3,m}\big{(}\sum_{n\in\mathcal{N}}z_{n,m}-I_{m}^{\text{max}}+\sum_{l=0}^{\overline{l}_{3,m}}2^{l}{s}_{3,m}\big{)}^{2},$
(21)

where
$\overline{l}_{3,m}=\big{\lceil}\log_{2}\big{(}\min_{\mathbf{Z}}(I_{m}^{\text{max}}-\sum_{n\in\mathcal{N}}z_{n,m})\big{)}\big{\rceil}.$

$\displaystyle
f_{Q}^{(\text{C}_{16})}(\mathbf{X},\mathbf{Z},\mathbf{w},\mathbf{s})=$
$\displaystyle\xi_{4}\big{(}\mathcal{L}(\mathbf{P}^{(l)},\bm{\delta}^{(l)},\mathbf{X},\mathbf{Z})-\bar{\phi}(\mathbf{w})$
$\displaystyle+\sum_{l=0}^{\overline{l}_{4}}2^{l}{s}_{4}\big{)}^{2},$ (22)

where
$\overline{l}_{4}=\big{\lceil}\log_{2}\big{(}\min_{\mathbf{w},\mathbf{Z}}\big{(}\bar{\phi}(\mathbf{w})-\mathcal{L}(\mathbf{P}^{(l)},\bm{\delta}^{(l)})\big{)}\big{)}\big{\rceil}$.

Here, $\bm{s}$ is the binary slack variables, $\bar{\bm{l}}$ is the upper
bound of the number of slack variables, and $\bm{\xi}$ is the penalty
parameters which are defined according to [40]. Then, the master problem can
be stated in the QUBO formulation as

$\displaystyle\min_{\mathbf{X},\mathbf{Z},\mathbf{w},\mathbf{s}}\quad$
$\displaystyle\bar{\phi}(\mathbf{w})+f_{Q}^{(\text{C}_{1})}(\mathbf{X},\mathbf{s})+f_{Q}^{(\text{C}_{5})}(\mathbf{Z},\mathbf{s})$
$\displaystyle+f_{Q}^{(\text{C}_{6})}(\mathbf{Z},\mathbf{s})+f_{Q}^{(\text{C}_{16})}(\mathbf{X},\mathbf{Z},\mathbf{w},\mathbf{s}).$
(23)

####  IV-A3 Overall Algorithm

The overall HQCGBD algorithm is summarized in Algorithm 1. The algorithm
contains an iterative procedure. First of all, we set the iteration index $l$
to 1 and the maximum number of iterations as $L^{\text{max}}$ and initialize
the binary variables $\mathbf{X}$ and $\mathbf{Z}$. In the $l$-th iteration,
we fix the binary variables $\mathbf{X}^{(l)}$ and $\mathbf{Z}^{(l)}$ and
solve the subproblem using the classical computer (Line 2). We add the
obtained Benders’ cut to the master problem and update the performance upper
bound $\text{UB}^{(l)}$ by the optimal solution of the subproblem (Line 3-6).
Then, we set the appropriate penalties and reformulate the master problem into
the QUBO formulation (Line 7-8). We utilize the quantum computer to solve the
QUBO master problem and update the performance lower bound $\text{LB}^{(l)}$
(Line 9-11). This iteration procedure stops until the approximation gap
$|\frac{\text{UB}^{(l)}-\text{LB}^{(l)}}{\text{UB}^{(l)}}|$ is within a preset
threshold $\epsilon$ or the maximal iteration index $L^{\text{max}}$ is
reached

###  IV-B Multi-cut Strategy

(a)

(b)

Figure 2: An overview of (a) CBD and (b) Multi-Cut HQCGBD

The main bottleneck of classical Benders’ decomposition (CBD) is the time
consumed by solving the master problems, which occupies over $90\%$ total
optimization time [41]. As shown in Fig. LABEL:sub@fig:cbd, classical
computers generate just one Benders cut at an iteration. However, QA utilizes
qubits that can explore many combinations of quantum states simultaneously by
leveraging the superposition of quantum states [16]. This endows quantum
computers the powerful parallel computing capacity. Thanks to this feature, we
can observe multiple feasible solutions at the end of QA. Thus, quantum
computers can potentially accelerate the convergence of the GBD compared to
classical computers. In Fig. LABEL:sub@fig:MQBC, we demonstrate the basic idea
of multi-cut HQCGBD. In multi-cut HQCGBD, solving a master problem can obtain
multiple feasible solutions. We select the top $\rho$ feasible solutions for
the classical computers to generate multiple Benders’ cuts in parallel.

The details of the multi-cut HQCGBD are summarized in Algorithm 2. The main
difference between Algorithm 1 and Algorithm 2 is that a set of feasible
binary variables $\mathcal{X}$ is generated by solving the master problem on
the quantum computer. For each feasible solution, we can solve a subproblem on
the classical computer to generate a Benders’ cut. Then, all Benders’ cuts are
added to the master problem for the quantum computer to solve. This iteration
procedure continues until the upper bound and lower bound converge.

Algorithm 1 The Proposed HQCGBD Algorithm

0: Iteration index $l=1$, maximum iteration number $L^{\text{max}}$, iteration
threshold $\epsilon$, $UB^{(0)}=+\infty$, and $LB^{(0)}=-\infty$. Initialize
$\mathbf{X}^{(0)},\mathbf{Z}^{(0)}$.

1: while
$|\frac{\text{UB}^{(l-1)}-\text{LB}^{(l-1)}}{\text{UB}^{(l-1)}}|>\epsilon$ or
$l<L^{\text{max}}$ do

2: Fix $\mathbf{X}$, $\mathbf{Z}$ as $\mathbf{X}^{(l-1)},\mathbf{Z}^{(l-1)}$,
and solve the subproblem using a standard convex solver in the classical
computer

3: Obtain the optimal solution $\mathbf{P}^{(l)}$ and $-Q^{\text{T}(l)}$

4: Obtain the Benders’ cut $C$

5: Update $\text{UB}^{(l)}=\min\\{\text{UB}^{(l-1)},-Q^{\text{T},(l)}\\}$

6: Add the Benders cut $C$ to the master problem

7: Set appropriate penalty numbers or arrays $\bm{\xi}$

8: Reformulate both objective and constraints in the master problem and
construct the QUBO formation by using corresponding rules, i.e., (19)-(23)

9: Solve the master problem by the quantum computer

10: Obtain optimal solution $\mathbf{X}^{(l)}$, $\mathbf{Z}^{(l)}$, and
$\phi^{(l)}$

11: Update $\text{LB}^{(l)}=\phi^{(l)}$

12: Set $l$ = $l$ \+ 1

13: end while

13: Optimal $\mathbf{X}^{*},\mathbf{Z}^{*},\mathbf{P}^{*}$.

Algorithm 2 The Proposed Multi-Cut HQCGBD Algorithm

0: Iteration index $l=1$, maximum iteration number $L^{\text{max}}$, iteration
threshold $\epsilon$, $UB^{(0)}=+\infty$, and $LB^{(0)}=-\infty$. Initialize
$\rho$ feasible values as
$\mathcal{X}^{(0)}=\\{\mathbf{X}^{(0)}_{i},\mathbf{Z}^{(0)}_{i}\\}_{i=1}^{\rho}$.

1: while
$|\frac{\text{UB}^{(l-1)}-\text{LB}^{(l-1)}}{\text{UB}^{(l-1)}}|>\epsilon$ or
$l<L^{\text{max}}$ do

2: for $\\{\mathbf{X},\mathbf{Z}\\}\in\mathcal{X}^{(l-1)}$ do

3: Fix $\mathbf{X}$ and $\mathbf{Z}$, and solve the subproblem using a
standard convex solver in the classical computer

4: Obtain the optimal solution $\mathbf{P}^{(l)}$ and $-Q^{\text{T},(l)}$

5: Obtain the Benders’ cut $C$

6: Add the Benders’ cut $C$ to the master problem

7: Update $\text{UB}^{(l)}=\min\\{\text{UB}^{(l-1)},-Q^{\text{T},(l)}\\}$

8: end for

9: Set appropriate penalty numbers or arrays $\bm{\xi}$

10: Reformulate both objective and constraints in the master problem and
construct the QUBO formation by using corresponding rules, i.e., (19)-(23)

11: Solve the master problem by the quantum computer

12: Obtain $\rho$ feasible solutions
${\mathcal{X}}^{(l)}=\\{\mathbf{X}^{(l)}_{i},\mathbf{Z}^{(l)}_{i}\\}_{i=1}^{\rho}$
and $\\{\phi^{(l)}_{i}\\}_{i=1}^{\rho}$

13: Update $\text{LB}^{(l)}=\min\\{\phi^{(l)}_{i}\\}_{i=1}^{\rho}$

14: Set $l$ = $l$ \+ 1

15: end while

15: Optimal $\mathbf{X}^{*},\mathbf{Z}^{*},\mathbf{P}^{*}$.

##  V Numerical Experiments

In this section, we evaluate the performance of our proposed HQCGBD algorithm
and cache-enabled ISTN architecture. Since quantum computing resource is still
extremely expensive, we only conduct a small-scale setting that could be
solved in fewer than 1000 iterations, but our results show how promising this
technology could be in the future. Both HQCGBD and CBD are implemented in
Python 3.7. Specifically, we utilize the Mosek [35] to solve the classical
convex problems and Gurobi [42] to solve classical MILP problems on a desktop
computer with a 3.2 $\mathrm{G}\mathrm{H}\mathrm{z}$ $\text{Intel}^{\text{R}}$
$\text{Core}^{\text{TM}}$ i7-8700 CPU and 16 GB of RAM. The HQCGBD master
problems are solved by the D-Wave hybrid quantum computer, which has over
5,000 physical qubits, and 35,000 couplers based on the Pegasus topology [20].

###  V-A Simulation Setup

In our simulation, we consider a cache-enabled ISTN system with one TBS placed
in the center and 10 ground users that are uniformly distributed within an
area of $1000\times 1000$ $\mathrm{m}^{2}$, excluding an inner circle of 50
$\mathrm{m}$ radius around the TBS. In order to meet the quality of service
(QoS) requirement, one LEO satellite cooperatively provides the content
delivery service to the ground users. The ISTN system operates at
2$\mathrm{G}\mathrm{H}\mathrm{z}$ with a bandwidth of
10$\mathrm{M}\mathrm{H}\mathrm{z}$. For terrestrial communication, the path-
loss exponent $\alpha$ is set to $3.7$ [43], and the log-normal shadowing
parameter is set to be 8$\mathrm{d}\mathrm{B}$. The small-scale fading over
the terrestrial channel is modeled as the normalized Rayleigh fading. For
satellite communication, the path-loss is modeled by
$L_{p}(dB)=92.44+20\log_{10}{d}+20\log_{10}(f)$, where $f$ is the operating
frequency in $\mathrm{G}\mathrm{H}\mathrm{z}$, and $d$ is the distance between
the satellite and user in kilometers, which is determined by the satellite
altitude and elevation angle [44]. We set the total attenuation caused by
rain, gas, clouds, and scintillation as $5.2$$\mathrm{d}\mathrm{B}$ [45], and
the additional losses from polarization and antenna misalignment as
0.1$\mathrm{d}\mathrm{B}$ and 0.35$\mathrm{d}\mathrm{B}$, respectively [46].
The small-scale fading over the satellite channel is modeled as Rician fading.

We assume the popularity of $F$ content follows a Zipf distribution [47].
Therefore, the probability of user $n$ to require $f$-th content is given by
$p_{f_{n}}=\frac{f_{n}^{-\kappa}}{\sum_{j=1}^{F}j^{-\kappa}}$, where $\kappa$
is the skewness parameter. In general, large $\kappa$ means more user requests
are concentrated on less popular content. Moreover, we set the penalty
parameter $\lambda$ as 0.6 by default. The rest of our simulation parameters,
unless otherwise stated, are given in Table I.

TABLE I: Simulation Parameters

Parameters Values Satellite altitude $H_{s}$ 1000$\mathrm{k}\mathrm{m}$
Transmission power of TBS $P_{b}^{\text{max}}$
42$\mathrm{d}\mathrm{B}\mathrm{m}$ Transmission power of satellite
$P_{s}^{\text{max}}$ 43$\mathrm{d}\mathrm{B}\mathrm{m}$ The antenna gain of
TBS 10$\mathrm{d}\mathrm{B}\mathrm{i}$ The antenna gain of satellite
35$\mathrm{d}\mathrm{B}\mathrm{i}$ Number of content 5 Size of each content
30$\mathrm{M}\mathrm{b}$ The cache storage capability of BS
30$\mathrm{M}\mathrm{b}$ Zipf parameter $\kappa$ 0.7 The spectral density of
noise -174$\mathrm{d}\mathrm{B}\mathrm{m}\mathrm{/}\mathrm{H}\mathrm{z}$
Elevation angle $\theta$ 60°

To evaluate the proposed schemes’ performance, we consider two prevalent
caching strategies in ISTNs as baselines [48, 8, 49, 50, 51, 52]. Besides, we
also design a non-cooperative ISTN scheme as Baseline 3 to show the advantages
of cooperation in the cache-enabled ISTN. The three baselines are as follows:

  1. 1.

Baseline 1 - Cooperative random caching: Similar to [48, 8, 49], TBSs and
satellites cache the content randomly with equal probabilities regardless of
content popularity distribution.

  2. 2.

Baseline 2 - Cooperative popularity-aware caching: TBSs and satellites cache
the most popular content until their storage is full [50, 51, 52]. In this
caching scheme, the cached content in the TBS and satellite are the same since
their cache sizes are the same.

  3. 3.

Baseline 3 - Non-cooperative caching: In this scheme, TBSs and satellites
provide the content delivery service to users without cooperation. Each user
is only associated with one BS.

(a) The upper and lower bounds of each iteration.

(b) Approximation gap of each iteration.

Figure 3: Convergence of the proposed HQCGBD algorithm.

###  V-B Comparsion of Proposed HQCGBD and CBD Algorithm

In this part, we first evaluate the convergence process of the proposed HQCGBD
algorithm. Fig. 3 shows the convergence of our 5-cut HQCGBD algorithm. Fig.
LABEL:sub@fig:convergence shows that the difference between UB and LB
decreases and finally converges after 237 iterations. Fig. LABEL:sub@fig:gap
illustrates the corresponding approximation gap decreases w.r.t. the iteration
number. In practice, to speed up the process, we can terminate the algorithm
earlier to obtain an approximately optimal solution when the approximation gap
is within a threshold $\epsilon$.

Figure 4: The convergence performances of CBD and different multi-cut HQCGBD strategies. TABLE II: Performance comparison between CBD with different multi-cut HQCGBD Algorithm |  Iterations | Solver accessing time ($\mathrm{m}\mathrm{s}$)
---|---|---
|  |  Max. |  Min. |  Mean. |  Std. |  Total
CBD |  828 | 92.21 | 0.59 | 35.87 | 18.58 |  29699.74
Single-cut HQCGBD |  768 | 3.21 | 1.58 | 2.26 | 0.79 |  1738.65
3-cut HQCGBD |  351 | 3.21 | 1.58 | 2.24 | 0.78 |  787.35
5-cut HQCGBD |  237 | 3.21 | 1.58 | 2.12 | 0.75 |  502.41

In Fig. 4, we further compare the convergence of CBD and different multi-cut
HQCGBD strategies. We can observe that the values of the lower bounds (i.e.,
the objective values of master problems) keep increasing while the upper
bounds (i.e., the objective values of subproblems) keep decreasing until
convergence. Specifically, the single-cut HQCGBD and CBD need 768 and 828
iterations to converge, respectively. This result verifies that our proposed
single-cut HQCGBD algorithm is mathematically consistent with the CBD
algorithm. Essentially, if the CBD algorithm can solve a problem, our proposed
single-cut HQCGBD algorithm can reach the same result at least. Furthermore,
we can see that the lower bounds of CBD and single-cut HQCGBD increase very
slowly compared to the multi-cut HQCGBD strategies. The reason is that we can
improve the obtained lower bounds through the multi-cut strategies. This
figure also shows the superiority of the 3-cut and 5-cut HQCGBD strategies,
which can reduce the number of required iterations by $57.60\%$ and $71.37\%$,
respectively.

Figure 5: The cumulative solver accessing time of master problems for CBD and
different multi-cut HQCGBD strategies.

Next, we compare the running time of our proposed algorithm and CBD. Although
each iteration of HQCGBD requires processing multiple subproblems, the
complexity of each subproblem is the same as that of the subproblem in CBD,
and they can be executed in parallel. Therefore, we only compare the
performances of CBD and different multi-cut HQCGBD strategies regarding the
real solver accessing time of the master problems111The solver accessing time
is the accessing time of QPU solver and local solver without considering other
overheads, such as variables setup latency, network transmission latency,
etc.. As illustrated in Fig. 5, the single-cut HQCGBD master problem’s
cumulative solver accessing time increases linearly w.r.t. the iteration
number, while the CBD master problems’ cumulative solver accessing time
increases quadratically w.r.t. the iteration number. Before the $10$-th
iteration, the CBD outperforms the single-cut HQCGBD. However, the single-cut
HQCGBD performs better and better when the master problem becomes more and
more computation-intensive as we keep adding Benders’ cuts to the master
problem in each iteration. The computational time of the master problems on
the quantum computers is less than that spend on the classical computers. This
result demonstrates that quantum computers outperform classical computers in
solving large-scale MILP problems. Specifically, the proposed single-cut,
3-cut, and 5-cut HQCGBD can save up to $94.14\%$, $97.34\%$, and $98.31\%$
solver accessing time of the master problem compared with CBD, respectively.

We also show the performance details of CBD and multi-cut HQCGBD strategies in
Table II. We can observe that the multi-cut HQCGBD strategies have a stable
computation performance as they have a much smaller standard deviation of the
master problem’s solver accessing time than the CBD. In summary, the proposed
multi-cut HQCGBD outperforms CBD in terms of both convergence speed of
iterations and cumulative master problems’ solver accessing time.

###  V-C Impact of Parameter $\lambda$

(a) Network throughput

(b) Total cache throughput

(c) Total backhaul throughput

Figure 6: The impact of $\lambda$ on the system performance.

In Fig. 6, we study how the trade-off parameter $\lambda$ affects the system
performance in terms of the network throughput $Q^{T}$, total cache throughput
$\sum_{f\in\mathcal{F}}\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}Q_{n,m,f}^{C}$,
and total backhaul throughput
$\sum_{f\in\mathcal{F}}\sum_{n\in\mathcal{N}}\sum_{m\in\mathcal{M}}\lambda
Q_{n,m,f}^{B}$. To that end, we increase the penalty parameter $\lambda$ from
0.5 to 0.8. From Fig. LABEL:sub@fig:tn, we can observe that the proposed ISTN
scheme performs better than the other three baselines. Meanwhile, as $\lambda$
increases, the network throughput of the non-cooperative caching ISTN scheme
is first larger and then smaller than the cooperative popularity-aware caching
ISTN scheme. Fig. LABEL:sub@fig:tc and Fig. LABEL:sub@fig:tb further
demonstrate the details. Specifically, when $\lambda$ is below 0.6, the weight
of the total cache throughput is relatively large. Due to the cache
optimization, the cooperative popularity-aware caching ISTN scheme outperforms
the non-cooperative caching ISTN scheme. However, the total backhaul
throughput becomes dominant when $\lambda$ is larger. The non-cooperative
caching ISTN scheme decreases the total cache throughput to increase the total
backhaul throughput. The cooperative popularity-aware caching ISTN scheme
sacrifices less total cache throughput to improve the total backhaul
throughput due to the cooperative ISTN. Fig. LABEL:sub@fig:tc also shows that
our proposed ISTN scheme outperforms the cooperative random and popularity-
aware caching ISTN schemes in the total cache throughput. Although the non-
cooperative caching ISTN scheme has a slightly larger total cache throughput,
the proposed ISTN scheme has a much higher total backhaul throughput as shown
in Fig. LABEL:sub@fig:tb.

###  V-D Impact of Satellite Transmission Power

(a) Network throughput

(b) Total cache throughput

(c) Total backhaul throughput

Figure 7: The impact of satellite transmission power on the system
performance.

(a) Network throughput

(b) Total cache throughput

(c) Total backhaul throughput

Figure 8: The impact of TBS resource blocks on the system performance.

In this part, we investigate how the network throughput, total cache, and
total backhaul throughput change as the satellite transmission power
increases. As demonstrated in Fig. LABEL:sub@fig:pn, the network throughput
increases as the satellite transmission power increases. It also shows that
our proposed ISTN scheme achieves the highest network throughput than the
other three baselines. The network throughput of the cooperative random
caching ISTN scheme performs the worst. The reason is that the cooperative
random caching ISTN scheme can not fully exploit the satellite cache capacity.
As shown in Fig. LABEL:sub@fig:pc and Fig. LABEL:sub@fig:pb, the proposed ISTN
scheme can better utilize the cache storages of the TBSs and satellites and
efficiently reduce the backhaul pressure in this case. Without cache placement
optimization, the cooperative random caching and cooperative popularity-aware
caching ISTN schemes push more throughput to backhaul traffic to achieve
better network throughput performance. Although our proposed ISTN scheme has a
similar total cache throughput to the non-cooperative caching ISTN scheme, our
proposed ISTN scheme has a much higher total backhaul throughput. In general,
the proposed ISTN has the ability to effectively leverage the power of
satellite transmission by balancing the total cache and backhaul throughput.

###  V-E Impact of Resource Blocks

In this part, we compare the network throughput, total cache, and backhaul
throughput of our proposed ISTN scheme with the three baseline schemes
regarding the TBS resource blocks. As shown in Fig. LABEL:sub@fig:an, our
proposed ISTN scheme has the highest network throughput than the other three
baselines in the different numbers of TBS resource blocks. Besides, the
network throughput of all schemes increases as the number of resource blocks
at TBS increases, except that the network throughput of the non-cooperative
caching ISTN scheme remains stable. The reason is that the transmission power
of TBS is optimally allocated to each associated user. With more resource
blocks available, TBSs can allocate their transmission powers more flexibly to
increase the network throughput. However, the non-cooperative caching ISTN
scheme does not have this flexibility since each user is served by only one
BS. From Fig. LABEL:sub@fig:ac, we can observe that the total cache throughput
of the popularity-aware caching ISTN scheme increases as the number of
resource blocks increases, and the cooperative random caching ISTN scheme
performs the worst. Fig. LABEL:sub@fig:ab illustrates that the total backhaul
throughput of the proposed ISTN scheme and the cooperative random caching ISTN
scheme increases when the number of TBS resource blocks increases while the
total backhaul throughput of the cooperative popularity-aware caching ISTN
scheme keeps decreasing. This is because the cooperative popularity-aware
caching ISTN scheme can not fully exploit the BS caching capacity with a small
number of TBS resource blocks. Since the total cache throughput has a higher
weight, the cooperative popularity-aware caching ISTN scheme needs to shift
the network throughput from the backhaul link to the cache to increase the
network throughput. Therefore, considering the trade-off between the total
cache and backhaul throughput, our proposed ISTN scheme has the best
performance in different numbers of TBS resource blocks.

##  VI Conclusion

In this paper, we have investigated the problem of optimizing content delivery
services to terrestrial users in ISTN. We have formulated a MINLP to jointly
optimizes the content delivery policy, cache placement, and transmission power
allocation for maximizing the network throughput and proposed a hybrid
quantum-classical solution method called HQCGBD to solve it. Furthermore, we
have designed a specialized quantum multi-cut strategy to accelerate the
convergence speed of HQCGBD. Due to the limited number of qubits in the
current D-wave system, we conduct the experiments in a small-scale setting as
a proof of concept. However, even in this setting, numerical results
demonstrate that our proposed multi-cut HQCGBD can reduce both the required
iteration numbers to achieve convergence and solver accessing time without
losing optimality. This work is our first attempt to leverage quantum
computing techniques for optimizing cache placement in ISTNs. In the future,
we will extend our work to a setting of multi-timescale systems and
investigate cache placement and resource allocation in ISTNs. Since the
proposed algorithm can efficiently solve large-scale MINLPs, it holds great
promise for various ISTN applications, e.g., routing and scheduling
optimization problems. With the rapid development of quantum computers and
increasing number of qubits [53], we believe that the proposed quantum-
assisted optimization can play a crucial role in the ISTN field.

## References

  * [1] “Mobile data traffic outlook,” November 2022. [Online]. Available: https://www.ericsson.com/en/reports-and-papers/mobility-report/dataforecasts/mobile-traffic-forecast
  * [2] H. Li, K. Ota, and M. Dong, “ECCN: orchestration of edge-centric computing and content-centric networking in the 5G radio access network,” _IEEE Wireless Communications_ , vol. 25, no. 3, pp. 88–93, 2018.
  * [3] Z. Piao, M. Peng, Y. Liu, and M. Daneshmand, “Recent advances of edge cache in radio access networks for internet of things: techniques, performances, and challenges,” _IEEE Internet of Things Journal_ , vol. 6, no. 1, pp. 1010–1028, 2018.
  * [4] K. An, Y. Li, X. Yan, and T. Liang, “On the performance of cache-enabled hybrid satellite-terrestrial relay networks,” _IEEE Wireless Communications Letters_ , vol. 8, no. 5, pp. 1506–1509, 2019.
  * [5] Y. Su, Y. Liu, Y. Zhou, J. Yuan, H. Cao, and J. Shi, “Broadband LEO satellite communications: Architectures and key technologies,” _IEEE Wireless Communications_ , vol. 26, no. 2, pp. 55–61, 2019.
  * [6] A. U. Chaudhry and H. Yanikomeroglu, “Free space optics for next-generation satellite networks,” _IEEE Consumer Electronics Magazine_ , vol. 10, no. 6, pp. 21–31, 2020.
  * [7] X. Zhu and C. Jiang, “Integrated satellite-terrestrial networks toward 6G: Architectures, applications, and challenges,” _IEEE Internet of Things Journal_ , vol. 9, no. 1, pp. 437–461, 2021.
  * [8] D. Han, W. Liao, H. Peng, H. Wu, W. Wu, and X. Shen, “Joint cache placement and cooperative multicast beamforming in integrated satellite-terrestrial networks,” _IEEE Transactions on Vehicular Technology_ , vol. 71, no. 3, pp. 3131–3143, 2021.
  * [9] D.-H. Tran, S. Chatzinotas, and B. Ottersten, “Satellite-and cache-assisted uav: A joint cache placement, resource allocation, and trajectory optimization for 6G aerial networks,” _IEEE Open Journal of Vehicular Technology_ , vol. 3, pp. 40–54, 2022.
  * [10] A. Alsharoa and M.-S. Alouini, “Improvement of the global connectivity using integrated satellite-airborne-terrestrial networks with resource optimization,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 8, pp. 5088–5100, 2020.
  * [11] J. Li, K. Xue, D. S. Wei, J. Liu, and Y. Zhang, “Energy efficiency and traffic offloading optimization in integrated satellite/terrestrial radio access networks,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 4, pp. 2367–2381, 2020.
  * [12] Q. Tang, Z. Fei, B. Li, and Z. Han, “Computation offloading in LEO satellite networks with hybrid cloud and edge computing,” _IEEE Internet of Things Journal_ , vol. 8, no. 11, pp. 9164–9176, 2021.
  * [13] C. Ding, J.-B. Wang, H. Zhang, M. Lin, and G. Y. Li, “Joint optimization of transmission and computation resources for satellite and high altitude platform assisted edge computing,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 2, pp. 1362–1377, 2021.
  * [14] D. Han, Q. Ye, H. Peng, W. Wu, H. Wu, W. Liao, and X. Shen, “Two-timescale learning-based task offloading for remote IoT in integrated satellite-terrestrial networks,” _IEEE Internet of Things Journal_ , 2023.
  * [15] G. Cui, P. Duan, L. Xu, and W. Wang, “Latency optimization for hybrid GEO-LEO satellite assisted IoT networks,” _IEEE Internet of Things Journal_ , 2022.
  * [16] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke _et al._ , “Noisy intermediate-scale quantum algorithms,” _Reviews of Modern Physics_ , vol. 94, no. 1, p. 015004, 2022.
  * [17] “Highlights of the ibm quantum summit 2022,” April 2023. [Online]. Available: https://www.ibm.com/quantum
  * [18] “Amazon braket - accelerate quantum computing research,” April 2023. [Online]. Available: https://https://aws.amazon.com/braket/
  * [19] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,” _Physical Review E_ , vol. 58, no. 5, p. 5355, 1998.
  * [20] “D-wave hybrid solver service: An overview,” 2023. [Online]. Available: https://www.dwavesys.com/resources/white-paper/d-wave-hybrid-solver-service-an-overview/
  * [21] S. Yarkoni, A. Alekseyenko, M. Streif, D. Von Dollen, F. Neukart, and T. Bäck, “Multi-car paint shop optimization with quantum annealing,” in _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2021, pp. 35–41.
  * [22] D. M. Fox, K. M. Branson, and R. C. Walker, “mRNA codon optimization with quantum computers,” _PloS one_ , vol. 16, no. 10, p. e0259101, 2021.
  * [23] V. K. Mulligan, H. Melo, H. I. Merritt, S. Slocum, B. D. Weitzner, A. M. Watkins, P. D. Renfrew, C. Pelissier, P. S. Arora, and R. Bonneau, “Designing peptides on a quantum computer,” _BioRxiv_ , p. 752485, 2019.
  * [24] D. M. Fox, C. M. MacDermaid, A. M. Schreij, M. Zwierzyna, and R. C. Walker, “RNA folding using quantum computers,” _PLOS Computational Biology_ , vol. 18, no. 4, p. e1010032, 2022.
  * [25] S. Mugel, M. Abad, M. Bermejo, J. Sánchez, E. Lizaso, and R. Orús, “Hybrid quantum investment optimization with minimal holding period,” _Scientific Reports_ , vol. 11, no. 1, p. 19587, 2021.
  * [26] M. Lee, N. Ma, G. Yu, and H. Dai, “Accelerating generalized benders decomposition for wireless resource allocation,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 2, pp. 1233–1247, 2020.
  * [27] L. Fan and Z. Han, “Hybrid quantum-classical computing for future network optimization,” _IEEE Network_ , vol. 36, no. 5, pp. 72–76, 2022.
  * [28] A.-D. Doan, M. Sasdelli, D. Suter, and T.-J. Chin, “A hybrid quantum-classical algorithm for robust fitting,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 417–427.
  * [29] T. Q. Dinh, S. H. Dau, E. Lagunas, and S. Chatzinotas, “Efficient hamiltonian reduction for quantum annealing on satcom beam placement problem,” _arXiv preprint arXiv:2210.06042_ , 2022.
  * [30] T. He, H. Khamfroush, S. Wang, T. La Porta, and S. Stein, “It’s hard to share: Joint service placement and request scheduling in edge clouds with sharable and non-sharable resources,” in _2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2018, pp. 365–375.
  * [31] B. Di, H. Zhang, L. Song, Y. Li, and G. Y. Li, “Ultra-dense LEO: Integrating terrestrial-satellite networks into 5G and beyond for data offloading,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 1, pp. 47–62, 2018.
  * [32] A. Abdi, W. C. Lau, M.-S. Alouini, and M. Kaveh, “A new simple model for land mobile satellite channels: First-and second-order statistics,” _IEEE Transactions on Wireless Communications_ , vol. 2, no. 3, pp. 519–528, 2003.
  * [33] S. Burer and A. N. Letchford, “Non-convex mixed-integer nonlinear programming: A survey,” _Surveys in Operations Research and Management Science_ , vol. 17, no. 2, pp. 97–106, 2012.
  * [34] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [35] M. ApS, “Mosek optimizer API for python,” _Version_ , vol. 9, no. 17, pp. 6–4, 2022.
  * [36] A. M. Geoffrion, “Generalized benders decomposition,” _Journal of optimization theory and applications_ , vol. 10, pp. 237–260, 1972.
  * [37] D. Li, X. Sun _et al._ , _Nonlinear integer programming_. Springer, 2006, vol. 84.
  * [38] W. Scherer, _Mathematics of quantum computing_. Springer, 2019.
  * [39] Z. Zhao, L. Fan, and Z. Han, “Hybrid quantum Benders’ decomposition for mixed-integer linear programming,” in _2022 IEEE Wireless Communications and Networking Conference (WCNC)_. IEEE, 2022, pp. 2536–2540.
  * [40] G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, “The unconstrained binary quadratic programming problem: a survey,” _Journal of combinatorial optimization_ , vol. 28, pp. 58–81, 2014.
  * [41] T. L. Magnanti and R. T. Wong, “Accelerating Benders’ decomposition: Algorithmic enhancement and model selection criteria,” _Operations research_ , vol. 29, no. 3, pp. 464–484, 1981.
  * [42] L. Gurobi Optimization, “Gurobi optimizer reference manual,” 2021.
  * [43] X. Xu, Z. Sun, X. Dai, T. Svensson, and X. Tao, “Modeling and analyzing the cross-tier handover in heterogeneous networks,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 12, pp. 7859–7869, 2017.
  * [44] S. Fu, J. Gao, and L. Zhao, “Integrated resource management for terrestrial-satellite systems,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 3, pp. 3256–3266, 2020.
  * [45] J. Shi, W. Yu, Q. Ni, W. Liang, Z. Li, and P. Xiao, “Energy efficient resource allocation in hybrid non-orthogonal multiple access systems,” _IEEE Transactions on Communications_ , vol. 67, no. 5, pp. 3496–3511, 2019.
  * [46] N. Saeed, A. Elzanaty, H. Almorad, H. Dahrouj, T. Y. Al-Naffouri, and M.-S. Alouini, “Cubesat communications: Recent advances and future challenges,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 3, pp. 1839–1862, 2020.
  * [47] M. Hong, M. Razaviyayn, Z.-Q. Luo, and J.-S. Pang, “A unified algorithmic framework for block-structured optimization involving big data: With applications in machine learning and signal processing,” _IEEE Signal Processing Magazine_ , vol. 33, no. 1, pp. 57–77, 2015.
  * [48] Q. T. Ngo, K. T. Phan, W. Xiang, A. Mahmood, and J. Slay, “Two-tier cache-aided full-duplex hybrid satellite–terrestrial communication networks,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 58, no. 3, pp. 1753–1765, 2021.
  * [49] C. Jiang and Z. Li, “Decreasing big data application latency in satellite link by caching and peer selection,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 4, pp. 2555–2565, 2020.
  * [50] D. Han, H. Peng, H. Wu, W. Liao, and X. S. Shen, “Joint cache placement and content delivery in satellite-terrestrial integrated C-RANs,” in _ICC 2021-IEEE International Conference on Communications_. IEEE, 2021, pp. 1–6.
  * [51] H. Wu, J. Li, H. Lu, and P. Hong, “A two-layer caching model for content delivery services in satellite-terrestrial networks,” in _2016 IEEE global communications conference (GLOBECOM)_. IEEE, 2016, pp. 1–6.
  * [52] S. Gu, X. Sun, Z. Yang, T. Huang, W. Xiang, and K. Yu, “Energy-aware coded caching strategy design with resource optimization for satellite-UAV-vehicle-integrated networks,” _IEEE Internet of Things Journal_ , vol. 9, no. 8, pp. 5799–5811, 2021.
  * [53] “D-wave demonstrates large-scale coherent quantum annealing,” October 2023. [Online]. Available: https://www.dwavesys.com/company/newsroom/press-release/d-wave-demonstrates-large-scale-coherent-quantum-annealing/