# Battery-constrained Federated Edge Learning in UAV-enabled IoT for B5G/6G
Networks

Shunpu Tang, Wenqi Zhou, Lunyuan Chen, Lijia Lai, Junjuan Xia and Liseng Fan
S. Tang, W. Zhou, L. Chen, L. Lai, J. Xia and L. Fan are all with the School
of Computer Science, Guangzhou University, Guangzhou, China (e-mail:
{tangshunpu, 2112006156, 2112019037<EMAIL_ADDRESS><EMAIL_ADDRESS>lsfan2019@126.com).

###### Abstract

In this paper, we study how to optimize the federated edge learning (FEEL) in
UAV-enabled Internet of things (IoT) for B5G/6G networks, from a deep
reinforcement learning (DRL) approach. The federated learning is an effective
framework to train a shared model between decentralized edge devices or
servers without exchanging raw data, which can help protect data privacy. In
UAV-enabled IoT networks, latency and energy consumption are two important
metrics limiting the performance of FEEL. Although most of existing works have
studied how to reduce the latency and improve the energy efficiency, few works
have investigated the impact of limited batteries at the devices on the FEEL.
Motivated by this, we study the battery-constrained FEEL, where the UAVs can
adjust their operating CPU-frequency to prolong the battery life and avoid
withdrawing from federated learning training untimely. We optimize the system
by jointly allocating the computational resource and wireless bandwidth in
time-varying environments. To solve this optimization problem, we employ a
deep deterministic policy gradient (DDPG) based strategy, where a linear
combination of latency and energy consumption is used to evaluate the system
cost. Simulation results are finally demonstrated to show that the proposed
strategy outperforms the conventional ones. In particular, it enables all the
devices to complete all rounds of FEEL with limited batteries and meanwhile
reduce the system cost effectively.

###### Index Terms:

UAV, federated learning, latency, energy consumption, mobile edge computing.

##  I Introduction

Swarms of unmanned aerial vehicles (UAVs) play a non-negligible role in
Internet of things (IoT) for beyond the fifth-generation (B5G) and the
forthcoming sixth-generation (6G) wireless mobile networks[1, 2, 3]. Due to
the mobility and flexibility, UAVs can effectively collect data and
communicate in the edge computing-based IoT networks. Thanks to these
advantages, UAVs have been widely used in many application scenarios, such as
environmental monitoring, emergence communication, transportation control and
remote sensing.

In recent years, deep learning has shown its great success on speech
recognition, computer vision and many other domains.[4]. Especially in the era
of big data, millions or billions of data are collected by various sensors and
are applied to train the deep learning model. The authors in [5] proposed a
large-scale hierarchical database for image classification and promoted the
emergence of state-of-the-art (SOTA) CNN models[6, 7, 8]. Large amounts of
high-quality data are the key to improve the performance of the deep learning
model. As a matter of fact, data collection faces a series of challenges.
Though a lot of data are produced by heterogeneous devices, especially IoT
devices and smartphones in the mobile edge, these data are fragmented and
scattered in various devices. This brings out a huge communication cost to
centralize data on the server to train models when we adopt the traditional
centralized training method of deep learning. Meanwhile, increasing concerns
of sensitive privacy make data collection more difficult. People do not want
their personal data (e.g. figs, voice, chat history) to be uploaded to others’
servers. There are also some companies, banks and hospitals with a lot of
sensitive data which are not allowed to divulge. Moreover, laws on privacy
protection have been promulgated continuously. Due to these reasons, data are
difficult to be centralized to train deep learning models, which is called
“data island” [9]. In this context, federated learning has been proposed to
break the “data island” and it makes full use of each device’s data to train a
model with a fine performance. In the federated learning, all devices use
local data to train a model and share the model on the premise of safety to
aggregate a global model with the federated optimization[10, 11, 12].

In the edge computing-based IoT networks, in order to speed up the process of
training and inference of deep learning, a new concept “Edge AI” was presented
to bring model closer to the places where data are generated when the
computational capabilities of edge devices are continually growing[13, 14,
15]. Federated learning is also applied to train deep learning models
cooperatively in MEC networks, which is referred to as federated edge learning
(FEEL)[16, 17]. Google Inc[18] used an edge server to build a keyboard input
prediction model based on FEEL, and FEEL can be also applied to improve the
performance of content caching without gathering users’ data centrally for
training[19, 20].

Although the FEEL has been successfully applied to many application scenarios,
there still exist some challenges. One major challenge is that there is a high
requirement for the latency and energy consumption in UAV-enabled IoT
networks, which is one of the important and critical issues. More importantly,
UAVs are powered by limited batteries and they can only work for a few dozen
minutes. It is dangerous for UAVs to run out of power when they are working
and it is of vital importance to control the remaining power. On the other
hand, enough participants are the guarantee of the performance for the FEEL
training. With a limited battery power, how to complete more training rounds
of federated learning is an unconsidered issue and it is our motivation to
control batteries effectively to prolong their service life. Accordingly, in
this paper we study the battery-constrained FEEL, where the UAVs can adjust
their operating CPU-frequency to prolong the battery life and avoid
withdrawing from federated learning training untimely. We optimize the system
by jointly allocating the computational resource and wireless bandwidth in
time-varying environments. To solve this optimization problem, we employ a
deep deterministic policy gradient (DDPG) based strategy, where a linear
combination of latency and energy consumption is used to evaluate the system
cost. The main contributions of this work are summarized below.

  * •

We study the resource allocation strategy for the FEEL in complicated
scenarios, where UAVs in edge computing-based IoT networks are powered by
limited batteries. Moreover, the characteristics of each device are different
and complicated, such as computational capabilities and channel conditions
which are time-varying.

  * •

We propose a resource allocation strategy based on the deep reinforcement
learning for the FEEL optimization, where the total latency and energy
consumption can be minimized by adjusting the CPU-frequency of devices and
upload wireless bandwidth for each device. More importantly, the strategy can
prolong the battery life of each device and enable devices to complete the
required rounds of federated learning.

  * •

We conduct simulated experiments to evaluate the performance of the proposed
resource allocation strategy and compare the performance with some
conventional strategies to demonstrate the superiority of the proposed
approach.

The rest of this paper is described as follows. Existed and relevant works are
introduced in Sec. II. Then, Sec. III describes the system model and
formulates the optimization problem, and Sec. IV provides the DDPG-based
allocation strategy involving the optimization on computational resource and
wireless bandwidth in time-varying environments. After that, Sec. V gives some
simulation results and discussions, and we finally conclude our work in Sec.
VI.

##  II Related Works

Mobile Edge computing networks: With the explosive growth of the number of IoT
devices in 5G and 6G era,more and more data are mainly generated in the mobile
edge, and mobile edge computing (MEC) is used to process a large quantity of
data with a lower latency and energy consumption[21]. Many researchers focus
on the offloading strategy in MEC to reduce system cost (e.g. Zhao[22]
optimized the computation offloading based on the discrete particle swarm
algorithm, the authors in [23] studied the multi-user computational offloading
and Li[24] proposed a DRL based approach to solve the problem of offloading
for multiuser and multi-CAP MEC networks and so on [25, 26, 27])
FL in the wireless networks: In MEC networks, there are many existing works
about reducing the latency and energy consumption by allocating the system
resources. But federated learning is basically distributed and heterogeneous,
and it needs to synchronize all the participants with different channel
conditions and computational capabilities [28]. Hence, another challenge is
how to reduce the cost of FEEL. In this direction, Takayuki [29] proposed a
client selection scheme for federated learning in mobile edge to accelerate
the training. In [30, 31], the authors studied the federated learning in
wireless networks and tried to allocate more bandwidth to nodes with poor
channel or weak computational capabilities. Due to the lack of continuous
connection between the UAV swarms, a joint powered allocation design was
proposed to optimize the convergence of federated learning [32]. The authors
in [33] presented worker-centric model selection for federated learning in the
MEC networks. Zhou[34] proposed a blockchain-based FL framework in the B5G
network. So far, few works have considered that most of the IoT devices are
powered by limited batteries. Zhan et al. [35] executed DRL to adjust the CPU-
frequency making a good trade-off between the latency and energy consumption.
But this work did not quantify the amount of battery power.

Figure 1: System model of FEEL in the UAV-enabled IoT networks.

##  III System Model and Problem Formulation

###  III-A Federated Learning

Federated learning is a distributed machine learning method to train a shared
model in the context of protecting personal privacy. It allows users to train
their dataset locally instead of uploading the sensitive data to a server. The
server collects the information from different users and generates a global
model. This process can be expressed as

$\displaystyle\arg\min_{w\in\mathbb{R}}F(\omega)=\frac{1}{M}\sum_{m=1}^{M}F_{m}(\omega),$
(1)

where $\omega$ is the model weight, $M$ is the user number, and $F_{m}(\cdot)$
is the loss function. As a matter of fact, FedAvg[10] is used to aggregate a
global model to reduce the communication rounds. Firstly, all the devices
train their models locally and then update the weight as

$\displaystyle\omega_{k+1}^{m}\leftarrow\omega_{k}^{m}-\alpha\nabla
F_{m}(\omega),$ (2)

where $\alpha$ is a positive learning rate, $\nabla(\cdot)$ denotes the
gradient operation and $k$ is the round index. Each user executes (2) several
times, and then it uploads the weight $w_{k+1}^{m}$ to the server. The server
aggregates the collected weights and calculates the weighted average weights
as

$\displaystyle\overline{\omega}_{k+1}\leftarrow\sum_{m=1}^{M}\frac{n_{m}}{n}\omega^{m}_{k+1},$
(3)

where $\frac{n_{m}}{n}$ is the proportion of samples in total. It is called as
model average[11, 36]. Lastly, the server broadcasts the new global model to
each user.

###  III-B System Model

Fig. 1 shows the system model of the considered FEEL framework, where there
are $M$ distributed users and a centralized server. In practical, the $M$
users can be various UAV devices in the edge computing-based IoT network, and
the parameters server can be the base station or one of the UAVs. We use
$\mathcal{M}=\left\\{1,2,\cdots,M\right\\}$ to denote the user set. The number
of data samples which needs to be trained locally is $d_{m}$. We assume that a
round of FL training can be completed in a time slot. For each device
$m\in\mathcal{M}$ in the $k$-th round, the base CPU-frequency is $f_{m}^{k}$
and it requires $c_{m}$ CPU-cycles to process a sample of the local dataset.
To deal with the problem of limited communication resources, each device will
train $e$ times locally before uploading the weights[10]. The local training
time of device $m$ at the $k$-th round can be written as

$\displaystyle t^{k}_{m,local}=\frac{ec_{m}D_{m}}{\eta_{m}^{k}f_{m}^{k}},$ (4)

where $\eta_{m}^{k}$ is the coefficient of frequency adjustment which
determines the practical operating CPU-frequency and $K$ is the maximum round
of FL. The weights will be uploaded to the centralized server through the
wireless link after each device completes the local training. The data rate of
the wireless link from device $m$ to the centralized server is:

$\displaystyle
r_{m}^{k}=B_{m}^{k}\log_{2}\left(1+\frac{P_{m}|h_{m}^{k}|^{2}}{\sigma_{m}^{2}}\right),$
(5)

where $h_{m}^{k}\sim\mathcal{CN}(0,\beta)$ is the channel parameter of the
link from device $m$ to the centralized server, $\sigma^{2}$ is the variance
of the additive white Gaussian noise (AWGN) at the server and $P_{m}$ is the
transmit power of device $m$. Notation $B_{m}^{k}$ is the bandwidth of device
$m$ and it can be allocated by the base station. At each round, $B_{m}^{k}$
should meet the following requirement

$\displaystyle\sum_{m=1}^{M}B_{m}^{k}=B_{total}.$ (6)

According to (5), the transmission latency can be calculated as

$\displaystyle t^{k}_{m,up}=\frac{\epsilon}{r_{m}^{k}},$ (7)

where $\epsilon$ is the size of deep learning model’s weights. The total time
to provide a local model of device $m$ can be expressed as

$\displaystyle T^{k}_{m}=t^{k}_{m,local}+t^{k}_{m,up}.$ (8)

Each device trains its local model and uploads parallelly. The centralized
server has to wait for the local model from the slowest device which can be
viewed as the bottleneck of the system to aggregate a new global model. So the
system latency at the $k$-th round is

$\displaystyle T_{k}=\max_{m\in\mathcal{M}}{T^{k}_{m}}.$ (9)

Similarly, we can calculate the energy consumption in two stages. At the first
stage, device $m$ performs some algorithms like back propagation (BP) to
update the weights at the cost of huge energy consumption. According to [2],
the training energy consumption can be written as

$\displaystyle
E^{k}_{m,local}=\zeta_{m}c_{m}D_{m}(\eta_{m}^{k}f_{m}^{k})^{2},$ (10)

where $\zeta_{m}$ is the energy consumption coefficient of CPU chips. Then
device $m$ uploads the weights with transmit power $P_{m}$ and the energy
consumption of transmission can be easily expressed as

$\displaystyle E^{k}_{m,up}=P_{m}t^{k}_{m,up}.$ (11)

So the total energy consumption of device $m$ at the $k$-th round is

$\displaystyle E^{k}_{m}=E^{k}_{m,local}+E^{k}_{m,up}.$ (12)

Under ideal conditions, devices can continuously participate in FedAvg[10] and
contribute their local models until achieving the best performance. However,
in the case of limited resources, we have to consider that the battery of
devices may run out. The energy model should meet the following requirement

$\displaystyle\sum_{k=1}^{K}E^{k}_{m}\leq\delta_{m},$ (13)

where $\delta_{m}$ is the total battery power of device $m$.

To describe the total system cost, we use a linear combination of latency and
energy consumption as following [35, 24]

$\displaystyle\Phi=\sum_{k=1}^{K}\left[\lambda
T_{k}+(1-\lambda)\sum_{m}^{M}E^{k}_{m}\right],$ (14)

where $\lambda\in\left[0,1\right]$ is a factor to describe the importance of
latency and energy consumption in the system cost. We can adjust $\lambda$ to
trade-off the latency and energy consumption. Specifically, the linear
combination approaches to the energy consumption when $\lambda$ goes to zero,
while it degenerates into the latency if $\lambda$ is near one. In fact, the
linear combination is a method to solve multi-objective programming problems
by giving a proper weight coefficient according to the importance of each
objective and changing to single-objective programming problems.

###  III-C Problem Formulation

For the practical battery-constrained devices, we expect that they can
participate in the rounds of FEEL training as much as possible and meanwhile
try to avoid running out of power. Moreover, the system cost measured by the
latency and energy consumption should be minimized, which is particularly
important for the IoT devices. By taking into account these factors, we can
optimize the training rounds and system cost by adjusting the CPU-frequency
and bandwidth. The system optimization problem can be given by

$\displaystyle\max_{\\{{\eta_{m}^{k}},B_{m}^{k}\\}}K-\ \overline{\Phi}$
$\displaystyle\quad\quad\mathrm{s.t.}\quad C_{1}:$
$\displaystyle\eta_{m}^{k}\in[0,1],$ (15) $\displaystyle C_{2}:$
$\displaystyle\sum_{m=1}^{M}B_{m}^{k}=B_{total},$ $\displaystyle C_{3}:$
$\displaystyle\sum_{k=1}^{K}E^{k}_{m}\leq\delta_{m},$

where $\overline{\Phi}=\frac{\Phi}{K}$ is the average cost of per round. It is
generally very hard to solve the above optimization problem by using
conventional optimization methods such as convex optimization. Especially, in
a time-varying environment, the base CPU-frequency and channel condition are
different in each round, causing heterogeneity in the training process. Due to
these reasons, a learning based algorithm should be developed to adapt to
different states in order to find a proper solution. The notations of this
section we have used are summarized in Table. I.

TABLE I: Symbol notations Notation |  Definition
---|---
$\alpha$ |  learning rate of FL
$\omega^{m}_{k}$ |  model weight of the $m$-th user in the $k$-th round
$\epsilon$ |  size of deep learning model weight
$\zeta_{m}$ |  energy consumption coefficient of the $m$-th user
$\Phi$ |  system cost
$r^{k}_{m}$ |  transmission rate between the $m$-th user and the server
$e$ |  local training times
$c_{m}$ |  cpu-cycles to process a sample of the $m$-th user
$d_{m}$ |  number to data samples of the $m$-th user
$\delta_{m}$ |  total battery power of device $m$
$\eta_{m}^{k}$ |  coefficient of frequency adjustment of the $m$-th user in the $k$-th round
$f_{m}^{k}$ |  base CPU-frequency of the $n$-th user in the $k$-th round
$t^{k}_{m,local}$ |  local latency of the $m$-th user in the $k$-th round
$t^{k}_{m,up}$ |  transmission latency of the $m$-th user in the $k$-th round
$B_{m}^{k}$ |  wireless bandwidth of the $n$-th user in the $k$-th round
$T^{k}$ |  system latency in the $k$-th round
$E^{k}_{m,local}$ |  Local energy consumption of the $m$-th user in the $k$-th round
$E^{k}_{m}$ |  system energy consumption of the $n$-th user in the $k$-th round
$F(\cdot)$ |  loss function of FL

##  IV DDPG-Based Allocation Strategy

In this section, we will try to solve the system optimization problem in
(III-C), by using the DDPG-based allocation strategy. Specifically, we will
first describe the Markov decision process (MDP), and then introduce how to
implement the DDPG-based resource allocation strategy.

###  IV-A Markov Decision Process

MDP is used to model decision-making in time-varying environments and it
mainly consists of a 4-tuple $\\{S,A,P_{a},R_{a}\\}$. Specifically,
$S=\\{k,\mathbf{O^{k}},\mathbf{F^{k}},\mathbf{H^{k}}\\}$ is the state space,
where $\mathbf{O^{k}}$ is a vector of the remaining battery power,
$\mathbf{F^{k}}$ is a vector of the current base CPU-frequency of all the
devices, and $\mathbf{H^{k}}$ is the channel parameter of the $k$-th round
which can be obtained by using some channel estimation methods. We use
$A=\\{\mathbf{N^{k}},\mathbf{B^{k}}\\}$ to denote the action space, where
$\mathbf{N^{k}}=\\{\eta_{1}^{k},\eta_{2}^{k},\cdots\eta_{M}^{k}\\}$ is the
coefficient of CPU-frequency adjustment and
$\mathbf{B^{k}}=\\{B^{k}_{1},B^{k}_{2}\cdots B^{k}_{M}\\}$ is the allocated
vector of bandwidth.

At the $k$-th round of the FEEL training, the current state is $s_{k}\in S$
and the agent will perform an action $a_{t}\in A$ in the environment. From the
feedback of environment, $s_{k}$ will transit to $s_{k+1}$ with a conditional
probability $P$. Meanwhile, the agent will achieve an instant reward from the
environment, which can be expressed by

$\displaystyle R^{k}=k-\phi,$ (16)

where $k$ is positive feedback and $\phi$ is the instant cost of a round in
FEEL training, which is denoted by the linear combination of energy
consumption and latency. The agent expects to achieve a long-term average
reward from the environment by maximizing $K$ and minimizing
$\overline{\Phi}$.

However, it is difficult to estimate the conditional probability $P$ in many
application scenarios. Hence, we turn to use the DDPG algorithm to solve this
problem.

Figure 2: Actor-critic framework.

###  IV-B Deep Deterministic Policy Gradient

In the considered FEEL scenario, the CPU-frequency and bandwidth allocation
vary over a continuous range with infinite possibilities. Accordingly,
although deep Q-learning network [37, 38] can deal with the problem of
discrete and low-dimensional action space, it is unable to work efficiently in
the face of continuous action space since its performance severely relies on
finding the maximum of value function approximated by the neural network in
each iteration. Due to this reason, we turn to use the DDPG strategy to solve
the optimization problem of CPU-frequency and bandwidth allocation.
Deterministic Policy Gradient[39] was proposed to output a deterministic
action, instead of the value of all the actions under the actor-critic
framework. Fig. 2 shows the actor-critic framework in the DDPG, where a deep
neural network called actor network is used to produce a deterministic action
while a critic network is employed to approximate the value-function which
evaluates the action. To formulate the DDPG strategy, we use
$\mu(s|\theta^{\mu})$ and $Q(s,a|\theta^{Q})$ to denote the actor and critic
network, respectively. For a deterministic action $a_{t}$ in the state
$s_{t}$, the Bellman equation for the action-state value function can be
written as

$\displaystyle Q(s,a)=\mathbb{E}_{s_{t+1}\sim S}\left[r(s_{t},a_{t})+\gamma
Q(s_{t+1},a_{t+1})\right],$ (17)

where $s_{t+1}$ is the next state when the agent executes the action $a_{t}$
in the state $s_{t}$ and $a_{t+1}$ is the next action given by the actor
network.

Figure 3: Implementation structure of DDPG.

Motivated by the idea of double network in the DQN, target networks and main
networks are used in DDPG. Fig. 3 shows the implementation structure of DDPG,
where there are four neural networks working together,

  * •

Main actor network $\mu$: We will get the deterministic action from
$a_{t}=\mu(s|\theta^{\mu})$ and $\mu$ is used to update weights of the target
actor network.

  * •

Target actor network $\mu^{\prime}$: The target actor network predicts the
next action by $a_{t+1}=\mu^{\prime}(s_{t+1}|\theta^{\mu^{\prime}})$.

  * •

Main critic network $Q$: According to the current state $s_{t}$ and action
given by the main actor network $\mu$, the main critic network $Q$ is
responsible for giving the $Q$ value by $Q(s,a|\theta^{Q})$.

  * •

Target critic network $Q^{\prime}$: In the state $s_{t+1}$, the $Q$-value will
be evaluated by
$Q^{\prime}(s_{t+1},\mu^{\prime}(s_{t+1}|\theta^{\mu^{\prime}})|\theta^{Q^{\prime}})$.

The approach of target networks reduces the correlation between the current
$Q$-value and target $Q$-value, which helps increase the robustness of
training. For the main critic network, the loss function can be expressed as

$\displaystyle
L(\theta^{Q})=\mathbb{E}_{\mu^{\prime}}(Q(s,a|\theta^{Q})-y_{i})^{2},$ (18)

where

$\displaystyle y_{i}=r(s_{t},a_{t})+\gamma
Q^{\prime}(s_{t+1},\mu^{\prime}(s_{t+1}|\theta^{\mu^{\prime}})|\theta^{Q^{\prime}}),$
(19)

in which $\gamma$ is a positive discount factor of reward. By executing the
gradient descent method and minimizing the loss function in (18), we can
update the main critic network. Additionally, to optimize action decisions and
achieve higher rewards, $Q$-value is considered as the loss function of the
actor network. The main actor network will be updated by the gradient ascent
from

$\displaystyle\nabla_{\theta^{\mu}}=\mathbb{E}_{\mu^{\prime}}\left[\nabla_{a}Q(s,a|\theta^{Q})|_{s=s_{t},a=\mu(s_{t})}\nabla_{\theta^{\mu}}\mu(s|\theta^{\mu})|_{s_{t}}\right].$
(20)

Different from copying weights from the main networks in a certain interval of
time in DQN, the target networks in DDPG adopt a soft update in each step as

$\displaystyle\theta^{Q^{\prime}}\leftarrow\tau\theta+(1-\tau)\theta^{Q^{\prime}}$
(21)
$\displaystyle\theta^{\mu^{\prime}}\leftarrow\tau\theta+(1-\tau)\theta^{\mu^{\prime}},$
(22)

where $\tau$ is an update factor. In addition, an experience reply unit (ERU)
is used to collect training samples and the agent will randomly choose batches
of samples during the training process. This can help break the relevance and
non-stationary distribution between training samples and improve the
performance.

###  IV-C DDPG-based resource allocation strategy

Algorithm 1 DDPG-based resource allocation strategy

Input: current state $S=\\{k,\mathbf{O^{k}},\mathbf{F^{k}},\mathbf{H^{k}}\\}$
Output: allocation matrix $A=\\{\mathbf{N^{k}},\mathbf{B^{k}}\\}$

1:Initialize the target network $Q^{\prime}$ and $\mu^{\prime}$ with
$\theta^{Q^{\prime}}\leftarrow\theta^{Q}$,$\theta^{\mu^{\prime}}\leftarrow\theta^{\mu}$
in the server.

2:Initialize experience replay memory $\mathcal{D}$

3:for episode = 1,M do

4: Initialize a random process $\mathcal{N}$ for exploring.

5: Initialize state $s_{1}$

6: while $s\notin S_{end}$ do

7: Devices upload the base frequency to the server and estimate the channel
parameters.

8: Server chooses an action $a_{k}=\mu(s_{t}|\theta^{\mu})+\mathcal{N}_{t}$

9: Execute action the $a_{k}$ and observe reward $r_{k}$ and next state
$s_{k+1}$

10: Store $(s_{k},a_{k},r_{k},s_{k+1})$ in $\mathcal{D}$

11: Randomly sample a mini-batch of transitions $(s_{i},a_{i},r_{i},s_{i+1})$
from $\mathcal{D}$

12: $y_{i}=r(s_{i}+\gamma
Q^{\prime}(s_{i+1},\mu^{\prime}(s_{i+1}|\theta^{\mu^{\prime}})|\theta^{Q^{\prime}}).$

13: Update the critic network by minimizing :
$L=\frac{1}{N}{\mu^{\prime}}(Q(s,a|\theta^{Q})-y_{i})^{2}$

14: Update the actor network by gradient ascent:
$\nabla_{\theta^{\mu}}=\mathbb{E}_{\mu^{\prime}}\left[\nabla_{a}Q(s,a|\theta^{Q})|_{s=s_{t},a=\mu(s_{t})}\nabla_{\theta^{\mu}}\mu(s|\theta^{\mu})|_{s_{t}}\right]$

15: Update the target networks:
$\theta^{Q^{\prime}}\leftarrow\tau\theta+(1-\tau)\theta^{Q^{\prime}}$
$\theta^{\mu^{\prime}}\leftarrow\tau\theta+(1-\tau)\theta^{\mu^{\prime}}$

16: end while

17:end for

In this part, we will introduce the proposed DDPG-based resource allocation
strategy. Firstly, we design a mutil-task neural network which outputs the
results of $N_{k}$ and $B_{k}$ simultaneously. In order to ensure the outputs
in the correct range, the Sigmoid and Softmax activation functions are used in
the last layer of network. Before each round of FEEL training, clients need to
report their available resources such as the base CPU-frequency and remaining
battery power to the server. At the same time, the server should estimate the
channel parameters of the links from it to the users. These information is
entered as the input of the main actor network to get a deterministic action
of adjusting the practical CPU-frequency and bandwidth allocation. The base
station will inform participants the operating CPU-frequency and the available
wireless bandwidth to them. The agent will achieve different rewards in each
round according to the latency, energy consumption and the current number of
rounds. When the experience reply unit has enough samples, the agent will
adjust its strategy by the way introduced in the previous part. In order to
guarantee the global convergence, we reset the environment and re-initialize
state $s_{1}$ to train the agent when the agent reaches the final state. After
some episodes with convergence, the DDPG strategy can find a proper result of
$\eta_{m}^{k}$ and $B_{m}^{k}$. In this way, the optimization problem of
(III-C) is solved. The whole procedure of the DDPG strategy is summarized in
Algorithm 1.

##  V Simulations and Discussions

In this section, we will demonstrate the performance of the proposed DDPG-
based resource allocation strategy by simulations. To simulate the practical
scenarios of FEEL, we suppose that there are 20 users with limited battery
power subject to $\mathcal{U}(2\times 10^{4},3\times 10^{4})$ and their
initial base CPU-frequencies are subject to $\mathcal{U}(1\times
10^{7},5\times 10^{7})$. The users will train locally 5 times per round and
participate in 1000 rounds of the FEEL training at most. In addition, the
number of CPU-cycles to process a sample is set subject to
$\mathcal{U}(7\times 10^{4},2\times 10^{5})$, the sizes of users’ dataset are
subject to $\mathcal{U}(400\\\ ,600)$, and the energy consumption coefficients
of CPU chips are set subject to $\mathcal{U}(1\times 10^{-22},2\times
10^{-22})$. Moreover, the transmit power of all the devices is set to $5\times
10^{-5}$, the total wireless bandwidth is $5$MHz, and the model size is set to
$10$MB. We assume that the condition will be static in a round, while it is
time-varying in different rounds of training. To simulate the time-varying
environments, we set the initial base CPU-frequency varying from $0.8$ to
$1.2$ times. Similarly, the average channel gain of the wireless links is set
to unity, and the variance of the AWGN is set to $10^{-9}$.

As to the DDPG network, we implement it by the well-known Pytorch library
[40]. The actor networks consist of 2 hidden layers with 64 and 256 nodes,
respectively. In the critic networks, there are 2 hidden layers with 30 nodes
per layer. To enhance the fitting ability of the networks, the Rectified
Linear Unit (ReLU)[41] is used as the activation function. The Adam[42] method
is used to optimize the loss function of networks and the learning rates are
$10^{-6}$ and $10^{-2}$ in the main actor and main critic networks,
respectively. We set the capacity of ERU to $10^{4}$ and the batch size is
$128$. Besides, the value of $\gamma$ is $0.999$, and $\tau$ is set to
$10^{-3}$. The DDPG agent will train $50$ times at the end of FEEL in each
episode. The total episode of DRL is $800$, and we repeat the experiments to
reduce the accidental error.

Figure 4: Convergence of the proposed DDPG approach with $\lambda=0.5$. Figure
5: Convergence of the maximum round.

Fig. 4 shows the training process of the proposed DDPG-basd resource
allocation strategy, where $\lambda=0.5$ and there are 800 episodes at all. We
focus on the total reward in each episode. From this figure, we can find that
the curve of the total reward grows very fast in the first 200 episodes and
then it continues to increase with a slow growth tendency. After about 500
episodes, the proposed DDPG approach can achieve an asymptotic reward value of
about 4000. These results can help verify the proposed DDPG-based strategy.

Fig. 5 depicts the maximum round of the proposed strategy versus episodes,
where $\lambda=0.5$ and there are 800 episodes at all. From this figure, we
can observe that at the beginning of episode, the battery-constrained devices
are easily to run out of power and can only participate in about 500 rounds.
When the episode increases, the devices can participate in more rounds of
training. This is because that with the learning of DDPG agent, the proposed
resource allocation strategy continues to improve and all the devices can
prolong the life of their batteries. When the curve is converged, all the
devices can complete 1000 rounds of training. This can not only ensure the
performance of training, but also avoid the danger caused by shutdown.

Fig. 6 shows the maximum round of two strategies versus the static adjustment
factor of frequency, where $\lambda=0.5$ and the adjustment factor varies from
0.1 to 1. For comparison, we provide the performance of the static strategy,
where the coefficient of frequency adjustment is static at each FL training
round and bandwidth allocation is even with $B_{m}^{k}=B_{total}/M$ for each
device. We use the static strategy to compare since in the practical time-
varying scenario, it is however difficult to determine how to set the proper
operating CPU-frequency of devices, and the devices should run at a proportion
of base CPU-frequency in order to reduce the energy consumption. From this
figure, we can see that the proposed strategy remains unchanged with the
adjustment factor, and it can enable all the devices to complete 1000 rounds
of training. In contrast, the static strategy can only obtain about 200 rounds
of training when the adjustment factor is around 1, since all the devices
operate at the base CPU-frequency with a high energy consumption. When the
adjustment factor decreases, the static strategy can enable all devices to
reduce the energy consumption and take part in more rounds of training. In
particular, the static approach can achieve 1000 rounds of training when the
adjusting factor is smaller than 0.3. The comparison results in this figure
can further verify the effectiveness of the proposed DDPG strategy.

Figure 6:  Maximum rounds versus the static adjustment factor of frequency.
Figure 7:  Energy consumption versus the static adjustment factor of
frequency.

Fig. 7 shows the energy consumption versus the static adjustment factor of
frequency, where $\lambda=0.5$. The energy consumption of the proposed
strategy is about $69$ and it is a little higher than it in the static
approach when the adjustment factor is smaller than $0.2$. With the increase
of the static adjustment factor, the energy consumption of the static approach
grows explosively. This causes the battery power of devices being easily
exhausted and influences the continuous training of FL.

Fig. 8 describes the latency versus the static adjustment factor of frequency,
where $\lambda=0.5$. From this figure, we can observe that the latency is more
than 200 when the adjustment factor is smaller than $0.2$ while the latency of
the proposed strategy is only about 96. Hence, it is unacceptable to save
energy by decreasing the adjustment factor smaller than $0.2$. With the
increase of the adjustment factor, the latency is lowing down. Moreover, the
latency of the proposed strategy is almost identical to that in the static
strategy when the adjustment factor is $0.5$. By combining the results in
Figs. 7\- 8, we can conclude that the proposed strategy can make a good trade-
off between the energy consumption and latency efficiently. This can help
verify the effectiveness of the proposed DDPG strategy furthermore.

Fig. 9 shows the system cost versus the static adjustment factor of frequency.
To describe clearly, we use the linear combination to express the system cost,
where $\lambda=0.5$. We can find from this figure that the system cost of the
proposed DDPG strategy remains unchanged with the adjustment factor, which is
similar to the phenomena in Figs. 6-8. In contrast, the static approach is
affected by the adjustment factor significantly. Specifically, the system cost
of the static approach becomes smaller when the adjustment factor increases in
a low region of adjustment factor. This is due to the energy saving, which
however leads to a huge latency. On the contrary, the system cost of the
static approach becomes larger when the adjustment factor increases in a high
region of adjustment factor. This is because that the pursuit of reducing
latency leads to a great energy consumption. In particular, the static
approach achieves the minimum system cost when the adjustment factor is 0.3,
which is still higher than that of the proposed DDPG strategy.

Fig. 10 depicts the system cost of several strategies versus the number of
users, where $\lambda=0.5$. For comparison, we plot the performance of the
proposed DDPG strategy with even bandwidth allocation, denoted by E-DDPG. From
this figure, we can find that the proposed DDPG outperforms E-DDPG, since the
former can exploit the wireless bandwidth resources in the learning process,
which can help improve the system performance. Moreover, E-DDPG is much better
than the static approach, since the later cannot utilize the system
communication and computational resources efficiently. In further, the system
performance of all the three strategies increases with a larger number of
users, as more uses impose a heavier burden on the training process.

Figure 8:  Latency versus the static adjustment factor of frequency. Figure 9:
Average system cost versus the static adjustment factor of frequency. Figure
10: Average system cost versus number of users.

In Fig. 11, we plot the performance of several resource allocation strategies
versus the wireless bandwidth, where $\lambda=0.5$ and the wireless bandwidth
varies from 1MHz to 9MHz. From this figure, we can see that the performances
of the three strategies become better when the bandwidth increases, since a
larger bandwidth can help reduce the transmission latency as well as the
transmission energy consumption. Moreover, the proposed strategy outperforms
the static approach and E-DDPG for various values of wireless bandwidth, since
it can exploit the system communication and computational resources
efficiently. In particular, when the total bandwidth is 1MHz, the cost of the
proposed DDPG strategy, E-DDPG and the static approach is about 130, 140, and
170, respectively. In further, when the bandwidth increases, the transmission
latency becomes negligible in the system cost for the proposed DDPG and E-DDPG
strategies, which makes the performance gap between these two strategies
decrease. The results in this figure demonstrate the merits of the proposed
DDPG strategy furthermore.

Figure 11: Average system versus different bandwidth.

##  VI Conclusions

This paper studied how to optimize the FEEL in UAV-enabled IoT networks where
UAVs had limited batteries, from a deep reinforcement learning approach.
Specifically, we provided an optimization framework where the devices could
adjust their operating CPU-frequency to prolong the battery life and avoid
withdrawing from federated learning training untimely, through jointly
allocating the computational resource and wireless bandwidth in time-varying
environments. To solve this optimization problem, we employed the DDPG based
strategy, where a linear combination of latency and energy consumption was
used to evaluate the system cost. Simulation results were demonstrated to show
that the proposed strategy could efficiently avoid devices withdrawing from
the FL training untimely and meanwhile reduce the average system cost.

## References

  * [1] M. Mozaffari, A. T. Z. Kasgari, W. Saad, M. Bennis, and M. Debbah, “Beyond 5g with uavs: Foundations of a 3d wireless cellular network,” _IEEE Transactions on Wireless Communications._ , vol. 18, no. 1, pp. 357–372, 2019\.
  * [2] X. Li, Q. Wang, Y. Liu, T. A. Tsiftsis, Z. Ding, and A. Nallanathan, “Uav-aided multi-way noma networks with residual hardware impairments,” _IEEE Wireless Communications Letters_ , vol. 9, no. 9, pp. 1538–1542, 2020.
  * [3] M. Mozaffari, W. Saad, M. Bennis, Y. Nam, and M. Debbah, “A tutorial on uavs for wireless networks: Applications, challenges, and open problems,” _IEEE Communications Surveys Tutorials_ , vol. 21, no. 3, pp. 2334–2360, 2019\.
  * [4] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _Nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [5] J. Deng, W. Dong, R. Socher, L. Li, K. Li, and F. Li, “Imagenet: A large-scale hierarchical image database,” in _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_ , 2009, pp. 248–255.
  * [6] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _Advances in Neural Information Processing Systems (NIPS)_ , 2012, pp. 1106–1114.
  * [7] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_ , 2016, pp. 770–778.
  * [8] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_ , 2017, pp. 4700–4708.
  * [9] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [10] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22_ , vol. 54, 2017, pp. 1273–1282.
  * [11] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [12] J. Konečnỳ, H. B. McMahan, D. Ramage, and P. Richtárik, “Federated optimization: Distributed machine learning for on-device intelligence,” _arXiv preprint arXiv:1610.02527_ , 2016.
  * [13] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” _IEEE internet of things journal_ , vol. 3, no. 5, pp. 637–646, 2016.
  * [14] E. Li, Z. Zhou, and X. Chen, “Edge intelligence: On-demand deep learning model co-inference with device-edge synergy,” in _Proceedings of the 2018 Workshop on Mobile Edge Communications, MECOMM@SIGCOMM_. ACM, 2018, pp. 31–36.
  * [15] E. Li, L. Zeng, Z. Zhou, and X. Chen, “Edge ai: On-demand accelerating deep neural network inference via edge computing,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 1, pp. 447–457, 2020.
  * [16] W. Y. B. Lim, N. C. Luong, D. T. Hoang, Y. Jiao, Y. Liang, Q. Yang, D. Niyato, and C. Miao, “Federated learning in mobile edge networks: A comprehensive survey,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 3, pp. 2031–2063, 2020.
  * [17] Y. Guo, F. Liu, Z. Cai, L. Chen, and N. Xiao, “Feel: A federated edge learning system for efficient and privacy-preserving mobile healthcare,” in _49th International Conference on Parallel Processing-ICPP_ , 2020, pp. 1–11.
  * [18] T. Yang, G. Andrew, H. Eichner, H. Sun, W. Li, N. Kong, D. Ramage, and F. Beaufays, “Applied federated learning: Improving google keyboard query suggestions,” _arXiv preprint arXiv:1812.02903_ , 2018.
  * [19] Z. Yu, J. Hu, G. Min, H. Lu, Z. Zhao, H. Wang, and N. Georgalas, “Federated learning based proactive content caching in edge computing,” in _IEEE Global Communications Conference (GLOBECOM)_ , 2018, pp. 1–6.
  * [20] L. Cui, X. Su, Z. Ming, Z. Chen, S. Yang, Y. Zhou, and W. Xiao, “Creat: Blockchain-assisted compression algorithm of federated learning for content caching in edge computing,” _IEEE Internet of Things Journal_ , pp. 1–1, 2020.
  * [21] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 4, pp. 2322–2358, 2017.
  * [22] Z. Zhao, R. Zhao, J. Xia, X. Lei, D. Li, C. Yuen, and L. Fan, “A novel framework of three-hierarchical offloading optimization for mec in industrial iot networks,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 8, pp. 5424–5434, 2019.
  * [23] Z. Liang, Y. Liu, T.-M. Lok, and K. Huang, “Multiuser computation offloading and downloading for edge computing with virtualization,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 9, pp. 4298–4311, 2019\.
  * [24] C. Li, J. Xia, Y. Rao, F. Liu, L. Fan, G. K. Karagiannidis, and A. Nallanathan, “Dynamic offloading for multiuser muti-cap mec networks: A deep reinforcement learning approach,” _IEEE Transactions on Vehicular Technology_ , vol. 72, no. 3, pp. 3424–3438, 2020.
  * [25] J. Feng, F. R. Yu, Q. Pei, J. Du, and L. Zhu, “Joint optimization of radio and computational resources allocation in blockchain-enabled mobile edge computing systems,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 6, pp. 4321–4334, 2020.
  * [26] J. Feng, Q. Pei, F. R. Yu, X. Chu, J. Du, and L. Zhu, “Dynamic network slicing and resource allocation in mobile edge computing systems,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 7, pp. 7863–7878, 2020.
  * [27] Y. Wang, X. Tao, Y. T. Hou, and P. Zhang, “Effective capacity-based resource allocation in mobile edge computing with two-stage tandem queues,” _IEEE Transactions on Communications_ , vol. 67, no. 9, pp. 6221–6233, 2019\.
  * [28] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečnỳ, S. Mazzocchi, H. B. McMahan _et al._ , “Towards federated learning at scale: System design,” _arXiv preprint arXiv:1902.01046_ , 2019.
  * [29] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” in _IEEE International Conference on Communications (ICC)_ , 2019, pp. 1–7.
  * [30] W. Shi, S. Zhou, and Z. Niu, “Device scheduling with fast convergence for wireless federated learning,” in _IEEE International Conference on Communications (ICC)_ , 2020, pp. 1–6.
  * [31] W. Shi, S. Zhou, Z. Niu, M. Jiang, and L. Geng, “Joint device scheduling and resource allocation for latency constrained wireless federated learning,” _IEEE Transactions on Wireless Communications_ , 2020.
  * [32] T. Zeng, O. Semiari, M. Mozaffari, M. Chen, W. Saad, and M. Bennis, “Federated learning in the sky: Joint power allocation and scheduling with uav swarms,” in _IEEE International Conference on Communications (ICC): Next-Generation Networking and Internet Symposium_ , 2020.
  * [33] H. Huang and Y. Yang, “Workerfirst: Worker-centric model selection for federated learning in mobile edge computing,” in _2020 IEEE/CIC International Conference on Communications in China (ICCC)_ , 2020, pp. 1039–1044.
  * [34] S. Zhou, H. Huang, W. Chen, P. Zhou, Z. Zheng, and S. Guo, “Pirate: A blockchain-based secure framework of distributed machine learning in 5g networks,” _IEEE Network_ , vol. 34, no. 6, pp. 84–91, 2020.
  * [35] Y. Zhan, P. Li, and S. Guo, “Experience-driven computational resource allocation of federated learning by deep reinforcement learning,” in _Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS)_ , 2020, pp. 234–243.
  * [36] H. Yu, S. Yang, and S. Zhu, “Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 5693–5700.
  * [37] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.
  * [38] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [39] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, “Deterministic policy gradient algorithms,” in _Proceedings of the 31st International Conference on Machine Learning (ICML)_ , vol. 32, 2014, pp. 387–395.
  * [40] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in neural information processing systems_ , 2019, pp. 8026–8037.
  * [41] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , 2011, pp. 315–323.
  * [42] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.


# A comment on “Factoring integers with sublinear resources on a
superconducting quantum processor”

Tanuj Khattar<EMAIL_ADDRESS>Google Research, Venice, CA 90291,
United States  Noureldin Yosri<EMAIL_ADDRESS>Google, Dublin,
Ireland

###### Abstract

Quantum computing has the potential to revolutionize cryptography by breaking
classical public-key cryptography schemes, such as RSA and Diffie-Hellman.
However, breaking the widely used 2048-bit RSA using Shor’s quantum factoring
algorithm is expected to require millions of noisy physical qubits and is well
beyond the capabilities of present day quantum computers. A recent proposal by
Yan et. al. tries to improve the widely debated Schnorr’s lattice-based
integer factorization algorithm using a quantum optimizer (QAOA), and further
claim that one can break RSA 2048 using only 372 qubits. In this work, we
present an open-source implementation of the algorithm proposed by Yan et. al.
and show that, even if we had a perfect quantum optimizer (instead of a
heuristic like QAOA), the proposed claims don’t hold true. Specifically, our
implementation shows that the claimed sublinear lattice dimension for the
Hybrid quantum+classical version of Schnorr’s algorithm successfully factors
integers only up to 70 bits and fails to find enough factoring relations for
random 80 bit integers and beyond. We further hope that our implementation
serves as a playground for the community to easily test other hybrid quantum +
classical integer factorization algorithm ideas using lattice based
reductions.

All code and data used in the paper is available at github.com/google-
research/google-research/factoring_sqif

###### Contents

  1. I Introduction
  2. II Implementation of Sublinear Resource Quantum Integer Factorization (SQIF) Algorithm
  3. III Results
  4. IV Conclusion
  5. A Hyperparameters
    1. A.1 Lattice Parameter and Lattice Dimension
    2. A.2 Precision parameter for lattice construction
    3. A.3 Smoothness bound $B_{2}$
    4. A.4 Energy states specific hyperparameters

##  I Introduction

Integer factorization is a central problem to cryptography. While the exact
complexity class of the problem is not known, the lack of a polynomial time
algorithm suggests that it might not be in $\mathcal{P}$. The perceived
difficulty of the problem made it the center piece of many cryptography
algorithms, including the RSA [1] cryptosystem, and thus forms a foundation of
modern information security.

In 1994, Peter Shor [2] showed that integer factorization can be solved
efficiently on a quantum computer, which was a historic milestone that greatly
increased interest in quantum computing. Today it’s estimated that the number
of physical qubits needed to break 2048-bit RSA is roughly 20 million [3],
which is far beyond the capabilities of today’s quantum computers.

In classical cryptography, ideas for reducing integer factorization to solving
Closest Vector Problem (CVP) on a lattice were first introduced by an
influential proposal by Claus-Peter Schnorr in 1991 [4]. The approach has been
seriously explored (eg: [5]), and successful applications were found outside
the realm of factoring. One of the primary bottlenecks is that the method
requires solving CVP on large lattices, with lattice dimension that scale
polynomially in $n=\log_{2}(N)$, the bitsize of the number $N$ to be factored.
In 2021, a follow up work by Schnorr [6] claimed to reduce the required
dimension of the lattice to $\mathcal{O}(\frac{n}{\log_{2}{n}})$, and thus
“destroy the RSA cryptosystem”. However, the claims in the paper are highly
debated [7], [8] and most experts believe the lattice dimension required is
much larger than what is claimed in [6]. Léo Ducas also published an open-
source implementation [9] of the proposed algorithm and the experimental
results confirmed that the proposed claims did not hold true.

A recent work by Yan et. al [10] claims to improve the drawbacks of [6] by
using a quantum heuristic optimizer for solving CVP on a lattice, instead of a
classical heuristic optimizer. They reuse the weak claim of [6], that solving
CVP on a lattice of dimension $\mathcal{O}(\frac{n}{\log_{2}{n}})$ would be
enough, and thus arrive at a quantum algorithm for factoring that requires
“sublinear” resources. They further extend this claim to report resource
estimate of only $37$ qubits for breaking RSA-128 and $372$ qubits for
breaking RSA-2048, which took the world by surprise [11] [12].

The paper by Yan et. al [10] led some people to believe that there’s been a
decisive advance on how to factor huge integers, and thereby break the RSA
cryptosystem, using a near-term quantum computer [11] [12]. From a technical
point of view, [13] gives a critique of the assumptions and points out
inconsistencies in the paper.

Many experts have argued [14] that the heuristic quantum optimization
algorithm - QAOA [15], used by [10] is not expected to provide any meaningful
speedup for solving CVP on a lattice and thus the algorithm proposed by [10]
does not lead to meaningful improvements over classical Schnorr’s algorithm.
Follow-up works [16] have also appeared which try to replace the QAOA based
quantum optimizer with other quantum heuristics that might perform better.
However, all of this misses a more fundamental flaw in the proposal, i.e.,
even if a perfect quantum optimizer existed for solving CVP on a lattice; the
classical assumption of using a sublinear lattice itself is flawed and hence
the proposal is not expected to work!

The goal of this paper is to

  * •

Provide a working implementation, with configurable hyper parameters, of a
hybrid algorithm that combines Schnorr’s classical lattice based algorithm for
integer factorization with a quantum optimizer for solving CVP on a lattice.

  * •

Use our implementation to refute the claims of [10] and show that using a
sublinear prime lattice with a brute-force based perfect quantum optimizer
succeeds for factoring RSA style random integers upto 80-bits but fails beyond
that. A QAOA based quantum optimizer performs much worse, as expected.

We hope our open-source implementation serves as a playground for the
community to empirically test the various unproved ideas in classical and
quantum algorithms for lattice based integer factorization. For example, to
the best of our knowledge, this is the first implementation of Schnorr’s
algorithm that succeeds in factoring upto 80-bit integers with a sublinear
lattice of dimension $26$.

##  II Implementation of Sublinear Resource Quantum Integer Factorization
(SQIF) Algorithm

Most of the pitfalls of the SQIF algorithm proposed by Yan et. al. [10] were
covered by [13]. Here, we mainly aim to focus on the pitfall that the claims
for requiring sublinear quantum resources are based on Schnorr’s algorithm
[6], whose efficiency and probability of success are unknown.

The classical Schnorr’s algorithm [6] is not known to scale efficiently, in
particular [9] did an experimental study that showed that the algorithm fails
for 40-bit numbers. The SQIF algorithm by Yan et. al. [10] builds on top of
the classical Schnorr’s algorithm, with minor modifications to the lattice
construction scheme, and proposes the use of a quantum computer to find higher
quality (closer) solutions to the CVP problem on a lattice. This leads to a
hybrid “classical+quantum” algorithm such that

  1. I.

Classical: Use the claims from [6] to reduce the integer factorization problem
to solving the (approximate) Closest Vector Problem (CVP), which is NP-hard
[17], on a lattice of dimension $m=\mathcal{O}(\frac{n}{\log_{2}{n}})$.

  2. II.

Quantum: Find an approximate solution to CVP on a lattice using a classical
heuristic method, like Babai’s algorithm [18], and further improve the
classical solution by considering all neighbouring $2^{m}$ lattice points in
the $m$-dimensional unit length cube around the classical solution. The second
optimization is done by finding ground states of an all to all connected Ising
Hamiltonian via a heuristic quantum optimizer like QAOA [15].

While experts of quantum computing have raised concerns [14] about QAOA’s
performance on finding ground states of the proposed Hamiltonian (i.e. step
II), we empirically show that the classical reductions of step I itself are
flawed and thus a hypothetical perfect quantum optimizer for step II would
also not help provide any meaningful improvement over classical Schnorr’s
algorithm.

Our observations are consistent with the experimental study conducted by Léo
Ducas [9] to test the claims of Schnorr’s factoring algorithm [6], where he
showed that using a sublinear sized lattice would not be sufficient for
obtaining enough factoring relations and that the required lattice dimension
would be much larger than what is claimed in [6].

In algorithm 1, we present an overview of the SQIF factorization algorithm and
we highlight all hyper-parameters of the algorithm, for a discussion of their
effect and values see Appendix A. For the details of the algorithm we refer
the reader to our implementation [19], or to the original proposal by Yan et.
al[10]

input : N

input : lattice_parameter

input : precision_parameter

input : smoothness_bound

input : num_energy_states_samples

input : qaoa_depth

input : method

begin

$\textit{n}\leftarrow\textit{lattice\\_dimension}(N,\textbf{{lattice\\_parameter}})$;

$sr\\_pairs\leftarrow\emptyset$

while  _$|sr\\_pairs|
<\textit{num\\_required\\_sr\\_pairs}(n,\textbf{{smoothness\\_bound}})$_ do

$B,t\leftarrow\textit{construct\\_random\\_closest\\_vector\\_problem}(n,\textbf{{precision\\_parameter}})$

$b_{opt},B,D,\mu\leftarrow\textit{approximate\\_cvp\\_using\\_babai}(B,t)$

$H\leftarrow\textit{construct\\_hamiltonian}(t,b_{opt},D,\mu)$

if  _$\textit{method}=\textit{QAOA}$_ then

$states\leftarrow\textit{sample\\_low\\_energy\\_states\\_using\\_qaoa}$(H,qaoa_depth)

else

$states\leftarrow\textit{brute\\_force\\_find\\_low\\_energy\\_states}$(H,num_energy_states_samples)

end if

$\textit{lattice\\_vectors}\leftarrow\textit{lattice\\_vectors\\_from\\_states}(states,B)$

$sr\\_pairs\leftarrow
sr\\_pairs\cup\textit{sr\\_pairs\\_from\\_lattice\\_vectors}(\textit{lattice\\_vectors},\textbf{{smoothness\\_bound}})$

end while

$A\leftarrow\textit{difference\\_of\\_exponents\\_matrix}(sr\\_pairs,N,\textbf{{smoothness\\_bound}})$

$\textit{factors}\leftarrow\emptyset$

for  _$z\in\textit{null\\_space}(A\textit{ mod }2)$_ do

$e\leftarrow\frac{1}{2}Az$

$X\leftarrow\prod_{e_{i}>0}p_{i}^{e_{i}}$

$Y\leftarrow\prod_{e_{i}<0}p_{i}^{-e_{i}}$

$\textit{factors}\leftarrow\textit{factors}\cup\\{gcd(X+Y,N),gcd(|X-Y|,N)\\}$

end for

return _factors_

end

Algorithm 1 Quantum Integer Factorization using Schnorr’s algorithm as
described in [10].

##  III Results

Our code can be found in [19]. We ran our code on a Google Cloud Platform
(GCP) a2-highgpu-1g virtual machine. Our code optimizes its performance by
moving linear algebra and vectorizable operations to the GPU.

The largest number tested in [10] was 261980999226229 which has 48-bits. We
ran our code against random numbers with 63, 70, 80, 90, 100, 120, 128 bits.
As Table. 1 shows our implementation succeeds in factoring numbers up to
80-bits long and then fails to factor larger numbers.

Note that the claim on page 5 of [10] that 372 qubits to break RSA-2048 means
that we need to use a lattice parameter of 2 for large numbers. Thus in our
work when using a lattice parameter of 1 fails we try a lattice parameter of
2. This works for the 70-bit case and then fails at 80-bit onwards. Note that
we kept doing this up 100 bits. For 120 and 128 bit numbers we only tried
lattice parameter of 1 since a lattice parameter of 2 would have been
infeasible to brute force.

# bits | N |  lattice parameter | # qubits | # SR-Pairs | method | success/fail |  # iterations to success
---|---|---|---|---|---|---|---
40 | 624911573291 | 1 | 11 | 247 | qaoa | success | 40
40 | 624911573291 | 1 | 11 | 247 | brute force | success | 40
48 | 261980999226229 | 1 | 12 | 291 | qaoa | success | 127
48 | 261980999226229 | 1 | 12 | 291 | brute force | success | 118
63 | 2393864445846808531 | 1 | 15 | 165 | qaoa | fail |
63 | 2393864445846808531 | 1 | 15 | 452 | brute force | success | 359
70 | 700821480830487125167 | 1 | 17 | 45 | brute force | fail |
70 | 700821480830487125167 | 2 | 23 | 479 | qaoa | fail |
70 | 700821480830487125167 | 2 | 23 | 1064 | brute force | success | 242
80 | 675789769078847752141081 | 2 | 26 | 1295 | brute force | fail |
90 | 928497021444492107802357067 | 1 | 15 | 1 | brute force | fail |
90 | 928497021444492107802357067 | 2 | 30 | 446 | brute force | fail |
100 | 729097431295829382764936159407 | 1 | 14 | 0 | brute force | fail |
100 | 729097431295829382764936159407 | 2 | 28 | 33 | brute force | fail |
120 | 925141703449007503130714828237701463 | 1 | 17 | 0 | brute force | fail |
128 | 275538060341916784483102145290705042411 | 1 | 18 | 0 | brute force | fail |
Table 1: Factorization Results

##  IV Conclusion

The Schnorr’s algorithm with a sub-linear lattice size fails to scale. Using
heuristic quantum optimizers to solve CVP on a lattice in the hope of speeding
up the process of finding SR pairs isn’t fruitful in this case since even if
we brute force all possibilities the algorithm still fails.

## References

  * Rivest  _et al._ [1978] R. L. Rivest, A. Shamir, and L. Adleman, Commun. ACM 21, 120–126 (1978).
  * Shor [1994] P. Shor, in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (1994) pp. 124–134.
  * Gidney and Ekerå [2021] C. Gidney and M. Ekerå, Quantum 5, 433 (2021).
  * Schnorr [1991] C. P. Schnorr, in  _Advances in Cryptology — EUROCRYPT ’91_, edited by D. W. Davies (Springer Berlin Heidelberg, Berlin, Heidelberg, 1991) pp. 281–293.
  * Vera [2010] A. I. Vera, A note on integer factorization using lattices (2010), arXiv:1003.5461 [cs.DS] .
  * Schnorr [2021] C. P. Schnorr, Fast factoring integers by svp algorithms, corrected, Cryptology ePrint Archive, Paper 2021/933 (2021), https://eprint.iacr.org/2021/933.
  * S [2021] D. S, Does schnorr’s 2021 factoring method show that the rsa cryptosystem is not secure?, Cryptography Stack Exchange (2021), [Online:] https://crypto.stackexchange.com/a/88601.
  * Ryan [2021] K. Ryan, Did https://eprint.iacr.org/2021/232 actually break rsa? probably not, and here’s why., Twitter (2021), [Online:] https://twitter.com/inf_0_/status/1367376526300172288.
  * Ducas [2021] L. Ducas, Testing schnorr’s factoring claim in sagemath, https://github.com/lducas/SchnorrGate (2021).
  * Yan  _et al._ [2022] B. Yan, Z. Tan, S. Wei, H. Jiang, W. Wang, H. Wang, L. Luo, Q. Duan, Y. Liu, W. Shi, Y. Fei, X. Meng, Y. Han, Z. Shan, J. Chen, X. Zhu, C. Zhang, F. Jin, H. Li, C. Song, Z. Wang, Z. Ma, H. Wang, and G.-L. Long, Factoring integers with sublinear resources on a superconducting quantum processor (2022), arXiv:2212.12372 [quant-ph] .
  * Castelvecchi [2023] D. Castelvecchi, Nature 613, 221 (2023).
  * Schneier [2023] B. Schneier, Breaking RSA with a quantum computer, Schneier on Security (2023).
  * Grebnev  _et al._ [2023] S. V. Grebnev, M. A. Gavreev, E. O. Kiktenko, A. P. Guglya, K. V. Kuchkin, A. R. Efimov, and A. K. Fedorov, Pitfalls of the sublinear qaoa-based factorization algorithm (2023), arXiv:2303.04656 [quant-ph] .
  * Aaronson [2023] S. Aaronson, Cargo cult quantum factoring, Shtetl-Optimized (2023), [Online:] https://scottaaronson.blog/?p=6957.
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph] .
  * Hegade and Solano [2023] N. N. Hegade and E. Solano, Digitized-counterdiabatic quantum factorization (2023), arXiv:2301.11005 [quant-ph] .
  * Dinur  _et al._ [2003] I. Dinur, G. Kindler, R. Raz, and S. Safra, Combinatorica 23, 205 (2003).
  * Babai [1986] L. Babai, Combinatorica 6, 1 (1986).
  * Khattar and Yosri [2023] T. Khattar and N. Yosri, https://github.com/google-research/google-research/tree/master/factoring_sqif (2023).

##  Appendix A Hyperparameters

###  A.1 Lattice Parameter and Lattice Dimension

In [10] the function for computing the lattice dimension is given in multiple
slightly different variations. We believe that Equation. 2 captures these
where lattice_parameter (l) is a hyperparameter, $N$ is the integer to be
factored and $m$ is the lattice dimension.

$\displaystyle n=\lfloor\log_{2}{N}\rceil$ (1) $\displaystyle
m=\lfloor\frac{l*n}{\lfloor\log_{2}{n\rceil}}\rfloor$ (2)

In [10] two values were used for the hyperparameter $l\in\\{1,2\\}$. In
general, a larger value of $\textit{lattice\\_parameter}(l)$ leads to a larger
lattice dimension, which corresponds to a higher probability of finding enough
good SR pairs (thus leading to a successful factorization) at the cost of
increasing the space and time complexity of the algorithm.

###  A.2 Precision parameter for lattice construction

A CVP consists of a matrix $B$ of basis vectors that define a lattice and a
target vector $t$. The precision parameter ($c$) affects the last row of $B$
and the final coordinate of $t$ as given by Equation. 3

$\displaystyle B_{n,c}=\begin{bmatrix}f(1)&0&\dots&0\\\ 0&f(2)&\dots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\dots&f(n)\\\ \lfloor
10^{c}\ln{p_{1}}\rceil&\lfloor 10^{c}\ln{p_{2}}\rceil&\dots&\lfloor
10^{c}\ln{p_{n}}\rceil\end{bmatrix}t=\begin{bmatrix}0\\\ \vdots\\\
10^{c}\ln{N}\end{bmatrix}$ (3)

where the function $f(i)$ for $i=1,...,n$ is a random permutation of $(\lceil
1/2\rceil,\lceil 2/2\rceil,...,\lceil n/2\rceil)$.

The determinant of the lattice is positively correlated with precision
parameter $c$. It is conjectured that probability of finding vectors close to
the target vector should be positively correlated with $c$, but it’s not clear
to us that why this should be true. In our work we used $c=4$

###  A.3 Smoothness bound $B_{2}$

A $B$-smooth number is a positive integer such that the largest prime that
divides it is $\leq B$. A $B$-smooth relation (SR) pair is a pair of integers
$(u,v)$ such that $u,v,\text{and}|u-vN|$ are all $B$-smooth. In Schnorr’s
algorithm, by construction, every point on the lattice can be mapped to a pair
of integers $(u,v)$ s.t. both $u$ and $v$ are $p_{m}$-smooth, however not all
of them are $B_{2}$ SR pairs, where $B_{2}$ is a hyperparameter.

In general, $B_{2}$ affects the algorithms as: 1) Higher the $B_{2}$ bound,
the easier it is to find SR-pairs $(u,v)$ that satisfy the constraint that
$|u-v*N|$ is $B_{2}$-smooth. Thus it increases the probability of finding
valid SR-pairs. 2) However, an increase in $B_{2}$ also leads to an increase
in the requirement for number of SR-pairs to sample, which increases the
overall runtime of the algorithm.

To factorize $N$, it is sufficient to find enough SR-pairs. It is typically
sufficient that the number of such SR-pairs is a few more than smoothness
bound $B_{2}$. In [10] they suggest that $B_{2}\sim 2m^{2}$.

###  A.4 Energy states specific hyperparameters

In our work we implemented two versions of the algorithm. The first (brute
forces) computes the energy of all of the $2^{m}$ states and returns the
num_energy_states_samples lowest enerergy states (we set
$\textbf{num\\_energy\\_states\\_samples}=2^{\text{min}(15,m)}$). The second
is the QAOA heuristic which constructs the circuit described in [10] with
depth qaoa_depth. In [10] the depth was $\in[1,3]$. In our work we used depth
$=2$.