# Quantum Carry Lookahead Adders for NISQ and Quantum Image Processing

Himanshu Thapliyal, Edgard Muñoz-Coreas and Vladislav Khalus  Department of
Electrical and Computer Engineering
University of Kentucky, Lexington, KY, USA
Email<EMAIL_ADDRESS>
###### Abstract

Progress in quantum hardware design is progressing toward machines of
sufficient size to begin realizing quantum algorithms in disciplines such as
encryption and physics. Quantum circuits for addition are crucial to realize
many quantum algorithms on these machines. Ideally, quantum circuits based on
fault-tolerant gates and error-correcting codes should be used as they
tolerant environmental noise. However, current machines called Noisy
Intermediate Scale Quantum (NISQ) machines cannot support the overhead
associated with fault-tolerant design. In response, low depth circuits such as
quantum carry lookahead adders (QCLA)s have caught the attention of
researchers. The risk for noise errors and decoherence increase as the number
of gate layers (or depth) in the circuit increases. This work presents an out-
of-place QCLA based on Clifford+T gates. The QCLAs optimized for T gate count
and make use of a novel uncomputation gate to save T gates. We base our QCLAs
on Clifford+T gates because they can eventually be made fault-tolerant with
error-correcting codes once quantum hardware that can support fault-tolerant
designs becomes available. We focus on T gate cost as the T gate is
significantly more costly to make fault-tolerant than the other Clifford+T
gates. The proposed QCLAs are compared and shown to be superior to existing
works in terms of T-count and therefore the total number of quantum gates.
Finally, we illustrate the application of the proposed QCLAs in quantum image
processing by presenting quantum circuits for bilinear interpolation.

##  I Introduction

Quantum computing offers significant speedups for algorithms for encryption,
searching and scientific computations [1] [2]. Arithmetic units such as adders
are needed to implementing many of these quantum algorithms. Thus, researchers
proposed adders for quantum computers [3] [4].

Existing quantum computers (Noisy Intermediate Scale Quantum (NISQ) machines)
are plagued by noise errors [5] [6]. Computations can fail due to quantum
operation errors and quantum coherence errors [5]. To reduce impact from
coherence errors, the depth (number of gate layers) should be minimized.

Thus, low depth arithmetic circuits (such as quantum carry lookahead (QCLA)
adders) have been proposed (see [7] [3] [4]). Out-of-place QCLAs (both inputs
restored and sum on ancillae) such as [8] [4] and [3] and in-place QCLAs (one
input restored and sum replaces other input) such as [4] [3] and [7] are
proposed. However, these works suffer from overhead in terms of T gates and
qubits. The fault-tolerant implementation cost of the T gate is higher
compared to other quantum gates (such as Clifford gates) [6] [9]. By using
recent developments such as improved Toffoli gate implementations (see [9]) we
can design QCLAs with low T gate and/or qubit overhead.

To overcome shortcomings in existing works, this work proposes a novel QCLA
for NISQ and fault-tolerant machines. In-place QCLA and out-of-place QCLA
implementations for the design are shown. Both designs enjoy reduced T gate
cost and qubit cost compared to the existing works. The proposed QCLAs use a
proposed uncomputation gate with a T-count of 3. The proposed uncomputation
gate allows the QCLAS to be used on NISQ machines. The proposed QCLA designs
are based on the NOT gate, CNOT gate, Toffoli gate, logical AND gate and the
novel uncomputation gate. The logical AND gate depicted in Figure 1 is
presented in [9]. The existing designs in [4] are based solely on CNOT, NOT
and Toffoli gates.

The proposed work modifies the design methodologies in [4] by replacing
Toffoli gate with logical-AND gate and uncomputation gate pairs into the
design where possible. The proposed uncomputation gate is used to avoid the
measurement operation required by the uncomputation gate proposed in [9]. We
seek to avoid the measurement operation because (i) the errors associated with
the operation (such as SPAM errors) and (ii) the increased length of time to
perform measurement compared to gates on NISQ machines. In consequence, the
number of T gates thereby the total number of quantum gates used in the
proposed design is significantly reduced compared to existing work.

Further, quantum computing has been applied to image orientation problems and
image pattern recognition [10] [11]. To implement quantum image processing
algorithms, images must be encoded on quantum hardware and circuits to
manipulate image representations must be designed. In this work, we illustrate
an example of a quantum circuit for quantum image processing by presenting
quantum circuits for bilinear interpolation based on the proposed QCLAs.

$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{\bullet}$ $\textstyle{T+}$
$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{T+}$
$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$
$\textstyle{\bullet}$$\textstyle{T}$$\textstyle{\bullet}$$\textstyle{H}$$\textstyle{S}$$\textstyle{{\left|{x\cdot
y}\right\rangle}}$$\textstyle{{\left|{x\cdot y}\right\rangle}}$ (a) The
temporary logical-AND gate and its Clifford+T gate implementation. T-count is
$4$. The T gate needed to produce the $|A\textrangle$ state is included in the
T gate cost of the logical AND gate (for a total of 4 T gates). Source: [9]

$\textstyle{{\left|{x}\right\rangle}}$ $\textstyle{T}$
$\textstyle{\bullet}$$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{x}\right\rangle}}$$\textstyle{{\left|{y}\right\rangle}}$
$\textstyle{T}$
$\textstyle{\bullet}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{y}\right\rangle}}$$\textstyle{{\left|{x\cdot
y}\right\rangle}}$$\textstyle{S^{{\dagger}}}$$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{T^{{\dagger}}}$$\textstyle{\bullet}$
$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{{\left|{x\cdot
y}\right\rangle}}$ (b) The proposed uncomputation gate and its Clifford+T gate
implementation. T-count is $3$.

Figure 1: Gates used in this work. ${\left|{A}\right\rangle}$ is an ancillae
in the state
$\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}+e^{\frac{i\cdot\pi}{4}}{\left|{1}\right\rangle})$.
---
$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{{\left|{s_{0}}\right\rangle}}$$\textstyle{{\left|{a_{0}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{0}}\right\rangle}}$$\textstyle{{\left|{b_{0}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{b_{0}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{{\left|{s_{1}}\right\rangle}}$$\textstyle{{\left|{a_{1}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{1}}\right\rangle}}$$\textstyle{{\left|{b_{1}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{b_{1}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{s_{2}}\right\rangle}}$$\textstyle{{\left|{a_{2}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{2}}\right\rangle}}$$\textstyle{{\left|{b_{2}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{s_{2}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{{\left|{s_{3}}\right\rangle}}$$\textstyle{{\left|{a_{3}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{3}}\right\rangle}}$$\textstyle{{\left|{b_{3}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{b_{3}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$
$\textstyle{{\left|{s_{4}}\right\rangle}}$ Figure 2: Proposed out-of-place
QCLA for the case of adding two $4$ bit values $a$ and $b$.

##  II Proposed Design of Out-of-Place QCLA Circuit

The $8$ step methodology to implement proposed out-of-place QCLA is generic
and can be used to implement a QCLA circuit of any size. The methodology is a
modified version of the design methodology presented in [4]. An example of the
proposed QCLA is shown in Figure 2. The proposed QCLA saves resources by using
the temporary logical-AND gate and proposed uncomputation gate where possible.

The proposed out-of-place QCLA circuit operates as follows: Given 2 values $a$
and $b$ (each $n$ bits wide) stored in quantum registers $A$ and $B$ as well
as $n+1$ ancillae stored in register $X$. $X_{0}$ is set to $0$ and the
remaining locations are set to $A$ $\left(\text{ where
}A=\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)\right)$.
The QCLA require a register $Z$ with $n-w(n)-\lfloor log(n)\rfloor$ elements
(where $w(n)=n-\sum_{y=1}^{\infty}\lfloor\frac{n}{2^{y}}\rfloor$ and is the
number of ones in the binary expansion of $n$) all set to $A$ $\left(\text{
where
}A=\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)\right)$.
At the end of computation, $A$ and $B$ are restored to their initial values
and $X$ will contain the sum of the addition of $a$ and $b$. The QCLA will
restore $Z$ to
$\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)$.
These qubits can be set to computational basis values for reuse as ancillae.
The steps to implement QCLA are shown along with an illustrative example of
the QCLA circuit in Figure 2

##  III Proposed Design of In-Place QCLA Circuit

The $16$ step methodology to implement proposed in-place QCLA is generic and
can be used to implement a QCLA circuit of any size. The methodology is a
modified version of the design methodology presented in [4]. An example of the
proposed QCLA is shown in Figure 3. The proposed QCLA saves resources by using
the temporary logical-AND gate and proposed uncomputation gate where possible.

The proposed QCLA operates as follows: Given 2 values $a$ and $b$ (each $n$
bits wide) stored in quantum registers $A$, $B$ and an $n$ bit register $Z$ of
ancillae set to
$\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)$.
Lastly, QCLA requires a $n-w(n)-\lfloor log(n)\rfloor$ (where
$w(n)=n-\sum_{y=1}^{\infty}\bigl{\lfloor}\frac{n}{2^{y}}\bigr{\rfloor}$ and is
the number of ones in the binary expansion of $n$) bit register of ancillae
($X$) set to
$\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)$.
At the end of computation, $A$ is restored to their initial values and $B$
will contain sum bits $0$ through $n-1$ of the addition of $a$ and $b$. At the
end of computation, $Z[n]$ will contain the sum bit $s_{n}$. The QCLA will
restore the remaining locations in $Z$ to
$\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)$.
The QCLA will restore $X$ to
$\frac{1}{\sqrt{2}}\left({\left|{0}\right\rangle}+e^{\frac{i\pi}{4}}{\left|{1}\right\rangle}\right)$.

---
$\textstyle{{\left|{a_{0}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{0}}\right\rangle}}$$\textstyle{{\left|{b_{0}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$
$\textstyle{{\left|{s_{0}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{1}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{1}}\right\rangle}}$$\textstyle{{\left|{b_{1}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$ $\textstyle{\bullet}$ $\textstyle{\bullet}$
$\textstyle{{\left|{s_{1}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$
$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{a_{2}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{2}}\right\rangle}}$$\textstyle{{\left|{b_{2}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$ $\textstyle{\bullet}$
$\textstyle{{\left|{s_{2}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\left|{A}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$
$\textstyle{{\left|{a_{3}}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\left|{a_{3}}\right\rangle}}$$\textstyle{{\left|{b_{3}}\right\rangle}}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{{\left|{s_{3}}\right\rangle}}$$\textstyle{{\left|{A}\right\rangle}}$
$\textstyle{{\left|{s_{4}}\right\rangle}}$ Figure 3: In-place QCLA for the
case of adding two $4$ bit values $a$ and $b$.

##  IV Performance of Proposed QCLA circuits

TABLE I: Cost Comparison of Out-of-place QCLAs Design |  | T-count Equation
---|---|---
Draper et al. ([4]) |  | $35n-21w(n)-21\lfloor log(n)\rfloor-7$
Thapliyal et al. ([3] ) |  | $35n-14$
Babu et. al. ([8])* |  | $54\cdot n$
Proposed |  | $25n-14w(n)-14\lfloor log(n)\rfloor-7$
$w(n)=n-\sum_{y=1}^{\infty}\bigl{\lfloor}\frac{n}{2^{y}}\bigr{\rfloor}$
* Circuits modified to remove garbage output. We use the methodology in [12] to remove the garbage output.
TABLE II: Cost Comparison of In-Place QCLAs Design |  |  T-count Equation
---|---|---
Draper et al. ([4]) |  |  $70n-21w(n)-21\lfloor log(n)\rfloor-21w(n-1)-21\lfloor log(n-1)\rfloor-49$
Thapliyal et al. ([3]) |  |  $\frac{203}{4}n-28$
Cheng et al. ([7]) |  |  $\frac{14}{6}n^{3}+\frac{21}{6}n^{2}-\frac{49}{6}n$
Proposed |  |  $46n-14w(n)-14\lfloor log(n)\rfloor-14w(n-1)-14\lfloor log(n-1)\rfloor-36$
$w(n)=n-\sum_{y=1}^{\infty}\bigl{\lfloor}\frac{n}{2^{y}}\bigr{\rfloor}$

Table I indicates the proposed out-of-place QCLA has T-count cost of order
$\mathcal{O}(n)$. The proposed QCLA requires $53.70\%$ fewer T gates than the
design by Babu et al., $28.57\%$ fewer T gates than the designs by Draper et
al. and Thapliyal et al.

Table II indicates that the proposed in-place QCLA has a T-count cost of order
$\mathcal{O}(n)$. The proposed in-place QCLA requires $34.29\%$ fewer T gates
than the designs by Draper et al., $9.36\%$ fewer T gates than the designs by
Thapliyal et al. and has a polynomial factor improvement over the work in
Cheng et al.

##  V Application in Quantum Image Processing

(a) Coordinate mapping of a bilinear interpolated image.

Figure 4: Application of quantum arithmetic circuits in image processing.

We will now illustrate how the proposed QCLAs can be used to implement a
quantum circuit for bilinear interpolation. Interpolation is of interest
because it is used in image processing operations such as zooming, rotations,
and resampling [13] [14]. Bilinear interpolation is a well established method
for scaling images [15]. Bilinear interpolation uses linear interpolation to
sequentially perform interpolation for each pixel location variable $x$ and
$y$. Figure 4(a) shows an example coordinate mapping of a bilinear
interpolated pixel at original location $(X,Y)$. Further details about
bilinear interpolation can be found in [15].

The QCLA circuits can be used to implement quantum circuits for bilinear
interpolation. We can build quantum circuits for scaling down and for scaling
up an image by an integer $n$. Scaling up by $n$ will increase an image by
$2^{n}$ and scaling down by $n$ will decrease an image by $2^{n}$. We show the
complete quantum bilinear interpolation circuit for the scale down operation
in Figure LABEL:bilinear-scale-down-image-complete. Both quantum bilinear
interpolation use a (i) quantum adder, (ii) quantum subtractor and (iii)
quantum multiplier. The required block of quantum adder, quantum subtractor
and quantum multiplier can be easily designed from the proposed quantum carry
lookahead adders [16]. As an illustrative example, we have shown a quantum
integer multiplication circuit that is optimized for T-count and qubits [17].
The building blocks of the quantum integer multiplication circuit are (i)
quantum Ctrl-Add circuit and (ii) arrays of Toffoli gates. The quantum Ctrl-
Add circuit is based on a resource efficient quantum carry look-ahead adders
presented in this work. Figure 5 shows an example of the proposed multiplier
for the case of multiplying two $6$ bit integers. In Figure 5, quantum
registers ${\left|{A}\right\rangle}$ and ${\left|{B}\right\rangle}$ contain
the inputs $a$ and $b$ to be multiplied. The proposed quantum integer
multiplication circuit implements the shift and add multiplication algorithm.
The placement of the Ctrl-Add circuits eliminates the need for gates to
implement the shifting operation (see Figure 5). To reduce gate cost Ctrl-Add
circuits are replaced by Toffoli gate arrays where possible.

Figure 5: Example of the proposed quantum integer multiplication circuit for
the multiplication of two $6$-bit inputs ${\left|{A}\right\rangle}$ and
${\left|{B}\right\rangle}$. ${\left|{P}\right\rangle}$ is the product of the
values in ${\left|{A}\right\rangle}$ and ${\left|{B}\right\rangle}$.

We follow the procedures in [16] to implement both quantum bilinear
interpolation circuits. Both circuits take the original pixel’s position
${\left|{Y}\right\rangle},{\left|{X}\right\rangle}$ and color information
${\left|{C_{Y,X}}\right\rangle}$ as inputs. The color information for pixels
at locations ($y+1,x$), ($y,x+1$) and ($y+1,x+1$) are also inputs. The
circuitry outputs the scaled pixel’s location
${\left|{\overline{Y}}\right\rangle}$ and
${\left|{\overline{X}}\right\rangle}$ and its color information
${\left|{C_{\overline{Y},\overline{X}}}\right\rangle}$.

We determine the location information for the scaled pixel without gates by
either appending ancillae or truncating the input location values. The quantum
bilinear interpolation circuit to scale down an image evaluates expression 1
for the scaled color value:

$\left[\begin{matrix}(2^{n}-{\left|{\widetilde{Y}}\right\rangle})\cdot(2^{n}-{\left|{\widetilde{X}}\right\rangle})\cdot
C_{Y,X}+\\\
{\left|{\widetilde{Y}}\right\rangle}\cdot(2^{n}-{\left|{\widetilde{X}}\right\rangle})\cdot
C_{Y+1,X}+\\\
(2^{n}-{\left|{\widetilde{Y}}\right\rangle}\cdot{\left|{\widetilde{X}}\right\rangle})\cdot
C_{Y,X+1}+\\\
{\left|{\widetilde{Y}}\right\rangle}\cdot{\left|{\widetilde{X}}\right\rangle})\cdot
C_{Y+1,X+1}\\\ \end{matrix}\right]\div 2^{2\cdot n}$ (1)

Where $\widetilde{Y}=Y_{n-1:0}$ and $\widetilde{X}=X_{n-1:0}$. The quantum
bilinear interpolation circuit to scale up an image evaluates expression 2 for
the scaled color value:

$\left[\begin{matrix}\left(2^{m}-{\left|{\widetilde{Y}}\right\rangle}\right)\cdot\left(2^{m}-{\left|{\widetilde{X}}\right\rangle}\right)\cdot
C_{Y,X}+\\\
\left({\left|{\widetilde{Y}}\right\rangle}\right)\cdot(2^{m}-\left({\left|{\widetilde{X}}\right\rangle}\right)\cdot
C_{Y+1,X}+\\\
\left(2^{m}-{\left|{\widetilde{Y}}\right\rangle}\right)\cdot\left({\left|{\widetilde{X}}\right\rangle}\right)\cdot
C_{Y,X+1}+\\\
\left({\left|{\widetilde{Y}}\right\rangle}\right)\cdot\left({\left|{\widetilde{X}}\right\rangle}\right)\cdot
C_{Y+1,X+1}\\\ \end{matrix}\right]\div 2^{2\cdot m}$ (2)

Where $\widetilde{Y}=\overline{Y_{m+n-1:n-1}}$ and
$\widetilde{X}=\overline{X_{m+n-1:n-1}}$.

Details of the design of the quantum bilinear interpolation circuits for the
scale down operation and for the scale up operation are illustrated in [16].
We determine $\left(C_{\overline{Y},\overline{X}}\right)$ for both circuits
without division by truncating the quantum register containing the result of
computation (see Figure LABEL:bilinear-scale-down-image-complete).

##  VI Conclusion

In this work, we propose quantum circuits for carry lookahead addition for
NISQ machines. We propose designs for an in-place QCLA and out-of-place QCLA.
The proposed QCLAs are optimized for low T gate cost. The proposed QCLAs are
based on the NOT gate, the CNOT gate, the Toffoli gate, the logical AND gate
and the proposed uncomputation gate. These designs are compared and shown to
have reduced T gate and therefore total number of quantum gates compared to
the existing work. The proposed QCLAs also enjoy qubit cost savings compared
to existing work. We conclude that the proposed in-place QCLA and out-of-place
QCLA can be used in larger quantum data-path circuits in NISQ machines or when
fault-tolerant quantum circuit design is not possible. We also illustrate the
application of the proposed QCLAs in image processing through the example of
circuits for quantum bilinear interpolation.

## References

  * [1] S. Caraiman and V. Manta, “Image processing using quantum computing,” in _2012 16th International Conference on System Theory, Control and Computing (ICSTCC)_. IEEE, October 2012, pp. 1–6.
  * [2] L. Novo and D. Berry, “Improved hamiltonian simulation via a truncated taylor series and corrections,” _Quantum Information and Computation_ , vol. 17, no. 7-8, pp. 623–635, 2017.
  * [3] H. Thapliyal, H. Jayashree, A. Nagamani, and H. Arabnia, “Progress in reversible processor design: A novel methodology for reversible carry look-ahead adder,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 7420, pp. 73–97, 2013.
  * [4] T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, “A logarithmic-depth quantum carry-lookahead adder,” _Quantum Information and Computation_ , vol. 6, no. 4-5, pp. 351–369, 2006.
  * [5] I. Rigetti & Co, “Think quantum,” 2020. [Online]. Available: https://rigetti.com/
  * [6] S. J. Devitt, A. M. Stephens, W. J. Munro, and K. Nemoto, “Requirements for fault-tolerant factoring on an atom-optics quantum computer,” _Nature Communications_ , vol. 4, 2013.
  * [7] K.-W. Cheng and C.-C. Tseng, “Quantum plain and carry look-ahead adders,” _arXiv e-prints_ , 2002. [Online]. Available: https://arxiv.org/abs/quant-ph/0206028
  * [8] H. M. H. Babu, L. Jamal, and N. Saleheen, “An efficient approach for designing a reversible fault tolerant n-bit carry look-ahead adder,” in _2013 IEEE International SOC Conference_ , Sep. 2013, pp. 98–103.
  * [9] C. Gidney, “Halving the cost of quantum addition,” _Quantum_ , vol. 2, p. 74, Jun. 2018. [Online]. Available: https://doi.org/10.22331/q-2018-06-18-74
  * [10] G. Beach, C. Lomont, and C. Cohen, “Quantum image processing (quip),” vol. 2003-. Institute of Electrical and Electronics Engineers Inc., 2004, pp. 39–44.
  * [11] S. Venegas-Andraca, M. Lanzagorta, and J. Uhlmann, “Maritime applications of quantum computation,” in _OCEANS 2015 - MTS/IEEE Washington_. Institute of Electrical and Electronics Engineers Inc., 2016.
  * [12] C. H. Bennett, “Logical reversibility of computation,” _IBM J. Res. Dev._ , vol. 17, no. 6, pp. 525–532, Nov. 1973. [Online]. Available: http://dx.doi.org/10.1147/rd.176.0525
  * [13] H. Kim, Y. Cha, and S. Kim, “Curvature interpolation method for image zooming,” vol. 20, no. 7, pp. 1895–1903, 2011.
  * [14] P.-Y. Chen, C.-Y. Lien, and C.-P. Lu, “Vlsi implementation of an edge-oriented image scaling processor,” vol. 17, no. 9, pp. 1275–1284, 2009.
  * [15] R. C. Gonzalez, _Digital image processing_. Reading, Mass.: Addison-Wesley, 1992.
  * [16] E. Muñoz-Coreas and H. Thapliyal, “T-count Optimized Quantum Circuits for Bilinear Interpolation,” _arXiv e-prints_ , Sep. 2018. [Online]. Available: https://arxiv.org/abs/1809.09249
  * [17] E. Munoz-Coreas and H. Thapliyal, “Quantum circuit design of a t-count optimized integer multiplier,” _IEEE Transactions on Computers_ , vol. 68, no. 5, pp. 729–739, 2019.


# Federated Learning in Mobile Edge Computing: An Edge-Learning Perspective
for Beyond 5G

Shashank Jere, Qiang Fan, Bodong Shang, Lianjun Li, and Lingjia Liu The
authors are with the Bradley Department of Electrical and Computer
Engineering, Virginia Tech, Blacksburg, VA, USA.The corresponding author is L.
Liu (ljliu@ieee.org).

###### Abstract

Owing to the large volume of sensed data from the enormous number of IoT
devices in operation today, centralized machine learning algorithms operating
on such data incur an unbearable training time, and thus cannot satisfy the
requirements of delay-sensitive inference applications. By provisioning
computing resources at the network edge, Mobile Edge Computing (MEC) has
become a promising technology capable of collaborating with distributed IoT
devices to facilitate federated learning, and thus realize real-time training.
However, considering the large volume of sensed data and the limited resources
of both edge servers and IoT devices, it is challenging to ensure the training
efficiency and accuracy of delay-sensitive training tasks. Thus, in this
paper, we design a novel edge computing-assisted federated learning framework,
in which the communication constraints between IoT devices and edge servers
and the effect of various IoT devices on the training accuracy are taken into
account. On one hand, we employ machine learning methods to dynamically
configure the communication resources in real-time to accelerate the
interactions between IoT devices and edge servers, thus improving the training
efficiency of federated learning. On the other hand, as various IoT devices
have different training datasets which have varying influence on the accuracy
of the global model derived at the edge server, an IoT device selection scheme
is designed to improve the training accuracy under the resource constraints at
edge servers. Extensive simulations have been conducted to demonstrate the
performance of the introduced edge computing-assisted federated learning
framework.

###### Index Terms:

Mobile Edge Computing (MEC), Federated Learning (FL), Internet of Things
(IoT), Multiple Input Multiple Output (MIMO), Resource Allocation,
Communication latency, Communication cost, and Data privacy

##  I Introduction

The number of IoT devices is expected to increase exponentially in the next
decade [1]. Due to the large number of connected Internet of Things (IoT)
devices, the worldwide IP traffic is projected to grow to $400$ Exabytes per
month by $2022$. As the computational and communication capabilities of such
devices continue to improve, there is growing interest in harnessing their
capabilities for machine learning applications [2]. The complex and
heterogeneous nature of problems likely to be encountered in the context of
next-generation Beyond-$5$G cellular networks, especially with the adoption of
modern techniques such as ultra-massive MIMO, millimeter-wave (mmWave) usage,
beamforming, etc. is demonstrating traditional model-based techniques to be
insufficient in finding optimal solutions to such problems [3]. Additionally,
domain-specific knowledge, which is a characteristic of datasets generated
during network operation, can be used to provide for better interpretation of
the training data, leading to better trained models [4]. Based on the data
streams generated by IoT devices, some IoT applications such as autonomous
vehicles, environment monitoring and augmented reality can employ machine
learning methods (such as deep neural networks) to train a learning model to
make the right decision timely, thus satisfying their real-time control
requirements. Specifically, the remote cloud can collect the data streams
generated from various IoT devices and train a global model in a centralized
way. Subsequently, the global model will be feedbacked from the cloud to IoT
devices for inference tasks. However, owing to the huge volume of IoT devices
and the long communications delay, the training time is almost always
infeasible for delay-sensitive applications, whose models may be time-varying
in the highly dynamic environment. To solve this problem, mobile edge
computing, a computational paradigm that places computing resources at the
network edge [5] is integrated with the local computing resources of IoT
devices to execute training tasks in a decentralized way (i.e., federated
learning). Due to the rapid development in hardware platforms for end user
devices, each IoT device can employ its local computing resources to train a
local model based on its limited local dataset, the parameters of which are
then transferred to the edge servers for further processing. After aggregating
all model parameters from various IoT devices, the edge server can summarize
the model parameters and derive the corresponding global model. Since both the
local training tasks and the parameters transfer have a comparatively lower
delay, the training time for the global model is significantly reduced.

In Federated Learning (FL), both training time and global model accuracy are
crucial metrics. On one hand, the training time for the global model is
impacted by the local training process and the communications delay between
IoT devices and the edge server. Thus, reducing this communications delay
becomes a critical issue. As the wireless channel environments are highly
dynamic and local model parameters at different IoT devices are transmitted to
the edge server at different times, the available radio resources in the
network are time-varying. Meanwhile, as the future traffic load is
unpredictable, the radio resource allocations for different traffic tasks
(i.e., model parameters) are coupled with each other. In other words, if the
system allocates too many wireless channels for one traffic task owing to its
desirable channel condition, the subsequent tasks may not get enough radio
resources and thus violate the QoS requirement. On the other hand, this may
degrade the model accuracy in federated learning since the global model is
derived based on local model parameters, contrary to centralized machine
learning in the remote cloud. Therefore, global model accuracy remains an
important problem in federated learning especially when the computing and
storage resources of edge servers are limited.

To solve the above problem, we design a novel edge computing assisted
federated learning framework that aims to improve both the training time and
training accuracy in the network. The major contributions are summarized as
follows:

  * •

We introduce an edge computing assisted federated learning framework and
analyze its potential in improving the training efficiency.

  * •

We present the problem of improving the communications delay incurred in
transferring model parameters to edge servers and propose a reinforcement
learning based algorithm to solve it in real time.

  * •

We present the problem of selecting IoT devices for federated learning based
on their different weights in enhancing the training accuracy while the
computing and storage resources of the edge server are limited.

##  II State-of-the-Art

###  II-A Multi-Access Edge Computing

Although mobile cloud computing [6] has been a successful paradigm in bringing
richer and more complex applications to end users by harnessing the power of
the server cloud, extremely sensitive latency requirements have demanded an
alternate approach [5]. Driven by the complex traffic distributions in
wireless communications systems, the network architecture is becoming
increasingly heterogeneous. There are multiple types of network access nodes
providing reliable and seamless connectivity for mobile users such as macro
base station (BS), small cell BS and WiFi access point, to name a few. These
network access nodes support edge computing at network edges with low
transmission latency. Due to the different characteristics of network access
nodes such as coverage ability and transmit power, the design of the
coexistence of heterogeneous MEC networks has attracted increasing attention
[5]. The cooperative computation offloading between multiple different network
access nodes for mobile users needs to be well-designed.

Under such a heterogeneous network architecture, the task allocation and
resource allocation among different network nodes can significantly improve
system performance. On one hand, cooperation between edge computing and cloud
computing can be achieved to enhance the quality of service of IoT tasks
further. Specifically, cloud servers can process tasks that require intensive
computation, while edge servers can process computation tasks that entail a
small data size or have a low latency requirement [7]. On the other hand, the
task allocation among edge servers can effectively offload tasks from
overloaded edge servers to underutilized ones, and thus reduce the execution
delay of tasks [8].

###  II-B A Primer on Federated Learning (FL)

A traditional cloud-only based machine learning approach offloads data sensed
at end devices to the remote cloud server for centralized training in order to
learn the model for future inference. However, the training time at the cloud
may be impractical owing to the large volume of the sensed data that needs to
be utilized in the training process. Meanwhile, as the cloud server may be
physically distant from the end devices, these devices may suffer from large
communication delays. To solve this problem, federated learning facilitated by
MEC can be a promising approach to shift from a centralized training paradigm
to a more practical decentralized training one. Federated Learning (FL) [9]
aggregates the results of distributed training models at different end devices
based on their local datasets, and cooperatively derives the global training
model. Specifically, each device can train its local model based on its own
limited dataset efficiently and update the local model parameters to an
aggregator at the edge server. The aggregator then utilizes each learner’s
local model parameter updates to optimize a global model. This can be repeated
for a number of iterations to ensure the global model reaches a desired
accuracy. Subsequently, the global model parameters are fed back to the
distributed devices for future inference.

Federated Learning distinguishes itself from other distributed learning
schemes owing to certain unique factors. Firstly, the assumption that the data
samples sensed at the end devices of different users are realizations of
independent and identically distributed (IID) random variables may not hold in
FL, since the local dataset of a single user’s end device may not be
representative of the overall population distribution. Secondly, the local
datasets generated across federated learners may differ greatly in size,
causing an imbalanced distribution. This imbalance in dataset sizes are
primarily due to the different types of IoT devices (e.g., smartphone or
vehicle) and different application scenarios (e.g., a maps application on a
smartphone may generate more data for an active city user than a less active
rural user). Thirdly, in the FL setting, the total amount of sensed data
samples contributing towards learning the global model at the edge server is
much larger than that available for local training at each user. Finally, most
federated learners are mobile devices (e.g., smartphones, wearables, drones,
vehicles, etc.) with possibly unreliable wireless connectivity to the FL edge
server. This implies that the aggregator may have to support learners that may
be offline or experience slow connectivity. In the context of these
aforementioned differentiating factors [9], FL provides advantages not
available in other decentralized ML approaches, namely, user-data privacy,
efficient network resource usage and reduced end-to-end latency.

##  III Federated Learning Facilitated by Mobile Edge Computing

FL and MEC have a promising synergy that is particularly well-suited for use
cases proposed for Beyond-$5$G. Figure 1 describes the basic concept of MEC
with a single edge server that provisions services for a large number of IoT
devices. The Quality of Service (QoS) of the notable delay-sensitive
applications such as AR/VR, drone-based communications and Vehicle-to-
Infrastructure (V2I) communications, will be heavily impacted by the overall
round-trip latency between the edge server and distributed IoT devices.

In this section, we will present the edge computing-assisted federated
learning framework in which both the training efficiency and training accuracy
will be taken into account. Firstly, minimizing communication latency will
accelerate the mutual interactions between IoT devices and the edge server,
thus reducing the training time of a global model in various applications. To
reduce the communications delay of local model parameters, we investigate this
problem in Section III-A. Secondly, as the network involves heterogeneous
devices, the different datasets enable various IoT devices’ local model
parameters to have different weight on the global model accuracy. Meanwhile,
considering the huge number of IoT devices and the limiting processing
capability of each edge server, it is challenging to select the suitable IoT
devices to optimize the global model accuracy. This optimization problem that
attempts to maximize training accuracy while being constrained by both channel
conditions of end devices as well as the computational resources at the edge
server is set up in Section III-B.

Figure 1: General MEC Architecture

###  III-A Communications for Federated Learning

Under the FL setting, different end devices need to transfer the updated model
parameters to an edge server that can finally summarize the global model. In
this case, the communications latency becomes an important factor determining
the performance of the aggregated model. In other words, a low communications
latency can enable end devices to transfer their local model parameter updates
quickly, and thus reduce the total delay for deriving the global model.

These devices may have different channel conditions towards a BS and thus
require different volume of spectrum resources to transfer their traffic tasks
(which are generated by local training). Given a traffic task of each end
device, we need to focus on two factors: 1) how to allocate spectrum resources
to improve the communications latency of all tasks; 2) how to guarantee QoS
requirement of different tasks in terms of the maximum communications latency
requirement. Since latency is a critical metric for FL, it is desirable to
minimize the communications latency for as many traffic tasks as possible. On
the other hand, although some IoT devices may have unsatisfactory channel
conditions, we still need to allocate the required resources to their tasks to
meet their QoS requirement, thus ensuring the reliability of FL in the system.
Here, denote $\beta$ as a spectrum resource block, $\eta_{i}$ as the spectral
efficiency (bits/sec/Hz) based on the corresponding end device’s channel
condition, $x_{i}$ as the number of resource blocks allocated to task $i$, and
$l_{i}$ as the length of task $i$. The communications delay of task $i$ is
hence derived as $\frac{{{l_{i}}}}{{x_{i}\beta{\eta_{i}}}}$. Meanwhile, $\tau$
is the maximum delay requirement for a task and $W_{0}$ is the total bandwidth
of the wireless channel. Therefore, the resource allocation problem can be
formulated as follows:

_Given:_

  * •

The length of all traffic tasks.

  * •

The channel conditions of end devices where traffic tasks are generated.

  * •

The transmission power of end devices and the total resource blocks of the
system (i.e., the total bandwidth).

  * •

The QoS requirement of different tasks.

_Obtain:_

  * •

The number of resource blocks allocated to each task.

_Objective:_

  * •

Minimize the average communications delay of traffic tasks, while guaranteeing
the communications delay requirement of each task.

As a mobile end device may visit several locations, it may have time-varying
channel conditions and may generate different traffic tasks at different
times. Note that the resource allocation for the current task and future tasks
are coupled with each other. The optimal resource allocation decision relies
on the complete global network information such as task information. However,
owing to the difficulty of predicting future task information in advance, it
is impractical to optimize the resource allocation. Furthermore, as the above
resource allocation problem is an integer non-linear problem and the number of
end devices may be exceedingly large, it is also challenging to arrive at an
optimal solution in real-time. Thus, a data-driven approach such as
reinforcement learning (RL) can be adopted to iteratively learn the features
of the problem based on historical data and achieve a sub-optimal solution.
Specifically, we can design the state of the system to represent 1) the
channel condition of IoT devices 2) the available spectrum resource, and 3)
the traffic length of the arriving task, while the action can represent the
number of resource blocks estimated to be allocated to the arriving task. The
agent at the edge server can be trained to learn the policy (i.e., how to
conduct the desirable action based on the current state) to maximize the
reward (i.e., reciprocal of the average communications delay of tasks). Thus,
the system can react to the changing network status quickly and allocate
proper resources to different traffic tasks in real-time, thereby improving
their communications delay. Figure 2 depicts the spectrum resource allocation
tasks undertaken by the edge server.

Figure 2: Resource allocation in communications for Federated Learning

###  III-B Mobile Edge Computing-assisted Federated Learning

In this section, the model accuracy of the framework is investigated under the
constraints of wireless channels and limited storage and computing resources
of edge servers. Since the participating learners include IoT devices such as
sensors, drones, autonomous vehicles and smart wearable devices along with
smartphones, their ability to upload model state information updates to their
corresponding edge servers is highly dependent on their respective channel
conditions. Meanwhile, considering the limited storage and computing resources
of edge servers, the total number of IoT devices in the network is expected to
be much larger than the number of devices that the edge server can accommodate
in a given training round. The role of IoT devices in contributing to the
global model of FL is vastly different from their roles in generic distributed
ML approaches. This is due to their unique distinguishing features which
include their unreliable wireless channel conditions, widely-varying local
dataset sizes, limited on-device processing capabilities and device energy
constraints. The focus here is to introduce an optimal learner selection
method in each training round before the global aggregation phase occurs.

Figure 3: Federated Learning under wireless channel constraints

In the following description, a local model refers to the model trained
locally at each participating end device, while the global model refers to the
model aggregated by the edge server. As shown in Figure 3, we consider an FL
network with multiple end devices being served by a single edge server. Denote
$I$ as the set of all end devices, the size of which is $N$. Initially, the
edge server publishes the global model parameters to all the participating
devices. In each training round, the participant devices use their respective
local datasets and compute updates to their local models based on new sensed
data, which are subsequently sent to the edge server. At the end of each
training round, the edge server aggregates these local updates, derives and
sends back the updated global model parameters. In practice, most often the
aggregation simply amounts to a weighted average [9], however this may vary.
The local model update and parameter aggregation are repeated until the global
loss function (typically an average of local loss functions) converges.

To train a global model repeatedly, end devices have to complete their local
training tasks and transfer the local model parameters within each training
around. We denote $t=T_{\text{upd}}$ as the duration of a training round,
after which the edge server commences global model aggregation. If the model
parameters of an end device cannot meet the constraint of $T_{\text{upd}}$,
the device has no contributions on the global training task. In addition,
realizing that training machine learning models is typically resource-
intensive, it is imperative to strive for optimal operation of the training
task to avoid resource wastage. These resources may be in the form of
bandwidth, time, energy, cost, etc. In this context, let $L_{\text{max}}$ be
the maximum volume of local model parameters that the edge server can process.
Such a constraint is very relevant, since a practical requirement for
deploying FL would be to minimize communication delay, analogous to minimizing
control plane signaling latency in packet switched networks. Also, let
$\tau_{\text{comp},i}$ be the delay incurred in computing local model updates
at participating device $i$ in a given training round. This delay is dictated
by the on-device processing capabilities. For a particular device, given its
computational intensity $\alpha$ at an end device (i.e., the number of CPU
(Central Processing Unit) cycles needed to process one bit of data sensed by
the device) and its computation capacity $C_{i}$ (in CPU cycles/second), the
computing delay $\tau_{\text{comp},i}$ can be expressed as
$\tau_{\text{comp},i}=\alpha D_{i}/C_{i}$. Similarly, let
$\tau_{\text{comm},i}$ be the communications delay incurred in transferring
the local model update from device $i$ to the edge server. Note that this
communications delay is a function of the channel condition $h_{i}$ from the
device to the edge server, the bandwidth $B_{\text{ch}}$ used by this
connection, and the data size of its local model update $l_{i}$. Thus,
$\tau_{\text{comm},i}$ can be defined as $\tau_{\text{comm},i}=l_{i}/r_{i}$,
where $r_{i}$ is the data rate supported by this connection. On the other
hand, as end devices train their local models based on the local datasets, the
size of a dataset directly impacts the accuracy of an end device’s model
parameters. To better reflect the contribution of an end device in deriving
the global model, we define $w_{i}=D_{i}/\sum\limits_{i=1}^{N}D_{i}$ as the
weight of each device which is proportional to the size of its own local
dataset. Denote $X_{i}$ as the indicator variable that represents the
selection of device $i$ for the current training round. Therefore, the problem
of optimizing the global model accuracy can be formulated as follows:

$\displaystyle\mathop{\max}\limits_{{X_{i}}}$
$\displaystyle\sum_{i=1}^{N}{w_{i}}{X_{i}}$ (1) $\displaystyle
s.t.\sum_{i=1}^{N}{X_{i}}{l_{i}}$ $\displaystyle\leq L_{\text{max}},\
\forall~{}i\in I,$ $\displaystyle{X_{i}}$ $\displaystyle=\\{0,1\\},\
\forall~{}i\in I,$ $\displaystyle\tau_{\text{comp},i}+\tau_{\text{comm},i}$
$\displaystyle\leq T_{\text{upd}},\ \forall~{}i\in I.$

Here, the first constraint imposes the total collected model parameters to be
no more than the capacity of the edge server, in terms of the maximize size of
parameters that can be processed. The second constraint indicates that each
end device can be selected or removed by the edge server. The third constraint
imposes the local training time and communications delay to be less than the
training round time. Note that the size of the local model update $l_{i}$, can
differ from one participant to another. This is especially true in cases where
the participating devices are responsible for training a different part of the
same global model. This assumption also aligns well with non-IID assumption of
the local datasets. Figure 3 depicts the participant selection process in one
training round of FL.

The above participant selection problem can be transformed to a well-known
$0/1$ Knapsack problem, which poses challenges in achieving the optimal
solution due to the high computational complexity especially for a large
number of end devices. To arrive at an efficient solution, we design a greedy
algorithm to solve the problem in polynomial-time such that the objective
value $\sum_{i=1}^{M}{w_{i}}{X_{i}}$ is maximized, thereby reflecting the
accuracy of the global model. The detailed procedure of the algorithm is
described as follows. In each training round, we first obtain a set of devices
that meet the delay constraint described in Equation (1). Subsequently, we
calculate the weight $z_{i}=w_{i}/l_{i}$ for all devices in the set, and sort
them in descending order of their weights. Subsequently, the end device with
the highest $z_{i}$ is iteratively selected by the edge server until the edge
server cannot accommodate more end devices due to the constraint on its
capacity $L_{\text{max}}$. In this manner, the accuracy of the global model in
the edge server is improved by selecting such devices that collect more sensed
data to train their local models.

###  III-C Simulation Results

To further verify the performance of the designed algorithm, we set up a
simulation and compare it with a baseline algorithm (i.e., Best-SINR
algorithm). The basic idea of the Best-SINR algorithm is to select devices
with the best channel conditions, akin to the widely-used user association
mechanism in wireless networks. In this simulation, we consider three
categories of devices, namely, smartphones, vehicles and low-power IoT
sensors, where the proportion of each category of devices is pre-defined. To
be specific, for any given $N$, we assign $50\%$ of the devices as
smartphones, $30\%$ as vehicles and $20\%$ as IoT sensors. The devices are
randomly distributed in a $1$ $\text{km}^{2}$ area. Their training dataset
sizes are set according to a normal distribution (i.e., $\mathcal{N}$($\mu$,
$\sigma^{2}$)), with each device category having a specific mean value
$\mu_{D_{i}}$. Meanwhile, we choose $l_{i}$ for each device based on a normal
distribution as well. The transmission power $P_{t}$ of each device is set at
$200$ mW, and we employ the following pathloss (PL) model from $3$GPP [10],
i.e., $PL\text{(dB)}=128.1+37.6\log_{10}d$, where $d$ is the distance in
kilometers. The remaining simulation parameters have been defined in Table I.

TABLE I: Simulation Parameters - Definitions and Values used Parameter | Definition | Value
---|---|---
Service area | Coverage area served by Edge Server |  $1$ km2
$N$ | Number of users present in Service area |  $300$ (Fig. 4)
$\alpha$ | Computational intensity |  $0.5$ (CPU cycles/bit)
$T_{\text{upd}}$ | Global model update period |  $120$ ms
$L_{\text{max}}$ | Aggregator Capacity |  $1$ MB (Fig. 5)
$B_{\text{ch}}$ | Channel bandwidth per user |  $180\text{kHz}$ $\triangleq$ 1 RB (Resource Block)
$P_{t}$ | Transmit Power per user |  $200$ mW
$N_{0}$ | Noise Spectral Density |  $-174$ dBm/Hz
$\mu_{D_{1}}$ | Mean size of training dataset for smartphones |  $150$ kB
$\mu_{D_{2}}$ | Mean size of training dataset for vehicles |  $250$ kB
$\mu_{D_{3}}$ | Mean size of training dataset for IoT sensors |  $100$ kB
$\sigma_{D}$ | Standard deviation of training dataset for all device types |  $20$ kB
$\mu_{l}$ | Mean parameter update length |  $10$ kB
$\sigma_{l}$ | Standard deviation of parameter update length |  $2$ kB
${C_{1}}$ | Computational capacity of smartphones |  $1\text{\times}{10}^{6}$ CPU cycles/sec
${C_{2}}$ | Computational capacity of vehicles |  $2\text{\times}{10}^{6}$ CPU cycles/sec
${C_{3}}$ | Computational capacity of IoT sensors |  $5\text{\times}{10}^{5}$ CPU cycles/sec

Figure 4 illustrates the impact of the edge server’s aggregator capacity
$L_{\text{max}}$ on the objective value. It can be seen that the greedy
algorithm is able to consistently achieve a higher objective value compared to
the baseline over a wide range of aggregator capacity $L_{\text{max}}$. This
is attributed to the fact that the greedy algorithm prefers to select devices
with a larger local training dataset and thus ensures a higher accuracy of the
global model for a given capacity limitation of the aggregator at the edge
server. In contrast, the Best-SINR algorithm simply selects devices in its
vicinity, and thus cannot guarantee the accuracy of the global model.

Figure 4: Objective Value vs Aggregator Capacity $L_{\text{max}}$

Furthermore, in Figure 5, we analyze the impact of the number of participating
end devices on the total sensed data that contributes towards the global
model. It can be seen that the total sensed data of the two algorithms are
similar when the number of participating devices is small. This is because in
this case, all feasible devices satisfying the delay constraint are
accommodated by the aggregator in the edge server. As the number of devices
increases, the greedy algorithm is able to accommodate a much larger amount of
data sensed by the participating devices and thus, has a much better global
model accuracy while the performance of the Best-SINR algorithm reaches an
approximate upper bound in terms of the amount of user data it can contribute
to the global model. This phenomenon can be attributed to the fact that the
greedy algorithm continues to track the devices with larger datasets while the
Best-SINR approach selects a certain number of devices in its vicinity
constrained by the aggregator capacity even when the total number of devices
increases. Overall, the greedy algorithm takes into account each device’s
dataset size and results in a more accurate update to the global model in each
training round, leading to more optimized FL.

Figure 5: Total sensed data (in bytes) used for aggregation vs Number of
devices $N$

##  IV Future Research Challenges

###  IV-A Optimizing Learning Delay

The training delay of the global model in FL will be a critical metric in
real-time learning applications. In a given network, there may be certain
devices that are constrained by their wireless channel conditions, while other
devices may have energy constraints, thus limiting their computational
capabilities. In this context, given a required accuracy of the global model,
the selection policy of end devices accounting for their energy constraints
will play an important role in minimizing the overall training delay.
Therefore, the above problem of balancing between global model accuracy and
increasing operational longevity of user devices remains an open challenge.

###  IV-B Participation and Privacy Considerations

Ensuring maximum end device participation in the shared global model training
remains a challenge when a majority of participants are supported on
potentially unreliable wireless channels. Additionally, battery-powered IoT
devices may also implement policies specific to distributed learning to
conserve energy, thereby not participating in certain rounds of training for a
given task. Furthermore, the hallmark feature of FL is the guarantee of local
user data privacy. However, adversaries may still be able to extract sensitive
information from model updates alone [11]. Although solutions based on
differential privacy [12] and secure aggregation [13] have been proposed,
securing local model updates may come at the expense of model accuracy.
Therefore, learner selection strategies in general need to strike a balance
between maximum user participation for higher training accuracy and respecting
the security concerns of end devices.

###  IV-C Convergence studies for Asynchronous FL

Asynchronous FL is an approach allowing participants to join the training
phase while it is in progress, as opposed to Synchronous FL that is prone to
the straggler effect [14]. Although Synchronous FL is the preferred approach
owing to better convergence guarantees [15], the asynchronous model is better
suited to real-world FL training scenarios with end devices being channel and
energy-constrained. Convergence bounds and generalization abilities of popular
algorithms such as distributed gradient descent need to be studied
theoretically to arrive at convergence guarantees for convex as well as non-
convex loss functions.

##  V Conclusion

This article presents a brief introduction to Multi-Access Edge Computing
(MEC), its motivation and how Federated Learning (FL) together with MEC can
play an important role in efficiently realizing learning and inference tasks
under extremely stringent latency constraints, that are will be one of the
critical constaints in the Beyond-$5$G vision. The conceptual foundations
behind MEC and FL are introduced, accompanied by a brief state-of-the-art
survey. Under the larger umbrella of FL, two inter-related optimization
problems focusing on minimizing communications latency in FL tasks and
maximizing FL training accuracy under wireless channel constraints and edge
server limitations are formulated, along with a discussion on simulation
results obtained via the introduced greedy algorithm. We also present a
relevant sampling of current challenges and future directions for edge
computing-assisted FL research for Beyond-$5$G networks.

## References

  * [1] Cisco Visual Networking Index, _Global mobile data traffic forecast update, 2016-2021_. Cisco white paper, 2017\.
  * [2] H. Song, J. Bai, Y. Yi, J. Wu, and L. Liu, “Artificial intelligence enabled internet of things: Network architecture and spectrum access,” _IEEE Computational Intelligence Magazine_ , vol. 15, no. 1, pp. 44–51, Feb 2020.
  * [3] R. Shafin, L. Liu, V. Chandrasekhar, H. Chen, J. Reed, and J. Zhang, “Artificial Intelligence-enabled cellular networks: A critical path to beyond-5G and 6G,” _IEEE Wireless Commun. Mag._ , 2020.
  * [4] Z. Zhou, L. Liu, S. Jere, J. Zhang, and Y. Yi, “RCNet: Incorporating structural information into deep RNN for MIMO-OFDM symbol detection with limited training,” _IEEE Transactions on Wireless Communications_ , 2020, manuscript submitted for publication.
  * [5] 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, Fourthquarter 2017.
  * [6] N. Fernando, S. W. Loke, and W. Rahayu, “Mobile cloud computing: A survey,” _Future Generation Computer Systems_ , vol. 29, no. 1, pp. 84 – 106, 2013, including Special section: AIRCC-NetCoM 2009 and Special section: Clouds and Service-Oriented Architectures. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0167739X12001318
  * [7] Q. Fan and N. Ansari, “Workload allocation in hierarchical cloudlet networks,” _IEEE Communications Letters_ , vol. 22, no. 4, pp. 820–823, April 2018.
  * [8] ——, “Towards workload balancing in fog computing empowered IoT,” _IEEE Transactions on Network Science and Engineering_ , DOI:10.1109/TNSE.2018.2852762, early access, 2018.
  * [9] 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_ , ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. Fort Lauderdale, FL, USA: PMLR, 20–22 Apr 2017, pp. 1273–1282. [Online]. Available: http://proceedings.mlr.press/v54/mcmahan17a.html
  * [10] _Radio Frequency (RF) requirements for LTE Pico Node B_ , 3GPP Std. TR 36.931, Rev. 13.0.0, 2016.
  * [11] G. Ateniese, L. V. Mancini, A. Spognardi, A. Villani, D. Vitali, and G. Felici, “Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers,” _Int. J. Secur. Netw._ , vol. 10, no. 3, pp. 137–150, Sep. 2015. [Online]. Available: http://dx.doi.org/10.1504/IJSN.2015.071829
  * [12] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’16. New York, NY, USA: ACM, 2016, pp. 308–318. [Online]. Available: http://doi.acm.org/10.1145/2976749.2978318
  * [13] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for federated learning on user-held data,” in _NIPS Workshop on Private Multi-Party Machine Learning_ , 2016.
  * [14] M. R. Sprague, A. Jalalirad, M. Scavuzzo, C. Capota, M. Neun, L. Do, and M. Kopp, “Asynchronous federated learning for geospatial applications,” in _ECML PKDD 2018 Workshops_ , A. Monreale, C. Alzate, M. Kamp, Y. Krishnamurthy, D. Paurat, M. Sayed-Mouchaweh, A. Bifet, J. Gama, and R. P. Ribeiro, Eds. Cham: Springer International Publishing, 2019, pp. 21–28.
  * [15] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. M. Kiddon, J. Konečný, S. Mazzocchi, B. McMahan, T. V. Overveldt, D. Petrou, D. Ramage, and J. Roselander, “Towards federated learning at scale: System design,” in _SysML 2019_ , 2019, to appear. [Online]. Available: https://arxiv.org/abs/1902.01046


# Quasi-local studies of the particle surfaces and their stability in general
spacetimes

Yong Song111e-mail address<EMAIL_ADDRESS>Chuanyu Zhang222e-mail address:
<EMAIL_ADDRESS>(corresponding author) College of Mathematics and
Physics
Chengdu University of Technology, Chengdu, Sichuan 610059, China

###### Abstract

In this paper, enlightened by the definition of the photon surface given by
Claudel, Virbhadra and Ellis, we give a quasi-local definition of the particle
surface. From this definition, one can study the evolution of the circular
orbits in general spacetime. Especially, we pointed out that this definition
can be used to get the spherical circular orbits in stationary spacetimes
which cannot be got by the definition of Claudel, Virbhadra and Ellis.
Further, we give a condition to exclude the particle surface in spacetime
without gravity. Simultaneously, we give a quasi-local definition of the
stability of the particle surface in general spacetime. From this definition,
one can get the evolution equation of the innermost stable circular orbit
(ISCO) in general spacetime. To verify the correctness of these definitions,
we studied the circular orbits in some special cases and the results are all
consistent with the previous results.

##  I Introduction

Black holes are an important prediction of general relativity. Confirming the
existence of black holes can further verify the correctness of general
relativity. In 2019, the Event Horizon Telescope (EHT) Collaborations
published the first image of the black hole at the center of the M87 galaxy
EventHorizonTelescope:2019dse; EventHorizonTelescope:2019ggy;
EventHorizonTelescope:2019jan; EventHorizonTelescope:2019pgp;
EventHorizonTelescope:2019ths; EventHorizonTelescope:2019uob. As shown in
FIG.1.

Figure 1: black hole image EventHorizonTelescope:2019dse: The black hole image
was taken in 2017 and published in 2019 after two years of data processing.

In this image, one can clearly see a shadowed region surrounded by a halo.
This shadow region is called black hole shadow, and the halo corresponds to
the black hole accretion disk. One can get a lot of information about the
black hole by studying black hole shadow and accretion disk.

Up to date, there are many studies on the black hole shadow Grenzebach:2016;
Cunha:2018acu; Virbhadra:2022ybp; Virbhadra:2022iiy and the accretion disk
Abramowicz:2011xu. The circular orbits of the spacetime are important for
black hole shadow and accretion disk. For example, in Schwarzschild spacetime,
on the one hand, the photon sphere, which is the location of the circular
photon orbits, is the boundary of the black hole shadow Synge:1966okc;
Virbhadra:1999nm. On the other hand, the timelike stable circular orbits
determine the position of the accretion disk and the ISCO is the boundary of
the accretion disk Abramowicz:2011xu. Here, we focus on the study of the
circular orbits in the spacetime. There are mainly two ways to study the
circular orbits. In the first method, one can solve the geodesic equations to
get the circular orbits. This method has a wide range of applications. Such
as, for null geodesics, this method can be used to study the photon sphere in
static spacetimes Hasse:2001by; Chakraborty:2011uj; Cardoso:2008bp, the photon
surface in dynamical spacetime Mishra:2019trb; Koga:2022dsu and the photon
region in stationary spacetimes Bardeen:1972fi; Teo:2003; Johannsen:2013vgc;
Igata:2019pgb; Cederbaum:2019vwv; for timelike geodesics, one can use this
method to study the circular orbits in static spacetimes Cornish:2003ig;
Vieira:2013jga; Boonserm:2019nqq; Berry:2020ntz and stationary spacetimes
Slany:2013ora; Stuchlik:2003dt; Teo:2020sey. However, there are some practical
problems in this traditional method which have been pointed out by
Cao:2019vlu: (i). To grantee the separability of the geodesic equations, the
systems which have been studied must have enough symmetries Grenzebach:2016.
For real black holes, this condition is hard to satisfy. (ii). This method
depends on the information at the infinity of the spacetime. This dependence
means that we have to know the metric of the full spacetime, especially the
future infinity of spacetime. This is impossible without additional
assumptions. These problems inspire people to study the circular orbits in a
different way. The second approach, which is called quasi-local study, has
drawn some attention these years. For null geodesic, the first quasi-local
definition of the photon surface is given by Claudel, Virbhadra and Ellis
Claudel:2000yi. They defined a photon surface in a general spacetime as an
umbilical timelike hypersurface. Based on this definition, they studied the
photon surfaces in general spherically symmetric spacetimes. However, there
are some obvious problems with this definition: (i). This definition is based
on the null geodesic, so, it can not deal with the situation of timelike
geodesic. (ii). The umbilical condition can not be used to study the photon
region of stationary axisymmetric spacetimes. Up to date, there are some
generalization studies of photon surface in stationary axisymmetric
spacetimes. Such as, Yoshino et al. generalized the photon surface to be a
loosely trapped surface Shiromizu:2017ego and (dynamically) transversely
trapping surface Yoshino:2017gqv; Yoshino:2019dty; Galtsov:2019bty; Kobialko
et al. generalized the photon surface to be a fundamental photon hypersurfaces
and fundamental photon regions Kobialko:2020vqf; Kobialko:2021aqg. (iii). This
definition can not exclude the photon surface in spacetime without gravity.
For example, it allows the existence of the photon surface in Minkowski
spacetime. This problem has been solved by Cao:2019vlu which based on the
geometry of a codimension-2 surface.

In this work, we want to give a generalized definition to over come the above
three problems in the definition of the photon surface. Enlightened by the
quasi-local definition of the photon sphere and photon surface Claudel:2000yi;
Cao:2019vlu, we generalized the photon surface to the particle surface. Unlike
the work studied the stability of the photon surface Koga:2019uqd;
Koga:2020akc, we give a quasi-local definition of the stability of the
particle surface in general spacetime. From this generalization, we studied
the circular orbits in general spherical symmetric spacetimes and axisymmetric
spacetimes. The results are all consistent with the previous results.

This paper is organized as follows: In section II, we will give the
definitions of a particle surface and the stability of the particle surface.
In section III, based on these definitions, we will study the circular orbits
in general static spherical symmetric spacetimes. In section IV, we will study
the evolutions of the circular orbits in general spherical symmetric
spacetimes. Especially, we will study the evolutions of the circular orbits in
Vaidya spacetime. In section V, we will use the spherical orbits of Kerr
spacetime and evolved spherical orbits of Kerr-Vaidya spacetime in the slow
rotation limit as examples to show the validity of the definition 1. Section
VI is devoted to the conclusion and discussion.

Convention of this paper: We choose the system of geometrized unit, i.e., set
$G=c=1$. Also, we set the mass of a massive point particle $m=1$ and use $M$
to denote the mass of a black hole. We use the symbol
$(\mathcal{M},\nabla_{a},g_{ab})$ to denote a manifold $\mathcal{M}$ with
metric $g_{ab}$ and covariant derivative operator $\nabla_{a}$, and
($g_{ab},\nabla_{a}$) satisfies the compatibility condition, i.e.,
$\nabla_{a}g_{bc}=0$. The abstract index formalism has been used to clarify
some formulas or calculations. The curvature $R_{abcd}$ of the spacetime is
defined by $R_{abcd}v^{d}=(\nabla_{a}\nabla_{b}-\nabla_{b}\nabla_{a})v_{c}\,$
for an arbitrary tangent vector field $v^{a}$ Wald:1984rg.

##  II The definition of a particle surface and the stability of the particle
surface

In this section, we will give the quasi-local definition of the particle
surfaces and their stability in general spacetime. At first, let us give a
brief review of the circular orbits in the Schwarzschild spacetime
Wald:1984rg. The metric of the Schwarzschild spacetime in
$\\{t,r,\theta,\phi\\}$ coordinates can be expressed as

$\displaystyle
ds^{2}=-\bigg{(}1-\frac{2M}{r}\bigg{)}dt^{2}+\bigg{(}1-\frac{2M}{r}\bigg{)}^{-1}dr^{2}+r^{2}(d\theta^{2}+\sin^{2}\theta
d\phi^{2})$ (1)

Due to the spherical symmetry of Schwarzschild spacetime, we can choose the
equatorial plane, i.e., $\theta=\pi/2$. The circular photon orbits, which is
usually called photon sphere or photon surface, is located at

$\displaystyle r=3M\;,$ (2)

The null geodesics on the photon surface have the property that any null
geodesic emitted in any tangent direction of the photon surface from any point
on the photon surface will continue to propagate on the photon surface
Claudel:2000yi.

However, the case of timelike circular orbits is different. The locations of
the timelike circular orbits are satisfies

$\displaystyle E=\frac{(r-2M)}{\sqrt{r(r-3M)}}\;,\quad
L=\sqrt{\frac{Mr^{2}}{r-3M}}\;,$ (3)

where $E$ is the conserved orbital energy and $L$ is the conserved orbital
angular momentum of the timelike geodesic. And the tangent vector of the
timelike circular orbits in the equatorial plane can be written as

$\displaystyle
k^{a}=\bigg{\\{}-\frac{E}{1-2M/r},0,0,\frac{L}{r^{2}}\bigg{\\}}$ (4)

The timelike circular orbits are located at the hypersurface that
$r=\mathrm{constant}$, which will be called particle surface in this work. On
each particle surface, the timelike geodesics with specified parameter have
the property that it emitted in at least one tangent direction of the particle
surface from any point on the particle surface will continue to propagate on
the particle surface.

Enlightened by the above discussion and the quasi-local definition of the
photon surface Claudel:2000yi; Cao:2019vlu, we give the following definitions:

###### Definition 1

Let $(S,D_{a},h_{ab})$ be a timelike hypersurface (or a subset of a timelike
hypersurface) of $(\mathcal{M},\nabla_{a},g_{ab})$. Let $k^{a}$ be the null or
unit timelike tangent vector of $\gamma$ which is an affine null or timelike
geodesic in $S$, i.e., it satisfies

$\displaystyle k^{a}D_{a}k^{b}=0\;.$ (5)

Let $v^{a}$ be a unit normal vector to $S$ and $K_{ab}$ be the second
fundamental form on $S$. If for $\forall p\in S$, there exists at least one
$\gamma\in S$ passing through $p$ and satisfies

$\displaystyle K_{ab}k^{a}k^{b}=0\;,$ (6)

where $k^{a}$ can be timelike or null, and

$\displaystyle 2v^{c}\nabla_{c}(K_{ab}k^{a}k^{b})\neq 0\;,$ (7)

where $k^{a}$ is a null vector. Then, $S$ is called a (partial) particle
surface.