#  A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal
Routing in Wireless Multihop Networks

Dimitrios Alanis, Panagiotis Botsinis, Zunaira Babar, Hung Viet Nguyen, Daryus
Chandra, Soon Xin Ng, and Lajos Hanzo The authors are with the School of
Electronics and Computer Science, University of Southampton, Southampton, SO17
1BJ, UK (email: {da1d16, pb1y14, zb2g10, hvn08r, dc2n14, sxn,
lh}@ecs.soton.ac.uk).The financial support of the EPSRC under the grant
EP/L018659/1, that of the European Research Council, Advanced Fellow Grant and
that of the Royal Society’s Wolfson Research Merit Award is gratefully
acknowledged. Additionally, the authors acknowledge the use of the IRIDIS High
Performance Computing Facility, and associated support services at the
University of Southampton, in the completion of this work. The research data
of this paper can be found at http://doi.org/10.5258/SOTON/D0402.

###### Abstract

Wireless Multihop Networks (WMHNs) have to strike a trade-off among diverse
and often conflicting Quality-of-Service (QoS) requirements. The resultant
solutions may be included by the Pareto Front under the concept of Pareto
Optimality. However, the problem of finding all the Pareto-optimal routes in
WMHNs is classified as NP-hard, since the number of legitimate routes
increases exponentially, as the nodes proliferate. Quantum Computing offers an
attractive framework of rendering the Pareto-optimal routing problem
tractable. In this context, a pair of quantum-assisted algorithms have been
proposed, namely the Non-Dominated Quantum Optimization (NDQO) and the Non-
Dominated Quantum Iterative Optimization (NDQIO). However, their complexity is
proportional to $\sqrt{N}$, where $N$ corresponds to the total number of
legitimate routes, thus still failing to find the solutions in “polynomial
time”. As a remedy, we devise a dynamic programming framework and propose the
so-called Evolutionary Quantum Pareto Optimization (EQPO) algorithm. We
analytically characterize the complexity imposed by the EQPO algorithm and
demonstrate that it succeeds in solving the Pareto-optimal routing problem in
polynomial time. Finally, we demonstrate by simulations that the EQPO
algorithm achieves a complexity reduction, which is at least an order of
magnitude, when compared to its predecessors, albeit at the cost of a modest
heuristic accuracy reduction.

###### Index Terms:

Quantum Computing, NDQIO, NDQO, Dynamic Programming, Pareto Optimality,
Routing.

## List of Acronyms

BBHT-QSA |  Boyer-Brassard-Høyer-Tapp Quantum Search Algorithm
---|---
BF |  Brute Force
BER |  Bit Error Ratio
CDP |  Classical Dynamic Programming
CF(E) |  Cost Function (Evaluation)
DHA |  Durr-Høyer Algorithm
DN |  Destination Node
EQPO |  Evolutionary Quantum Pareto Optimization
HP |  Hardware Parallelism
MODQO |  Multi-Objective Decomposition Quantum Optimization

MO-ACO |  Multi-Objective Ant Colony Optimization
---|---
NDQO |  Non-Dominated Quantum Optimization
(P-)NDQIO |  (Preinitialized) Non-Dominated Quantum Iterative Optimization
NSGA-II |  Non-dominated Sorting Genetic Algorithm II
OF |  Objective Function
OPF-SR |  Optimal Pareto Front Self-Repair
(O)PF |  (Optimal) Pareto Front
QoS |  Quality-of-Service
QP |  Quantum Parallelism
RN |  Relay Node
SN |  Source Node
UV |  Utility Vector
UF |  Utility Function
WMHN |  Wireless MultiHop Network

##  I Introduction

The concept of _Wireless Multihop Networks_ (WMHN) [1] enables the
communication of remote nodes by forwarding the transmitted packets through a
cloud of mobile relays. Naturally, the specific choice of the relays plays a
significant role in the performance of WMHNs [2], thus bringing their routing
optimization in the limelight. Explicitly, optimal routing relies on a fragile
balance of diverse and often conflicting _Quality-of-Service_ (QoS)
requirements [3], such as the route’s overall _Bit-Error-Ratio_ (BER) or
_Packet Loss Ratio_ (PLR), its total power consumption, its end-to-end delay,
the route’s achievable rate, the entire system’s sum-rate and its “lifetime”
[4].

For the sake of taking into account multiple QoS requirements, several studies
consider single-component _Objective Functions_ (OF) as their optimization
objectives. In this context, the metric of Network Lifetime (NL) [5, 4] has
been utilized, which involves the routes’ power consumption in conjunction
with the nodes’ battery levels. Additionally, the so-called _Network Utility_
(NU) [6] also constitutes a meritorious single-component optimization OF.
Apart from the aforementioned QoS requirements, NU also takes into account the
routes’ achievable rate [7]. In conjunction with the construction of aggregate
functions, the authors of [8, 9] also incorporate QoS as constraints, thus
providing a more holistic view of the routing problem. In this context,
Banirazi _et al._ [9] optimized an aggregate function of the Dirichlet routing
cost as well as the average network delay at specific operating points that
maximize the network throughput.

The beneficial properties of _dynamic programming_ [10] have been exploited
for the sake of identifying the optimal routes, while relying on single-
component aggregate functions. In this context, Dijkstra’s algorithm [11, 12,
13] has been employed, since it is capable of approaching the optimal routes
at the cost of imposing a complexity on the order of $O(E^{3})$, where $E$
corresponds to the number of edges in the network’s graph. Additionally, the
appropriately modified Viterbi decoding algorithm [14, 15] has also been
utilized for solving single-component routing optimization problems, where the
route exploration process can be viewed as a _trellis graph_ and thus the
routing problem is transformed into a decoding problem. Explicitly, this
transformation is reminiscent of the famous _Bellman-Ford_ algorithm [16].

The aforementioned approaches fail to identify the potential discrepancies
among the QoS requirements, but they can be unified by the concept of _Pareto
Optimality_ [17]. However, the search-space of multi-component optimization is
inevitably expanded due to combining the single-component OFs. Furthermore,
the complexity is proportional to $O(N^{2})$, where $N$ corresponds to the
total number of eligible routes. Additionally, since $N$ increases
exponentially as the relay nodes proliferate [18], the Pareto-optimal routing
problem is classified as _Non-deterministic Polynomial hard_ (NP-hard) [19].
This escalating complexity can be partially mitigated by identifying a single
Pareto-optimal solution. For instance, Gurakan _et al._ [20] conceived an
optimal iterative routing scheme for identifying a single Pareto-optimal
solution in terms of the sum rate and the energy consumption of wireless
energy-transfer-enabled networks. However, in our application we are primarily
interested in identifying the entire set of Pareto-optimal solution, since it
provides fruitful insights into the underlying trade-offs [17]. In this
context, multi-objective evolutionary algorithms [18, 21, 22] have been
employed for addressing the escalating complexity. In particular, Yetgin _et
al._ [18] used both the _Non-dominated Sorting Genetic Algorithm II_ (NSGA-II)
and the _Multi-Objective Differential Evolution Algorithm_ (MODE) for
optimizing the transmission routes in terms of their end-to-end delay and
power dissipation. While considering a similar context, Camelo _et al._ [21]
invoked the NSGA-II for optimizing the same QoS requirements for both the
ubiquitous _Voice over Internet Protocol_ (VoIP) and for file transfer.
Additionally, the so-called _Multi-Objective Ant Colony Optimization_ (MO-ACO)
algorithm [23] has been employed in [19] for the sake of addressing the multi-
objective routing problem in WMHNs.

Quantum computing provides a powerful framework [24, 25, 26] for the sake of
rendering Pareto-optimal routing problems tractable by exploiting the so-
called _Quantum Parallelism_ (QP) [27]. Explicitly, in [28] _Quantum
Annealing_ [29], has been invoked for the sake of optimizing the activation of
the wireless links in wireless networks, while maintaining the maximum
throughput and minimum interference as well as providing a substantial
complexity reduction w.r.t. its classical counterpart, namely simulated
annealing. In terms of Pareto optimal routing using _universal quantum
computing_ [27], the so-called _Non-Dominated Quantum Optimization_ (NDQO)
algorithm proposed in [19] succeeded in identifying the entire set of Pareto-
optimal routes at the expense of a complexity, which is on the order of
$O(N\sqrt{N})$, relying on QP. As an improvement, the so-called _Non-Dominated
Quantum Iterative Optimization_ (NDQIO) algorithm was proposed in [30].
Explicitly, the NDQIO algorithm is also capable of identifying the entire set
of Pareto-optimal routes, while imposing a parallel complexity and a
sequential complexity defined111We define the _parallel complexity_ as the
complexity imposed while taking into account the degree of parallelism. By
contrast, the sequential complexity does not consider any kind of parallelism.
In [30], they are referred to as _normalized execution time_ and _normalized
power consumption_ , respectively. in [30], which is on the order of
$O(N_{\text{OPF}}\sqrt{N})$ and $O(N^{2}_{\text{OPF}}\sqrt{N})$, respectively,
by relying on the beneficial synergy between QP and _Hardware Parallelism_
(HP). Note that $N_{\text{OPF}}$ corresponds to the number of Pareto-optimal
routes.

Despite the substantial complexity reduction offered both by the NDQO and the
NDQIO algorithms, the multi-objective problem still remains intractable, when
the network comprises an excessively high number of nodes due to the
escalating complexity. Explicitly, Zalka [31] has demonstrated that the
complexity order of $O(\sqrt{N})$ is the minimum possible, as long as the
database values are uncorrelated. By contrast, when the formation of the
Pareto-optimal route-combinations becomes correlated owing to socially-aware
networking [32], a further complexity reduction can be achieved. Based on this
specific observation, we will design a novel algorithm, namely the
_Evolutionary Quantum Pareto Optimization_ (EQPO), in order to exploit the
correlations exhibited by the individual Pareto-optimal routes by
appropriately constructing trellis graphs that guide the search process in the
same fashion as in Viterbi decoding. Furthermore, we will also exploit the
synergies between QP and HP for the sake of achieving an additional complexity
reduction by considering as low a fraction of the database entries as
possible, while still guaranteeing a near-full-search-based performance.

Our contributions are summarized as follows: __

  1. _1)_

_In Section_ III, we develop a novel multi-objective dynamic programming
framework for generating potentially Pareto-optimal routes relying on the
correlations of the specific links constituting the Pareto-optimal routes,
hence substantially reducing the total number of routes considered.
Explicitly, this framework is a multi-objective extension of the popular
single-objective Bellman-Ford algorithm.

  2. _2)_

_In Section_ IV, we propose a novel quantum-assisted algorithm, namely the
_Evolutionary Quantum Pareto Optimization_ algorithm, which jointly exploits
our novel dynamic programming framework as well as the synergies between the
QP and the HP for the sake of solving the multi-objective routing problem of
WMHNs.

  3. _3)_

_In Section_ V, we also characterize the performance versus complexity of the
EQPO algorithm and demonstrate that it achieves both a parallel and a
sequential complexity reduction of at least an order of magnitude for a 9-node
WMHN, when compared to that of the NDQIO algorithm.

The rest of this paper is organized as follows. In Section II, we will briefly
discuss the specifics of the network model considered in our case study. In
Section III, we will present a dynamic programming framework, which is optimal
in terms of its heuristic accuracy. In Section IV, we will relax the optimal
framework of Section II for the sake of striking a better accuracy versus
complexity trade-off with the aid of our EQPO algorithm. Subsequently, in
Section V-A we will analytically characterize the EQPO algorithm’s complexity
and in Section V-B we will evaluate its performance.

##  II Network Specifications

In the context of this treatise, the model of the networks considered both in
[19] and in [30] has been adopted. To elaborate further, the WMHN considered
is a fully connected network and it consists of a single _Source Node_ (SN), a
single _Destination Node_ (DN) and a cloud of _Relay Nodes_ (RN). The SN and
the DN are located in the opposite corners of a (100$\times$100) m2 square-
block area, which is the WMHN coverage area considered. By contrast, the RNs
are considered to be roaming within the coverage area having random locations,
which obey the uniform distribution within the WMHN coverage area. A WMHN
topology is exemplified in Fig. 1 for a WMNH consisting of 5 nodes in total.
Additionally, a cluster-head equipped with a quantum computer, which is
responsible for collecting all the required WMHN information, such as the
nodes’ geolocations and their interference levels, is considered to be present
at the DN side. Therefore, we should point out that this treatise is focused
on a centralized protocol.

Figure 1: Exemplified WMHN topology associated with 5 nodes. The presence of a
cluster-head in possession of a quantum computer is considered at the DN side
as in [19] and in [30]. The interference levels experienced by each node are
presented in the legend.

Based on the network information gathered, the WMHN cluster-head has to
identify the optimal routes emerging from the SN to the DN based on certain
_Utility Functions_ (UF). Similar to [19] and [30], we have jointly taken into
account the route’s overall delay, its overall power consumption and its
overall _Bit Error Ratio_ (BER). Before delving into the UFs, let us define a
legitimate route of our WMHN consisting of $N_{\text{nodes}}$ nodes, as
$x_{r}=[\text{SN},\dots,\text{DN}]$, which contains each RN only once for the
sake of limiting the total number $N$ of legitimate routes, while at the same
time avoiding routes associated with excessive power consumption and delay.
Note that we have associated the SN and the DN with the node indices 1 and
$N_{\text{nodes}}$, respectively, in the context of this treatise.
Additionally, these legitimate routes are mapped to a specific index $x$ under
lexicographic ordering using _Lehmer Encoding_ 222Lehmer Encoding maps a
specific permutation to an index in the _factoradic basis_ [33]. [33]. The
route’s overall delay $D(x)$ is considered as one of our UFs, which is
quantified in terms of the number of hops established by the route. This is
formally formulated as follows:

$D(x)=\left|x_{r}\right|-1,$ (1)

where the operator $\left|\cdot\right|$ corresponds to the number of nodes
along the route $x_{r}$ including the SN and DN. Moving on to the $x$-th
route’s overall power consumption $P(x)$, it is proportional to the sum of
path-losses incurred by each of the individual links constituting the route.
Explicitly, the path-loss $L_{\text{dB}}(i,j)$ quantified in dB for a single
link between the $i$-th and the $j$-th nodes is equal to [30]:

$L_{\text{dB}}(i,j)=P_{Tx,ij}-P_{Rx,ij}=10\alpha\log_{10}\left(\frac{4\pi
d_{i,j}}{\lambda_{c}}\right),$ (2)

where $\alpha$ corresponds to the path-loss exponent, $d_{i,j}$ is the
distance between the two nodes and $\lambda_{c}$ denotes the carrier’s
wavelength. In our case-study we have set $\alpha=3$ and $\lambda_{c}\simeq
0.125$ m corresponding to a frequency of $f_{c}=2.4$ GHz. Consequently, the
second UF is formulated as follows:

$L(x)=\sum\limits_{i=1}^{\left|x_{r}\right|-1}10^{L_{\text{dB}}(x_{r}^{(i)},x_{r}^{(i+1)})/10}.$
(3)

Moving on to the final UF, namely the BER, let us first elaborate on the
interference levels experienced by the nodes. In our specific scenario, there
is only a single pair of source and destination nodes, resulting in a single
route being active. Additionally, we have assumed that the WMHN has a
sufficient number of orthogonal spreading codes and sub-carriers for the sake
of efficiently separating the routes as in [32]. In this context, there is no
interference stemming from the WMHN itself; however, we have assumed that a
sufficiently high number of users access the channel, hence the resultant
interference can be treated as _Additive White Gaussian Noise_ (AWGN), owing
to the _Central Limit Theorem_ (CLT) [34]. Therefore, the interference is
modeled by a random Gaussian process, with its mean set to -90 dBm and its
standard deviation set to 10 dB, while the transmission power is set to
$P_{Tx}=20$ dBm. Additionally, the nodes transmit their messages using the
uncoded QPSK scheme [35] over uncorrelated Rayleigh fading channels and
utilize _Decode-and-Forward_ relaying [36] for forwarding the respective
messages. Based on these assumptions, we can readily use the closed-form BER
performance of the adopted scheme versus the received _Signal-to-Noise Ratio_
(SNR), while the overall route’s BER $P_{e}(x)$ can be calculated using the
following recursive formula [19]:

$P_{e,tot}=P_{e,1}+P_{e,2}-2P_{e,1}P_{e,2},$ (4)

which corresponds to the output BER $P_{e,tot}$ of a two-stage _Binary
Symmetric Channel_ (BSC) [19], where $P_{e,1}$ and $P_{e,2}$ represent the BER
associated with the first and the second stage, respectively.

Having described the UFs considered, let us now proceed by defining our
optimization problem. Explicitly, we will jointly consider the UFs in the form
of a _Utility Vector_ (UV) $\mathbf{f}(x)$, which is defined as follows:

$\mathbf{f}(x)=\left[P_{e}(x),L(x),D(x)\right],$ (5)

where $D(x)$ and $L(x)$ correspond to the $x$-th route’s delay and power
consumption defined in Eqs. (1) and (3), while $P_{e}(x)$ denotes the $x$-th
route’s end-to-end BER, which is recursively evaluated using Eq. (4).
Explicitly, we opt for jointly minimizing the entire set of UFs considered by
the UV of Eq. (5). Therefore, for the evaluation of the fitness of the UVs we
will utilize the concept of _Pareto Optimality_ 333The readers should refer to
[32] for a more detailed tutorial on Pareto optimality. [17], which is
encapsulated by Definitions 1 and 2.

######  Definition 1.

Pareto Dominance [17]: A particular route $x_{i}$ associated with the UV
$\mathbf{f}(x_{i})=[f_{1}(x_{i}),\dots,$ $f_{K}(x_{i})]$, where $K$ is the
number of the UFs considered, is said to strongly dominate another route
$x_{j}$ associated with the UV
$\mathbf{f}(x_{j})=[f_{1}(x_{j}),\dots,f_{K}(x_{j})]$, denoted by
$\mathbf{f}(x_{i})\succ\mathbf{f}(x_{j})$, iff we have
$f_{k}(x_{i})<f_{k}(x_{j})$, $\forall{k}\in\\{1,\dots,K\\}$. Equivalently, the
route $x_{i}$ is said to weakly dominate another route $x_{j}$, denoted by
$\mathbf{f}(x_{i})\succeq\mathbf{f}(x_{j})$, iff we have $f_{k}(x_{i})\leq
f_{k}(x_{j})$, $\forall{k}\in\\{1,\dots,K\\}$ and $\exists
k^{\prime}\in\\{1,\dots,K\\}$, so that we have
$f_{k^{\prime}}(x_{i})<f_{k^{\prime}}(x_{j})$.

######  Definition 2.

Pareto Optimality [17]: A particular route $x_{i}$ associated with the UV
$\mathbf{f}(x_{1})$ is Pareto-optimal, iff there is no route that dominates
$x_{i}$, i.e. we have $\nexists{x_{j}}$ so that
$\mathbf{f}(x_{j})\succ\mathbf{f}(x_{i})$ is satisfied. Equivalently, the
route $x_{i}$ is strongly Pareto-optimal iff there is no route that weakly
dominates $x_{i}$, i.e. we have $\nexists{x_{j}}$, so that
$\mathbf{f}(x_{i})\succeq\mathbf{f}(x_{j})$ is satisfied.

Explicitly, Definition 1 provides us with the criterion for evaluating the
fitness of a specific route with respect to another reference route, while
Definition 2 outlines the condition of the specific route’s optimality. Based
on the number of routes dominating a specific route, it is possible to group
the routes into the so-called _Pareto Fronts_ (PF). Explicitly, the PF
comprises the Pareto-optimal routes, which are dominated by no other routes
according to Definition 2, which is often referred to as the _Optimal Pareto
Front_ (OPF).

In our application, our aim is to identify the entire set of weakly Pareto-
optimal routes for the sake of gaining insight into the routing trade-offs
associated with the UFs considered. Naturally, for the sake of identifying a
specific route as Pareto-optimal we have to perform precisely $(N-1)$ Pareto-
dominance comparisons, where $N$ corresponds to the total number of legitimate
routes. Therefore, the complexity imposed by the exhaustive search aiming for
identifying the entire set of routes belonging to the OPF is on the order of
$O(N^{2})$. Explicitly, the total number $N$ of legitimate routes increases
exponentially as the number $N_{\text{nodes}}$ of nodes increases [19], hence
rendering the multi-objective routing problem as NP-hard. Thus sophisticated
methods are required for finding all of the solutions.

Let us now proceed by elaborating on our novel dynamic framework designed for
efficiently exploring the search space.

##  III Mutli-Objective Routing Dynamic Programming Framework

Before delving into the analysis of our multi-objective dynamic programming
framework, which is specifically tailored for our routing problem, we will
express each of the UFs considered in the UV of Eq. (5) as a weighted sum of
the specific UFs associated with the individual links comprised by a
particular route. Explicitly, the power consumption has already been expressed
in this form based on Eq. (3). As for the delay, which we have defined as the
number of hops, it may be redefined as follows:

$D(x)=\sum\limits_{i=1}^{\left|x_{r}\right|-1}\left(1-\delta_{x_{r}^{(i)},x_{r}^{(i+1)}}\right),$
(6)

where $\delta_{i,j}$ corresponds to the _Kronecker delta_ function [37], while
$x_{r}$ and $x$ represent the route and its associated index, respectively. As
for the route’s overall BER, the recursive formula of Eq. (4) may be
approximated as follows:

$P_{e}(x)=\sum\limits_{i=1}^{\left|x_{r}\right|-1}P_{e,x_{r}^{(i)},x_{r}^{(i+1)}}-\epsilon(x)\thickapprox\sum\limits_{i=1}^{\left|x_{r}\right|-1}P_{e,x_{r}^{(i)},x_{r}^{(i+1)}},$
(7)

where $P_{e,k,l}$ represents the BER of the specific link established between
the $k$-th and the $l$-th nodes, while $\epsilon(x)$ is the approximation
error, which is on the order of:

$\epsilon(x)=O\left(\sum\limits_{i=1}^{\left|x_{r}\right|-1}\sum\limits_{\scriptsize\begin{array}[]{c}j=1\\\
j\neq
i\end{array}}^{\left|x_{r}\right|-1}P_{e,x_{r}^{(j)},x_{r}^{(i+1)}}P_{e,x_{r}^{(j)},x_{r}^{(j+1)}}\right).$
(8)

Since the sum of the products of all the links’ BER will be several orders of
magnitude lower than their sum, the approximation error of Eq. (7) may be
deemed to be negligible.

Having expressed the UFs considered as a weighted sum of the UFs associated
with their links, we may now proceed by exploiting this specific property for
the sake of achieving a further complexity reduction. In fact, it is possible
to transform our composite multi-objective routing problem into a series of
smaller subproblems, thus arriving at a dynamic programming structure. This
transformation is performed with the aid of Definition 3 in conjunction with
Proposition 1.

######  Definition 3.

A specific route $x=\\{SN{\rightarrow}\bar{R}_{i}{\rightarrow}DN\\}$ is said
to generate another route $x_{g}^{(j)}$ by inserting the single RN $R_{j}$
node between the previous RN and the DN. Explicitly, the resultant route
$x_{g}^{(j)}$ is
$x^{(j)}_{g}=\\{SN{\rightarrow}\bar{R}_{i}{\rightarrow}R_{j}{\rightarrow}DN\\}$,
$\forall j\in\\{1,\dots,N_{\text{nodes}}-2\\}$.

######  Proposition 1.

Let us consider a specific route
$x=\\{SN{\rightarrow}\bar{R}_{i}{\rightarrow}DN\\}$ associated with the UV
$\mathbf{f}(x)=[f_{1}(x),\dots,f_{K}(x)]$ and its sub-route
$x^{\prime}=\\{SN{\rightarrow}\bar{R}_{i}\\}$ associated with the UV
$\mathbf{f}(x^{\prime})=[f_{1}(x^{\prime}),\dots,f_{K}(x^{\prime})]$. Let us
assume furthermore that each component $f_{k}(x)$ of the UV associated with
the route $x$ has a positive value and that it can be expressed as a sum of
the respective UFs of its individual links $x_{i,i+1}$, i.e. we have:

$f_{k}(x)=\sum\limits^{\left|x\right|-1}_{i=1}f_{k}(x_{i,i+1}),$ (9)

with ${f}_{k}(x_{i,i+1})>0,\leavevmode\nobreak\ \forall\leavevmode\nobreak\
k,i,x:\leavevmode\nobreak\ k\in\\{1,...,K\\},\leavevmode\nobreak\
i\in\\{1,...,|x|-1\\},\leavevmode\nobreak\ x\in S$, where $K$ and $S$ are the
number of optimization objectives and the set of legitimate routes,
respectively. The route $x$ cannot generate any Pareto-optimal routes using
the rule of Definition 3 if there is a route
$x_{d}=\\{SN{\rightarrow}\bar{R}_{j}{\rightarrow}DN\\}$ from the SN to the DN
associated with $\bar{R}_{j}\neq\bar{R}_{i}$ that weakly dominates the sub-
route $x^{\prime}$, i.e. if we have $\exists x_{d}\in
S:\mathbf{f}(x_{d})\succeq\mathbf{f}(x^{\prime})$. The respective proof is
presented in Appendix A.

Explicitly, Proposition 1 guarantees that a specific route
$x=\\{SN{\rightarrow}\bar{R}_{i}{\rightarrow}DN\\}$ comprised by the sub-route
$x^{\prime}=\\{SN{\rightarrow}\bar{R}_{i}\\}$ cannot generate Pareto-optimal
routes by adding an intermediate RN to $x$ between its last RN and the DN, if
the sub-route $x^{\prime}$ is weakly dominated by any of the legitimate
routes. Explicitly, should its sub-route $x^{\prime}$ be sub-optimal, the
respective route $x$ will be sub-optimal as well, since we have $\exists
x_{d}\in S:\mathbf{f}(x_{d})\succeq\mathbf{f}(x^{\prime})\succ\mathbf{f}(x)$,
based on Proposition 1. Note that the opposite of this statement does not
apply, since there exist sub-optimal routes, whose sub-routes are indeed
Pareto-optimal.

Figure 2: Irregular trellis graph designed for guided search-space exploration for the 5-node WMHN of Fig. 1 using the optimal dynamic programming framework, encapsulated by Definition 3 and Proposition 1. Note that the UVs of each route are presented in Table I. Table I: Utility Vectors of the legitimate routes and of their respective sub-routes for the 5-node WMHN topology of Fig. 1. Route $x$ | Route UV | Sub-route UV | Optimal Route | Optimal Sub-route
---|---|---|---|---
$\\{1\leavevmode\nobreak\ 5\\}$ | $[4.52\leavevmode\nobreak\ 10^{-4},74.15,1]$ | $[\infty,\infty,\infty]$ | ✓ | ✓
$\\{1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 5\\}$ | $[2.52\leavevmode\nobreak\ 10^{-4},73.10,2]$ | $[2.52\leavevmode\nobreak\ 10^{-4},73.10,1]$ | ✓ | ✓
$\\{1\leavevmode\nobreak\ 3\leavevmode\nobreak\ 5\\}$ | $[2.35\leavevmode\nobreak\ 10^{-4},70.89,2]$ | $[3.13\leavevmode\nobreak\ 10^{-5},57.30,1]$ | ✓ | ✓
$\\{1\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\\}$ | $[1.43\leavevmode\nobreak\ 10^{-2},71.76,2]$ | $[1.41\leavevmode\nobreak\ 10^{-2},67.50,1]$ | ✓ | ✓
$\\{1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 5\\}$ | $[9.49\leavevmode\nobreak\ 10^{-4},76.09,3]$ | $[7.45\leavevmode\nobreak\ 10^{-4},74.61,2]$ |  |
$\\{1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\\}$ | $[1.91\leavevmode\nobreak\ 10^{-2},75.72,3]$ | $[1.89\leavevmode\nobreak\ 10^{-2},74.46,2]$ |  |
$\\{1\leavevmode\nobreak\ 3\leavevmode\nobreak\ 2\leavevmode\nobreak\ 5\\}$ | $[1.36\leavevmode\nobreak\ 10^{-4},69.55,3]$ | $[1.36\leavevmode\nobreak\ 10^{-4},69.54,2]$ | ✓ | ✓
$\\{1\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\\}$ | $[1.29\leavevmode\nobreak\ 10^{-2},71.74,3]$ | $[1.28\leavevmode\nobreak\ 10^{-2},67.46,2]$ |  | ✓
$\\{1\leavevmode\nobreak\ 4\leavevmode\nobreak\ 2\leavevmode\nobreak\ 5\\}$ | $[1.42\leavevmode\nobreak\ 10^{-2},71.19,3]$ | $[1.42\leavevmode\nobreak\ 10^{-2},71.19,2]$ |  | ✓
$\\{1\leavevmode\nobreak\ 4\leavevmode\nobreak\ 3\leavevmode\nobreak\ 5\\}$ | $[1.46\leavevmode\nobreak\ 10^{-2},73.50,3]$ | $[1.44\leavevmode\nobreak\ 10^{-2},70.27,2]$ |  | ✓
$\\{1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\\}$ | $[1.36\leavevmode\nobreak\ 10^{-2},76.36,4]$ | $[1.34\leavevmode\nobreak\ 10^{-2},75.30,3]$ |  |
$\\{1\leavevmode\nobreak\ 2\leavevmode\nobreak\ 4\leavevmode\nobreak\ 3\leavevmode\nobreak\ 5\\}$ | $[1.94\leavevmode\nobreak\ 10^{-2},76.50,4]$ | $[1.92\leavevmode\nobreak\ 10^{-2},75.18,3]$ |  |
$\\{1\leavevmode\nobreak\ 3\leavevmode\nobreak\ 2\leavevmode\nobreak\ 4\leavevmode\nobreak\ 5\\}$ | $[1.90\leavevmode\nobreak\ 10^{-2},74.13,4]$ | $[1.88\leavevmode\nobreak\ 10^{-2},72.18,3]$ |  |
$\\{1\leavevmode\nobreak\ 3\leavevmode\nobreak\ 4\leavevmode\nobreak\ 2\leavevmode\nobreak\ 5\\}$ | $[1.28\leavevmode\nobreak\ 10^{-2},71.18,4]$ | $[1.28\leavevmode\nobreak\ 10^{-2},71.17,3]$ |  |
$\\{1\leavevmode\nobreak\ 4\leavevmode\nobreak\ 2\leavevmode\nobreak\ 3\leavevmode\nobreak\ 5\\}$ | $[1.49\leavevmode\nobreak\ 10^{-2},75.23,4]$ | $[1.47\leavevmode\nobreak\ 10^{-2},73.35,3]$ |  |
$\\{1\leavevmode\nobreak\ 4\leavevmode\nobreak\ 3\leavevmode\nobreak\ 2\leavevmode\nobreak\ 5\\}$ | $[1.45\leavevmode\nobreak\ 10^{-2},72.82,4]$ | $[1.45\leavevmode\nobreak\ 10^{-2},72.81,3]$ |  |

This specific property can be exploited for the sake of reducing the search-
space size required for identifying the entire OPF. To elaborate further, we
can devise an _irregular trellis graph_ [38] for the sake of guiding the
search space exploration, as portrayed in Fig. 2 for the 5-node WMHN of Fig.
1. Note however that this specific trellis graph is different from those used
for channel coding in [38], since in the latter we only have as many
legitimate paths as many legitimate symbols. By contrast, here all transitions
represent legitimate routes in our scenario. Additionally, we rely on
Definition 3 for the sake of determining the possible trellis-node
transitions. For instance, observe in Fig. 2 that a trellis-path emerging from
the trellis-node associated with the generator route $\\{1\rightarrow
2\rightarrow 5\\}$ is only capable of visiting the nodes associated with the
routes $\\{1\rightarrow 2\rightarrow 3\rightarrow 5\\}$ and $\\{1\rightarrow
2\rightarrow 4\rightarrow 5\\}$, since a single RN is inserted before the DN
into the generator route based on Definition 3. Moving on to the next trellis
stages, during the $i$-th trellis stage the following three steps are carried
out:

####  III-1 Surviving Routes

The set $S^{\text{gen}}_{(i)}$ of generated routes are constructed based on
the set $S^{\text{surv}}_{(i-1)}$ of surviving routes of the previous stage
and relying on Definition 3.

####  III-2 Pareto-Optimal Routes

The set $S^{\text{OPF}}_{(i)}$ of Pareto-optimal routes is identified based on
the following optimization problem:

$\begin{array}[]{rl}S^{\text{OPF}}_{(i)}=&\mathop{\text{argmin}}\limits_{x\in{S^{\text{gen}}_{(i)}\cup
S^{\text{OPF}}_{(i-1)}}}\\{\mathbf{f}(x)\\},\\\
{}\hfil&s.t.\leavevmode\nobreak\ \nexists j\in{S^{\text{gen}}_{(i)}\cup
S^{\text{OPF}}_{(i-1)}}:\mathbf{f}(j)\succ\mathbf{f}(x).\end{array}$ (10)

Note that the optimization problem of Eq. (10) considers the joint search
space constituted by the all the routes $S^{\text{gen}}_{(i)}$ of the $i$-th
trellis stage as well as by the Pareto-optimal routes $S^{\text{OPF}}_{(i-1)}$
of the previous stage. Using recursion, we can readily observe that the
Pareto-optimal routes $S^{\text{OPF}}_{(i-1)}$ of the previous stage contain
the Pareto-optimal routes across all stages up to the $(i-1)$-st stage. This
property is beneficial for our dynamic programming framework, since it
eliminates the need for backwards propagation, thus only requiring the
employment of a feed-forward method for the identification of the entire OPF.

####  III-3 Surviving Routes

The set $S^{\text{surv}}_{(i)}$ of surviving routes is identified based on the
following optimization problem:

$\begin{array}[]{rl}S^{\text{surv}}_{(i)}=&\mathop{\text{argmin}}\limits_{x\in{S^{\text{gen}}_{(i)}}}\\{\mathbf{f}(x)\\},\\\
{}\hfil&s.t.\leavevmode\nobreak\ \nexists j\in{S^{\text{gen}}_{(i)}\cup
S^{\text{OPF}}_{(i-1)}}:\mathbf{f}(j)\succeq\mathbf{f}(x^{\prime}).\end{array}$
(11)

where $x^{\prime}$ corresponds to the particular sub-route of $x$, having all
the links of $x$, except for the last hop, as detailed in Proposition 1.

The optimization process proceeds to the next trellis stage as long as either
there exist surviving routes, i.e. we have
$S^{\text{surv}}_{(i)}\neq\varnothing$, or if the maximum affordable number of
trellis stages - which is equal to the maximum number of hops of the
legitimate routes - has not been exhausted. Otherwise, the optimization
process terminates by exporting the hitherto identified OPF.

Let us now proceed by elaborating on the route exploration process using the
5-node WMHN example of Fig 1. Its respective trellis is portrayed in Fig 2,
while the routes’ and their respective sub-route’s UVs are shown in Table I.
Initially, the optimization process considers the set $S^{\text{gen}}_{(1)}$
of routes, which is constituted by all the legitimate routes having a single
and two hops, namely the routes $\\{1\rightarrow 5\\}$, $\\{1\rightarrow
2\rightarrow 5\\}$, $\\{1\rightarrow 3\rightarrow 5\\}$ and $\\{1\rightarrow
4\rightarrow 5\\}$, as portrayed in the $1^{st}$ trellis stage of Fig. 2.
Based on Table I, all the routes considered are Pareto-optimal and thus the
respective set is equal to $S^{\text{OPF}}_{(1)}=S^{\text{gen}}_{(1)}$.
Subsequently, the set of surviving nodes is constructed. Explicitly, the
direct route is not considered in this case, since its inclusion leads to the
generation of routes, which have already been processed. Observe in Table I
that all the routes constituted by 2 hops have Pareto optimal sub-routes and
hence the set of surviving routes becomes
$S^{\text{surv}}_{(1)}=\left[\\{1\rightarrow 2\rightarrow 5\\},\\{1\rightarrow
3\rightarrow 5\\},\\{1\rightarrow 4\rightarrow 5\\}\right]$.

After the identification of the set of surviving routes
$S^{\text{surv}}_{(1)}$, the set $S^{\text{gen}}_{(2)}$ of routes generated in
the 2nd trellis stage is created by including an appropriate RN right before
the DN, as annotated with the aid of black arrows in Fig 2. Naturally, since
all the routes constituted by two hops have been identified as being Pareto-
optimal, the entire set of routes having three hops is visited by the trellis-
paths in the 2nd trellis stage, as seen in Fig. 2. The set
$S^{\text{OPF}}_{(1)}$ of Pareto-optimal routes of the $1^{st}$ trellis stage
is then concatenated to the set $S^{\text{gen}}_{(2)}$ of the routes generated
in the $2^{nd}$ trellis stage and the set $S^{\text{OPF}}_{(2)}$ of Pareto-
optimal routes is identified. After this operation, the latter is set to
$S^{\text{OPF}}_{(2)}=\left[\\{1\rightarrow 5\\},\\{1\rightarrow 2\rightarrow
5\\},\\{1\rightarrow 3\rightarrow 5\\},\\{1\rightarrow 4\rightarrow
5\\}\right.$, $\left.\\{1\rightarrow 3\rightarrow 2\rightarrow 5\\}\right]$,
hence including the route $\\{1\rightarrow 3\rightarrow 2\rightarrow 5\\}$ to
the OPF, as denoted with the aid of the bold rectangle in Fig. 2. The
surviving routes of the $2^{nd}$ trellis stage are then identified using the
optimization problem of Eq. (11). Explicitly, they constitute the set
$S^{\text{surv}}_{(2)}=\\{1\rightarrow 3\rightarrow 2\rightarrow
5\\},\\{1\rightarrow 3\rightarrow 4\rightarrow 5\\},\\{1\rightarrow
4\rightarrow 2\rightarrow 5\\},\\{1\rightarrow 4\rightarrow 3\rightarrow
5\\}$, as it may be verified by Table I and denoted with the aid of the gray-
filled nodes of Fig. 2.

In the presence of surviving nodes, the optimization process proceeds with the
final trellis stage; however, in this case the routes $\\{1\rightarrow
2\rightarrow 3\rightarrow 4\rightarrow 5\\}$ and $\\{1\rightarrow 2\rightarrow
4\rightarrow 3\rightarrow 5\\}$ are not considered, since their generators do
not have Pareto-optimal sub-routes. This is portrayed in Fig. 2 with the aid
both of the gray dashed arrows and of the gray dashed nodes. Hence, the set
$S^{\text{gen}}_{(3)}=\\{1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow
5\\},\\{1\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow
5\\},\\{1\rightarrow 4\rightarrow 2\rightarrow 4\rightarrow
5\\},\\{1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\\}$ is
generated. The set $S^{\text{OPF}}_{(2)}$ is then concatenated to that of the
routes generated in the final trellis stage and the final set
$S^{\text{OPF}}_{(3)}$ of Pareto-optimal routes is identified. Explicitly, the
latter is identical to the respective set of the $2^{nd}$ trellis stage, since
none of the routes generated in the final stage is Pareto-optimal, as verified
by Table I. Additionally, since we have reached the final stage, the set of
surviving routes is not identified and the process exits by exporting the
hitherto observed OPF.

In a nutshell, this route exploration process succeeds in transforming the
multi-objective routing problem into a series of significantly less complex
sub-problems, each corresponding to a single trellis stage, hence inheriting
the structure of dynamic programming problems [10]. Note that the metric-
accumulation, which is typical in dynamic programming problems, is constituted
by the update of the Pareto-optimal routes. Note that this dynamic programming
framework is optimal in terms of its efficacy in identifying the entire OPF,
just like the exhaustive search method. Primarily, this is a benefit of
Proposition 1, which excludes the routes that are incapable of generating
Pareto-optimal routes during the next trellis stages.

##  IV Evolutionary Quantum Pareto Optimization

In Section III, we introduced a novel dynamic programming framework for the
sake of guiding the search process in identifying the Pareto-optimal routes,
thus effectively reducing the complexity. In this section, we exploit this
framework and further improve it with the aid of our EQPO algorithm. More
specifically, we have relaxed the dynamic programming framework of Section III
for the sake of striking a better accuracy versus complexity trade-off.
Additionally, we have improved the quantum-assisted process of [30] for
identifying the Pareto-optimal routes, so that it becomes capable of
“remembering” the OPF identified in the previous trellis stages. We will refer
to this improved quantum-assisted process as the _Preinitialized-NDQIO_
(P-NDQIO) algorithm. In this context, the P-NDQIO and the EQPO algorithms are
presented in Sections IV-A and IV-B, respectively. Let us now proceed by
presenting the P-NDQIO algorithm.

###  IV-A Preinitialized NDQIO algorithm

The P-NDQIO algorithm, which is formally stated in Alg. 1, is the main
technique of _memorization_ [10], thus providing a significant complexity
reduction by remembering and propagating the OPF identified across the
previous trellis stages to the next ones. Its memorization is performed in
Step 1 of Alg. 1, where the OPF of the current trellis stage is initialized to
that of the previous stage. Subsequently, the P-NDQIO algorithm performs its
iterations, looking for Pareto-optimal routes in Steps 2-14 of Alg. 1.

Algorithm 1 Preinitialized Non-Dominated Quantum Iterative Optimization
Algorithm (P-NDQIO)

1: Initialize the OPF to $S^{\text{OPF}}_{(i)}\leftarrow
S^{\text{OPF}}_{(i-1)}$.

2: repeat

3: $\mathcal{T}\leftarrow 0$.

4: Invoke the BBHT-QSA of [30, Alg. 1] searching for routes in
$S^{\text{gen}}_{(i)}$ that are not dominated by any of the routes of
$S^{\text{OPF}}_{(i)}$ and output $x_{s}$.

5: if $\mathbf{f}(j)\nsucc\mathbf{f}(x_{s}),\leavevmode\nobreak\ \forall j\in
S^{\text{OPF}}_{(i)}$ then

6: repeat

7: Set $j\leftarrow x_{s}$.

8: Invoke the BBHT-QSA of [30, Alg. 1] searching for routes in
$S^{\text{gen}}_{(i)}$ that dominate the route $j$ and output $x_{s}$.

9: until $\mathbf{f}(x_{s})\nsucc\mathbf{f}(j)$.

10: Discard the routes from $S^{\text{OPF}}_{(i)}$ that are dominated by the
route $j$ and append it to the OPF.

11: else

12: Set $\mathcal{T}\leftarrow\mathcal{T}+1$.

13: end if

14: until $\mathcal{T}=2$

15: Export the $S^{\text{OPF}}_{(i)}$ and exit.

During each iteration, which results in identifying a single Pareto-optimal
route, the P-NDQIO algorithm first invokes the so-called _Boyer-Brassard-
Hoyer-Tapp Quantum Search Algorithm_ (BBHT-QSA) [25] for the sake of
identifying routes that are not dominated by any of the routes belonging to
the hitherto identified OPF. We refer to this process as the _Backward BBHT-
QSA_ (BW-BBHT-QSA) process [30]. If an invalid route-solution - i.e. a route
that is indeed dominated by the OPF identified so far - is output by the BBHT-
QSA, the P-NDQIO algorithm concludes that the entire OPF has been identified.
However, since the BBHT-QSA exhibits a low probability of failing to identify
a valid solution444We define a valid route-solution as the specific route that
satisfies the condition in Step 5 of Alg. 1, the BW-BBHT-QSA step is repeated
for an additional iteration in order to ensure the detection of the entire
OPF, as seen in Steps 12 and 14 of Alg. 1. Otherwise, should a valid route-
solution  be identified by the BW-BBHT-QSA step, this specific route is
classified as “potentially” being Pareto-optimal. Consequently, the P-NDQIO
algorithm invokes the so-called _BBHT-QSA chain process_ [19, 30] in Steps 6-9
of Alg. 1. Explicitly, the output of the BW-BBHT-QSA is set as the initial
reference solution in Step 7 of Alg. 1 and a BBHT-QSA process is activated in
Step 8 of Alg. 1, which searches for routes that dominate the reference one.
If a route that dominates the reference one is found, the reference route is
updated to the BBHT-QSA output and a new BBHT-QSA process is activated.
Naturally, the activation of the BBHT-QSA process is repeated until a
particular route is output by the BBHT-QSA that does not dominate the
reference route, thus indicating that the reference route is Pareto-optimal.
Subsequently, the Pareto-optimal routes of the set $S^{\text{OPF}}_{(i)}$ are
checked as to whether they are dominated by the reference route, so that they
are removed and the reference route is then included in
$S^{\text{OPF}}_{(i)}$, as seen in Step 10 of Alg. 1. Explicitly, this check,
which is referred to as the _OPF Self-Repair_ (OPF-SR) process in [30],
provides the EQPO algorithm with resilience against including sub-optimal
routes in the early trellis stages due to the limited number of generated
routes, hence preventing their propagation to the later stages.

Both the BW-BBHT-QSA process and the BBHT-QSA chains are parts of the original
NDQIO algorithm; thus, the P-NDQIO algorithm employs quantum circuits that are
identical to those of the NDQIO algorithm. Therefore, the motivated readers
may refer to [30] for extended discussions.

###  IV-B EQPO algorithm

The dynamic framework introduced in Section III, albeit optimal in terms of
its capability of identifying the entire OPF, it may impose an excessive
complexity quantified in terms of the number of dominance comparisons required
for solving the optimization problem of Eq. (11). To elaborate further, as the
number of UFs considered increases, the number of surviving routes is
increased due to the differences among the UFs. This in turn leads to the
proliferation of the number of routes generated per trellis stage. However,
only a relatively small fraction of the surviving route-population leads
eventually to generating Pareto-optimal routes in the next trellis stages.
Therefore, the employment of the optimal dynamic framework presented in
Section III imposes a significant complexity overhead for the sake of ensuring
the detection of the entire set of Pareto-optimal routes. Consequently, a
performance versus complexity trade-off has to be struck for the sake of
mitigating this complexity overhead. In fact, this specific balance is struck
in the context of the EQPO algorithm by jointly relying on Relaxations 1 and
2.

######  Relaxation 1.

A route can only generate optimal routes based on Definition 3, if it is
Pareto-optimal. This is formally formulated as follows:

$S^{\text{surv}}_{(i)}\triangleq S^{\text{OPF}}_{(i)}-S^{\text{OPF}}_{(i-1)}.$
(12)

Relaxation 1 restricts the set $S^{\text{surv}}_{(i)}$ of the surviving routes
at the end of the $i$-th trellis stage to the set of the newly-discovered
Pareto-optimal routes at this specific trellis stage. This relaxation provides
beneficial complexity reduction, since it makes the identification both of the
set $S^{\text{surv}}_{(i)}$ of surviving routes and of the set
$S^{\text{OPF}}_{(i)}$ of Pareto-optimal routes possible by simply solving the
optimization problem of Eq. (10). Explicitly, Proposition 1 does not conflict
with Relaxation 1, since the Pareto-optimal routes are guaranteed to have
Pareto-optimal sub-routes. This is justified by the fact that the sub-routes
dominate their routes due to the absence of the final hop, which results in
increasing all the UFs considered. Thus, since there exist no route from the
SN to the DN dominating the route identified, there exist no routes dominating
the respective sub-route either. However, the complexity reduction offered by
Relaxation 1 comes at the price of reduced accuracy, since sub-optimal routes
having Parero-optimal sub-routes do exist, which might potentially lead to the
generation of Pareto-optimal routes in the next trellis stages. This specific
limitation is mitigated with the aid of Relaxation 2.

######  Relaxation 2.

For the sake of facilitating the identification of all Pareto-optimal routes,
Definition 3 is relaxed as follows: a specific route $x$ is said to generate
another route $x_{g}^{(j,k)}$ by inserting the single RN $R_{j}$ between the
$k$-th and the $(k+1)$-st nodes.

Relaxation 2 extends the set $S^{\text{gen}}_{(i)}$ of generated routes, which
are created by the set $S^{\text{surv}}_{(i-1)}$ of surviving routes of the
previous trellis stage. This is realized by replacing a single direct link
established either by two RNs or by an RN and the DN with an indirect link
involving an appropriate RN as an intermediate relay. Naturally, this specific
modification enhances the heuristic accuracy of the EQPO algorithm, since it
allows the generation of additional routes, thus acting similarly to the
_mutation operation_ of _genetic algorithms_ [39].

Algorithm 2 Evolutionary Quantum Pareto Optimization (EQPO) Algorithm.

1: Set $S^{\text{gen}}_{(0)}\leftarrow\\{SN\rightarrow DN\\}$,
$S^{\text{OPF}}_{(0)}\leftarrow S^{\text{gen}}_{(0)}$,
$S^{\text{surv}}_{(0)}\leftarrow S^{\text{gen}}_{(0)}$, $i\leftarrow 0$.

2: repeat

3: Set $i\leftarrow i+1$.

4: Generate the set of routes $S^{\text{gen}}_{(i)}$ from the set
$S^{\text{surv}}_{(i-1)}$ based on Relaxation 2 by appropriately inserting a
single RN between two intermediate nodes.

5: Set $S^{\text{gen}}_{(i)}\leftarrow S^{\text{gen}}_{(i)}\cup
S^{\text{OPF}}_{(n-1)}$.

6: Invoke the P-NDQIO algorithm of Alg. 1 in the set $S^{\text{gen}}_{(i)}$
and initialize the identified OPF to $S^{\text{OPF}}_{(n)}\leftarrow
S^{\text{OPF}}_{(n-1)}$.

7: Set $S^{\text{surv}}_{(i)}\leftarrow
S^{\text{OPF}}_{(n)}-S^{\text{OPF}}_{(n-1)}$.

8: until $\left|S^{\text{surv}}_{(i)}\right|=0$ or $i=N_{\text{nodes}}-1$

9: Export the OPF $S^{\text{OPF}}_{(n)}$ and terminate.

Let us now proceed by elaborating on the specifics of the EQPO algorithm,
which is formally presented in Alg. 2. To elaborate further, in Step 1 of Alg.
2 the EQPO algorithm initializes the set of routes generated, the Pareto-
optimal routes as well as the surviving routes to the direct route, i.e. to
the route $\\{SN\rightarrow DN\\}$. It then proceeds with the trellis stages
using Steps 2-8 of Alg. 2. During each trellis stage, the set
$S^{\text{gen}}_{(i)}$ of generated routes is constructed in Step 4 of Alg. 2
relying on Relaxation 2. Upon applying Relaxations 1 and 2 in the trellis of
Fig. 2 results in the trellis of Fig. 3.

This set is then concatenated with the set $S^{\text{OPF}}_{(i-1)}$ of Pareto-
optimal routes identified in the previous stage. Subsequently, the P-NDQIO
algorithm is invoked in Step 6 of Alg. 2 for the sake of identifying the set
$S^{\text{OPF}}_{(i)}$ of Pareto-optimal routes from the set
$S^{\text{gen}}_{(i)}$. Then, the set $S^{\text{surv}}_{(i)}$ of surviving
routes is determined in Step 7 of Alg. 2, relying on Relaxation 1.

More specifically, the steps carried out as part of the EQPO algorithm’s
dynamic programming framework during a single trellis stage are listed as
follows:

Figure 3: Irregular trellis graph designed for guided search-space exploration
for the 5-node WMHN of Fig. 1 using the EQPO algorithm’s dynamic programming
framework, encapsulated by Relaxations 1 and 2. Note that the UVs of each
route are presented in Table I

####  IV-B1 Route Generation

EQPO creates the set $S^{\text{gen}}_{(i)}$ of routes based on the set
$S^{\text{surv}}_{(i-1)}$ of surviving routes from the previous trellis stage
using Relaxation 2, as seen in Step 4 of Alg. 2. For instance, observe in Fig.
3 that the route $\\{1\rightarrow 2\rightarrow 5\\}$ is capable of generating
4 routes, namely the routes $\\{1\rightarrow 2\rightarrow 3\rightarrow 5\\}$,
$\\{1\rightarrow 2\rightarrow 4\rightarrow 5\\}$, $\\{1\rightarrow
3\rightarrow 2\rightarrow 5\\}$, $\\{1\rightarrow 4\rightarrow 2\rightarrow
5\\}$. By contrast, Definition 3 allows the generation of only the first two
routes, as portrayed in Fig. 2. Additionally, in contrast to the optimal
dynamic programming framework of Section III, each route of the current
trellis stage in Fig. 3 can be generated by multiple surviving routes of the
previous stage. This specific feature of Relaxation 2 enhances the heuristic
accuracy, since it enables the generation of potentially Pareto-optimal
routes, which have suboptimal constructors and hence would be disregarded
based on Relaxation 1.

####  IV-B2 Pareto-Optimal and Surviving Routes

Following the construction of the set $S^{\text{gen}}_{(i)}$ of the routes
generated, the EQPO algorithm invokes the P-NDQIO algorithm of Section IV-A in
Step 6 of Alg. 2 in order to search for new Pareto-optimal routes belonging to
the set $S^{\text{gen}}_{(i)}$. However, based on Definition 2, the optimality
of the route depends on the set of eligible routes considered. Consequently,
the OPF $S^{\text{OPF}}_{(i-1)}$ hitherto identified across all the previous
trellis stages has to be concatenated with $S^{\text{gen}}_{(i)}$ in Step 5 of
Alg. 2, thus ensuring that the routes identified as optimal by the P-NDQIO
algorithm are indeed Pareto-optimal with respect to the entire set of
legitimate routes. Note that the set $S^{\text{OPF}}_{(i)}$ contains the
Pareto-optimal routes across all trellis stages all the way up to the $i$-th
one, as in the optimal dynamic programming framework of Section III.
Consequently, using Relaxation 1 the Pareto-optimal routes identified at the
current trellis stage are considered as surviving routes. Note that the
Pareto-optimal routes identified throughout the previous stages are not taken
into account, since they would generate routes already processed during the
previous trellis stages.

The EQPO algorithm continues processing the trellis stages either until it
reaches a trellis stage having no surviving paths or when the maximum
affordable number of trellis stages is exhausted, in a similar fashion to the
optimal dynamic programming framework of Section III.

Let us now highlight the differences between the trellises of Figs. 2 and 3
considering the 5-node example of Fig. 1. Note that the same annotation is
used in Fig. 3 as that of Fig. 2 Explicitly, based on Eq. (12), the EQPO
algorithm classified the specific routes, which are Pareto-optimal as being
“Pareto-Optimal” and those that have been generated in the current stage as
“Visited & Surviving”. Hence in contrast to Fig. 2, they are equivalent in
Fig. 3. Similar to the optimal dynamic programming framework of Section III,
the EQPO algorithm initializes the set $S^{\text{gen}}_{(1)}$ of generated
routes to the set of the legitimate routes having either single or two hops,
as portrayed in the $1^{st}$ trellis stage of Fig. 3. Based on Table I, all
the routes having two hops are Pareto-optimal and thus the EQPO algorithm
classifies them as the surviving routes of the $1^{st}$ trellis stage, as seen
in Fig. 3. Similar to Fig. 2, the EQPO algorithm’s trellis paths visit the
entire set of routes having three hops and then the algorithm identifies the
route $\\{1\rightarrow 3\rightarrow 2\rightarrow 5\\}$ as Pareto-optimal with
the aid of the P-NDQIO algorithm. Consequently, this specific route is deemed
to be the sole surviving route in Fig 3. This is in contrast to Fig. 2, where
three more routes have been identified as surviving ones. Recall from Fig. 2
that these routes do not lead to Pareto-optimal routes in the last trellis
stage. This in turn results in the EQPO algorithm visiting one less route in
the $3^{rd}$ trellis stage, i.e. not considering the sub-optimal route
$\\{1\rightarrow 4\rightarrow 2\rightarrow 3\rightarrow 5\\}$ as potentially
Pareto-optimal.

##  V Complexity versus Accuracy Discussions

In this section, we will characterize the complexity imposed by the EQPO Alg.
presented in Alg. 2 and evaluate its heuristic accuracy versus the complexity
invested. Additionally, note that since we had no quantum computer at our
disposal, the simulations of the QSAs were carried out using a classical
cluster. Explicitly, since the _quantum oracle gate_ $O$ [27] calculates in
parallel the UF vectors of all the legitimate routes in the QD, they were pre-
calculated. We note that this results in an actual complexity higher than that
of the full-search method. Therefore, the employment of the quantum algorithms
in a quantum computer is essential for observing a complexity reduction as a
benefit of the QP. Hence, in our simulations, we have made the assumption of
employing a quantum computer and we count the total number of $O$ activations
for quantifying the EQPO’s complexity. This number would be the same for both
classical and quantum implementations. Note that in the following analysis we
will use the notation $N^{x}_{(i)}\equiv\left|S^{x}_{(i)}\right|$, where
$N^{x}_{(i)}$ corresponds to the cardinality of the set $S^{x}_{(i)}$.

Furthermore, our simulation results have been averaged over $10^{8}$ runs.
During each run we have randomly generated the node’s locations as well as the
interference levels experienced by them with the aid of the respective
distributions mentioned in Section II. We have ensured that each run is
uncorrelated with the rest of the runs.

Let us now proceed by analytically characterizing the complexity imposed by
our proposed algorithm.

###  V-A Complexity

We will first characterize the complexity imposed by the EQPO algorithm’s
dynamic progamming framework, when the exhaustive search is employed instead
of the P-NDQIO algorithm in Step 6 of Alg. 2. We will refer to this method as
the _Classical Dynamic Programming_ (CDP) method and we will use it as a
benchmarker for assessing the complexity reduction offered by the QP.

Prior to characterizing the EQPO algorithm and the CDP method we will analyze
the the orders of the number $N_{(i)}^{\text{surv}}$ of the surviving routes
and of the number $N_{(i)}^{\text{OPF}}$ of the Pareto-optimal routes
identified across the first $i$ trellis stages. As far as the number
$N_{(i)}^{\text{OPF}}$ of the Pareto-optimal routes identified across the
first $i$ trellis stages is concerned, the trellis graph guiding the search
for Pareto-optimal routes identifies more Pareto-optimal routes, as it
proceeds through more trellis stages. Explicitly, its order can be formally
expressed as follows:

$O(N_{(i)}^{\text{OPF}})=O(a_{i}N_{\text{OPF}})=O(N_{\text{OPF}}),\leavevmode\nobreak\
\forall i\in\\{1,\dots,N_{\text{nodes}}-1\\},$ (13)

where $a_{i}$ corresponds to the fraction of the OPF identified by the first
$i$ trellis stages. Naturally, this fraction $a_{i}$ approaches unity as the
number $i$ of trellis stages moves closer to the maximum number of hops.

Moving on to the number $N_{(i)}^{\text{surv}}$ of the surviving routes at the
$i$-stage, it is equal to the number of Pareto-optimal routes identified at
the $i$-th trellis stage, based on Relaxation 1. Explicitly,
$N_{(i)}^{\text{surv}}$ is a fraction of the total number
$N_{(i)}^{\text{OPF}}$ of the Pareto-optimal routes identified across the
first $i$ trellis stages. Hence, we have
$N_{(i)}^{\text{surv}}=b_{i}N^{\text{OPF}}_{(i)}$ with $b_{i}\leq 1$ $\forall
i\in\\{1,\dots,N_{\text{nodes}}-1\\}$, since the set $S_{(i)}^{\text{surv}}$
of Pareto-optimal routes at the $i$-th trellis stage is included in the set
$S_{(i)}^{\text{OPF}}$ of Pareto-optimal routes identified at the first $i$
trellis stages. Therefore we can evaluate the order $O(N_{(i)}^{\text{surv}})$
as follows:

$O(N_{(i)}^{\text{surv}})=O(b_{i}N^{\text{OPF}}_{(i)})\mathop{=}\limits^{\eqref{eq:NOPF_order}}O(b_{i}a_{i}N_{\text{OPF}})=O(N_{\text{OPF}}).$
(14)

Consequently, in Eqs. (13) and (14), we have upper bounded the order
$O(N_{(i)}^{\text{surv}})$ of the number of surviving routes at the $i$-th
stage as well as the order $O(N_{(i)}^{\text{OPF}})$ of the number of Pareto-
optimal routes identified at the first $i$ stages by the order
$O(N_{\text{OPF}})$ of the total number of Pareto-optimal routes, i.e. we have
$O(N_{(i)}^{\text{surv}})=O(N_{(i)}^{\text{OPF}})=O(N_{\text{OPF}})$.
Naturally, Eq. (13) and (14) will facilitate the complexity analysis, since
they render the aforementioned orders independent of the index $i$ of the
trellis stages. Let us now proceed by characterizing the complexity imposded
by the CDP method.

####  V-A1 CDP method’s complexity

Let us assume that there is a total of $N^{\text{gen}}_{(i)}$ generated routes
arriving at the $i$-th trellis stage. These particular routes are generated by
the specific Pareto-optimal routes identified at the previous trellis stage,
which are $N^{\text{surv}}_{(i-1)}$ in total. Based on the aforementioned
assumptions, the number of generated routes arriving at the $i$-th trellis
stage is formulated as follows:

$\displaystyle N^{\text{gen}}_{(i)}$
$\displaystyle=N^{\text{surv}}_{(i-1)}(N_{\text{nodes}}-1-i)i=O\left[N^{\text{surv}}_{(i-1)}N_{\text{nodes}}i\right],$
$\displaystyle\mathop{=}\limits^{\eqref{eq:Nsurv_order}}O\left[N_{\text{OPF}}N_{\text{nodes}}i\right].$
(15)

Since the set of Pareto-optimal routes of the previous trellis stage are
concatenated to the set of generated routes in Step 5 of Alg. 2, the total
number of routes considered at the $i$-th trellis stage is given by:

$N^{\text{routes}}_{(i)}=N^{\text{gen}}_{(i)}+N^{\text{OPF}}_{(i-1)}\mathop{=}\limits^{\eqref{eq:NOPF_order},\eqref{eq:Ngen_i}}O\left[N_{\text{OPF}}N_{\text{nodes}}i\right].$
(16)

Additionally, the CDP method performs $O[(N^{\text{routes}}_{(i)})^{2}]$
dominance comparisons, which we will refer to as the _Cost Function
Evaluation_ (CFE), since each generated route has to be compared to all of the
routes considered. Therefore, the total complexity imposed by the CDP method
across all trellis stages may be quantified in terms of the number of
dominance comparisons, which is formulated as follows:

$L_{\text{CDP}}=\sum\limits_{i=1}^{N_{\text{nodes}}-1}O\left[\left(N^{\text{routes}}_{(i)}\right)^{2}\right]=O(N_{\text{OPF}}^{2}N_{\text{nodes}}^{5}),$
(17)

where we have exploited the property of the sum of squared numbers [37], where
we have $\sum^{n}_{i=1}{i^{2}}=O(n^{3})$.

####  V-A2 EQPO algorithm’s complexity

Moving on to the EQPO algorithm’s complexity analysis, the P-NDQIO algorithm
is activated once per trellis stage, based on Alg. 2. Note that we will
classify the complexity imposed by the P-NDQIO into two different domains,
namely that of the parallel and that of the sequential complexity. To
elaborate further, the P-NDQIO algorithm also exploits the synergies between
QP and HP, which was utilized by the NDQIO algorithm of [30]. Explicitly, the
parallel complexity, which is termed as “normalized execution time” in [30],
is defined as the number of dominance comparisons, when taking into account
the degree of HP. Therefore, it may be deemed to be commensurate with the
algorithm’s actual normalized execution time. By contrast, the sequential
complexity, which is termed as “normalized power consumption” in [30], is
defined as the total number of dominance comparisons, without considering the
potential degree of HP. Hence, this specific complexity may be deemed to be
commensurate with the algorithm’s normalized power consumption, as elaborated
in [30] as well.

Let us now proceed by characterizing the complexity of the individual sub-
processes of the P-NDQIO process. During each trellis stage, the P-NDQIO
algorithm activates its BW-BBHT-QSA step. This step invokes the BBHT-QSA once;
however, since the quantum circuits of the original NDQIO algorithm are
utilized, each activation of the quantum oracle, namely the operator $U_{G}$
in [30, Fig. 8], compares each of the generated routes to all the routes
comprising the OPF identified so far. Since this set of comparisons is carried
out in parallel, a single activation imposes a single CFE and
$N^{\text{OPF}}_{(i)}$ CFEs in the parallel and sequential domains,
respectively. Note that the BW-BBHT-QSA process will be activated
$(N^{\text{surv}}_{(i)}+2)$ times during a single trellis stage, since we
opted for repeating this step for an additional iteration, when the BBHT-QSA
fails to identify a valid route. Therefore, the parallel and sequential
complexity imposed by the BW-BBHT-QSA process are quantified as follows:

$\displaystyle L^{BW,P}_{(i)}$
$\displaystyle=(N^{\text{surv}}_{(i)}+2)L_{\text{BBHT}}(N^{\text{routes}}_{(i)}),$
(18) $\displaystyle=O(N_{\text{OPF}}\sqrt{N_{\text{OPF}}N_{\text{nodes}}i}),$
(19) $\displaystyle L^{BW,S}_{(i)}$
$\displaystyle=\sum\limits_{j=0}^{N^{\text{surv}}_{(i)}}{(j+N^{\text{OPF}}_{(i-1)})}\leavevmode\nobreak\
L_{\text{BBHT}}(N^{\text{routes}}_{(i)})+$
$\displaystyle\;\;\;\;+N^{\text{surv}}_{(i)}L_{\text{BBHT}}(N^{\text{routes}}_{(i)}),$
(20)
$\displaystyle=O(N_{\text{OPF}}^{2}\sqrt{N_{\text{OPF}}N_{\text{nodes}}i}).$
(21)

Recall that the term $N^{\text{surv}}_{(i)}$ in Eqs. (18) and (20) corresponds
to the number of Pareto-optimal routes identified . Additionally, for the
calculation of the orders of complexity we have relied on the fact that the
BBHT-QSA has a complexity on the order of $L_{\text{BBHT}}(N)=O(\sqrt{N})$ as
demonstrated both in [30] and in [25]. Moving on to the complexity imposed by
the BBHT-QSA chains, it has been demonstrated in [30] that the complexity
imposed by a single of BBHT-QSA chain - which leads to the identification of a
single Pareto-optimal route - is identical to that of the so-called _Durr-
Hoyer Algorithm_ (DHA) [26], namely on the order of
$L_{\text{DHA}}(N)=O(\sqrt{N})$ in terms of the number of quantum oracle gate
activations. As for the latter, the $U_{g^{\prime}}$ quantum operator of [30,
Fig. 7] has been utilized, which implements a dominance comparison.
Explicitly, each activation of this operator imposes a parallel complexity of
$1/K$ CFEs and a sequential complexity of a single CFE, owing to the parallel
implementation of the UF comparisons. Therefore, the parallel and sequential
complexity imposed by the BBHT-QSA chains are quantified as follows:

$\displaystyle L^{chain,P}_{(i)}$
$\displaystyle=\frac{N^{\text{surv}}_{(i)}}{K}L_{\text{DHA}}(N^{\text{routes}}_{(i)}),$
(22) $\displaystyle=O(N_{\text{OPF}}\sqrt{N_{\text{OPF}}N_{\text{nodes}}i}),$
(23) $\displaystyle L^{chain,S}_{(i)}$
$\displaystyle=N^{\text{surv}}_{(i)}L_{\text{DHA}}(N^{\text{routes}}_{(i)}),$
(24) $\displaystyle=O(N_{\text{OPF}}\sqrt{N_{\text{OPF}}N_{\text{nodes}}i}).$
(25)

Finally, as for the OPF-SR dominance comparisons of Step 10 of Alg. 1, the
parallel and sequential complexity imposed by this process are quantified as
follows:

$\displaystyle L^{SR,P}_{(i)}$
$\displaystyle=\frac{1}{K}\sum\limits_{j=1}^{N^{\text{surv}}_{(i)}}(j+N^{\text{OPF}}_{(i-1)})=O(N_{\text{OPF}}^{2}),$
(26) $\displaystyle L^{SR,S}_{(i)}$
$\displaystyle=\sum\limits_{j=1}^{N^{\text{surv}}_{(i)}}(j+N^{\text{OPF}}_{(i-1)})=O(N_{\text{OPF}}^{2}).$
(27)

Recall from Eqs. (19), (21), (23), (25), (26) and (27) that we used Eqs. (13)
and (14), where we have
$O(N^{\text{surv}}_{(i)})=O(N^{\text{OPF}}_{(i)})=O(N_{\text{OPF}})$ with
$N_{\text{OPF}}$ corresponding to the total number of Pareto-optimal routes.
Let us now proceed with the evaluation of the total parallel and sequential
complexities of the EQPO algorithm. In the worst-case scenario the EQPO
algorithm will process $(N_{\text{nodes}}-1)$ trellis stages, corresponding to
the maximum possible number of hops, whilst visiting each node at most once.
Thus, the total parallel and sequential complexities imposed by the EQPO
algorithm are quantified as follows:

$\displaystyle L_{EQPO}^{P}$
$\displaystyle=\sum\limits_{i=1}^{N_{\text{nodes}}-1}{L^{BW,P}_{(i)}+L^{chain,P}_{(i)}+L^{SR,P}_{(i)}},$
(28) $\displaystyle=O(N_{\text{OPF}}^{3/2}N_{\text{nodes}}^{2}),$ (29)
$\displaystyle L_{EQPO}^{S}$
$\displaystyle=\sum\limits_{i=1}^{N_{\text{nodes}}-1}{L^{BW,S}_{(i)}+L^{chain,S}_{(i)}+L^{SR,S}_{(i)}},$
(30) $\displaystyle=O(N_{\text{OPF}}^{5/2}N_{\text{nodes}}^{2}).$ (31)

Note that in Eqs. (29) and (31) we have exploited the specific property of the
sum of square roots, where we have $\sum_{i=1}^{n}{\sqrt{i}}=O(n^{3/2})$ [37].
Observe from Eqs. (17) and (29) that the EQPO algorithm achieves a parallel
complexity reduction against the CDP method by a factor on the order of
$O(N^{3}_{\text{nodes}}\sqrt{N_{\text{OPF}}})$. Additionally, the respective
sequential complexity reduction is by a factor on the order of
$O(N^{3}_{\text{nodes}}/\sqrt{N_{\text{OPF}}})$, based on Eqs. (17) and (31).
Hence, the EQPO imposes a lower sequential complexity than the CDP method, as
long as we have $O(N_{\text{nodes}}^{3})>O(\sqrt{N_{\text{OPF}}})$. As far as
the EQPO algorithm’s predecessors are concerned, it has been proven in [30]
that the NDQO algorithm imposes identical parallel and sequential
complexities, which are on the order of $O(N\sqrt{N})$. By contrast, the NDQIO
algorithm imposes a parallel and a sequential complexity, which are on the
order of $O(N_{\text{OPF}}\sqrt{N})$ and $O(N^{2}_{\text{OPF}}\sqrt{N})$,
respectively, where $N$ corresponds to the total number of legitimate routes.
Consequently, the complexity imposed by both the NDQO and the NDQIO algorithms
is proportional to $O(\sqrt{N})$ in both domains, yielding an exponential
increase in the order of complexity as the number nodes increases. By
contrast, both the EQPO algorithm and the CDP method exhibit a complexity
order similar to polynomial scaling, since its has been demonstrated in [30,
Fig. 11] that the total number $N_{\text{OPF}}$ of Pareto-optimal routes
increases at a significantly lower rate than that of the total number $N$ of
routes.

(a) Parallel Complexity (b) Sequential Complexity

Figure 4: EQPO Alg. (a) parallel and (b) sequential complexity quantified in
terms of the number of CFEs. The results have been averaged over $10^{8}$
runs.

Let us now proceed by presenting the average parallel and the average
sequential complexity imposed both by the EQPO algorithm and by the CDP
method, which are shown in Figs. 4a and 4b, respectively. We will compare the
complexities imposed by the aforementioned algorithms to those of the _Brute-
Force_ (BF) method as well as to those of the EQPO algorithm’s predecessors,
namely the NDQO and the NDQIO algorithms. The aforementioned methods consider
the entire set of legitimate routes, hence they have no database correlation
exploitation capabilities. Additionally, the NDQO algorithm and the BF method
do not employ any HP scheme, thus their respective parallel and sequential
complexities are identical. As far as the average complexity of the CDP method
is concerned, observe in Figs. 4a and 4b that it requires a higher number of
CFEs than the BF method for WMHNs having less than 8 nodes. This parallel
complexity overhead is justified by the fact that the number $N_{\text{OPF}}$
of Pareto-optimal routes w.r.t. the total number $N$ of legitimate routes is
relatively high. This in turn yields an increase in the fraction of trellis
nodes that are classified as survivors, hence leading to more dominance
comparisons. However, this trend is reversed for WMHNs having more than 7
nodes, where the CDP method exhibits a complexity reduction compared to the BF
method. More specifically, for WMHNs constituted by 9 nodes, this complexity
reduction is close to an order of magnitude. Still referring to 9-node WMHNs,
the CDP method imposes a slightly higher parallel complexity than that of the
NDQO algorithm, while it matches the sequential complexity of the NDQIO
algorithm for the same 9-node network, based on Figs. 4a and 4b, respectively.

Moving on to the average parallel complexity of the EQPO algorithm, observe in
Fig. 4a that the EQPO algorithm imposes fewer CFEs than the rest of the
algorithms considered for WHMNs having more than 5 nodes. Explicitly, this
complexity reduction becomes more substantial, as the number of nodes
increases, reaching a parallel complexity reduction of almost an order of
magnitude for 9-node WMHNs, when compared to the NDQIO algorithm, which is
capable of exploiting the HP as well. As for its sequential complexity,
observe in Fig. 4b that the EQPO algorithm imposes more CFEs than the rest of
the algorithms for WMHNs having less than 7 nodes. This may be justified by
the relatively small number of surviving routes, which does not allow the QP
to excel by providing beneficial complexity reduction. However, this trend is
reversed for WMHNs having more than 6 nodes, where the number of surviving
routes becomes higher. More specifically for 9-node WMHNs, the EQPO algorithm
begins to impose a sequential complexity reduction w.r.t. all the remaining
algorithms considered. Additionally, observe in Figs. 4a and 4b that the EQPO
algorithm’s complexity increases with a much lower gradient, as the number of
nodes increases, when compared to the full-search-based algorithms, namely to
the BF method as well as to the NDQO and the NDQIO algorithms. Explicitly,
this is justified by the “almost polynomial” order of complexity, as
demonstrated in Eqs. (29) and (31).

###  V-B Accuracy

Having elaborated on the complexity imposed by the EQPO let us now proceed by
discussing its heuristic accuracy. Since our design target is to identify the
entire set of Pareto-optimal routes, we will evaluate the EQPO algorithm’s
accuracy versus the complexity imposed in terms of two metrics, namely that of
the average _Pareto distance_ $E[P_{d}]$ and that of the average _Pareto
complection_ $E[C]$. The same set of metrics have been considered in [30] for
the evaluation of NDQIO algorithm’s accuracy as well. To elaborate further,
the Pareto distance of a particular route is defined as the probability of
this specific route being dominated by the rest of the legitimate routes.
Explicitly, given a set of Pareto-optimal routes identified by the EQPO
algorithm, their average Pareto distance is a characteristic of the OPF, since
it provides insights into the proximity of the exported OPF to the true OPF.
Naturally, a Pareto distance having a value of $E[P_{d}]=0$ implies that the
OPF identified by the EQPO is fully constituted by true Pareto-optimal routes.
By contrast, the average Pareto completion is defined as the specific fraction
of the solutions on the true OPF identified by the EQPO. Therefore, our goal
is to achieve a Pareto completion as close to $E[C]=1$ as possible.

(a)  (b)  (c)  (d)

Figure 5: EQPO algorithm performance in terms of its Pareto dinstance (a,b)
and its Pareto Completion (c,d) versus the parallel complexity (a,c) and the
sequential complexity (b,d) for required 7-node WHMNs. The results have been
averaged over $10^{8}$ runs.

Having defined the performance metrics, let us now present the performance
versus complexity results of the EQPO algorithm, which are shown in Fig. 5 for
7-node WMHNs. The reason we have evaluated the aforementioned metrics for
7-node WMHNs is for the sake of comparison to the methods analyzed in [19] as
well as in [30]. Apart from the NDQO and NDQIO algorithms, we have used as
benchmarks two additional classical evolutionary algorithms555The readers
should refer to [19] and to [18] for a detailed description of the MO-ACO and
the NSGA-II, respectively., namely the NSGA-II and the MO-ACO. Using the same
convention as in [19] and [30], we have set the number of individuals equal to
the number of generations and we have matched the total parallel complexity
imposed by these classical algorithms to that of the NDQO algorithm, since the
NDQO algorithm appears to impose the highest parallel complexity, based on
Fig. 4a. As for their total sequential complexity we have set it to that of
the NDQIO algorithm. Consequently, we have considered employing 19 individuals
over 19 generations for the parallel complexity matching and 29 individuals
over 29 generations for the sequential complexity matching for both the NSGA-
II and the MO-ACO algorithm.

Let us now proceed by elaborating on the average Pareto distance exhibited by
7-node WMHNs versus the parallel complexity invested, as portrayed in Fig. 5a.
Observe in this figure that the EQPO algorithm performs optimally – in the
sense that no suboptimal routes are included in the OPF – for about 130 CFEs
and then exhibits an error floor around $6\cdot 10^{-6}$. Similar trends are
observed for the classical NSGA-II and for MO-ACO algorithm as well as for the
quantum-assisted NDQO algorithm; the classical benchmark algorithms both
exhibit an error floor around $10^{-3}$, while the respective NDQO algorithm’s
error floor is around $7\cdot 10^{-9}$. By contrast, the NDQIO algorithm
initially has an error floor of about $3\cdot 10^{-5}$, which then decays to
infinitesimally low levels, when more CFEs are invested owing to its OPF-SR
process [30]. This specific trend is visible in Fig. 5a, where the NDQIO
algorithm outperforms the NDQO technique in terms of their $E[P_{d}]$ beyond
8842 CFEs in the sequential complexity domain. Additionally, the NDQIO
algorithm begins to exhibit a lower $E[P_{d}]$ than that of the EQPO algorithm
after 498 and 2932 CFEs in the parallel and sequential domains, respectively.

Let us now provide some further insights into the significance of the
aforementioned error floors. Explicitly, a particular route is considered
suboptimal, if there exists even just a single route dominating it, i.e. if it
has a Pareto distance higher than or equal to $P^{th}_{d}=1/N$, where $N$
corresponds to the total number of legitimate routes. This threshold is
visually portrayed with the aid of the dashed and dotted horizontal lines in
Figs. 5a and 5b. Hence, we can normalize the results w.r.t. this threshold for
exporting the probability of a specific route becoming suboptimal.
Consequently, EQPO algorithm’s error floor is translated into a probability of
a specific route being suboptimal, which is equal to 0.2%, while the
respective probability of the NDQO algorithm is equal to $2\cdot 10^{-6}$.
Additionally, the respective probabilities of the classical benchmark
algorithms are about 33% and 3.3%, when parallel and sequential complexity are
considered, respectively. Consequently, the EQPO algorithm’s probability of
opting for a suboptimal route may be regarded as negligible.

The evaluation of the average Pareto completion probability versus the
parallel and the sequential complexity are shown in Figs. 5c and 5d. Note that
the subplots inside these figures portray the portion of unidentified true
Pareto-optimal routes, as encapsulated by the expression of $1-E[C]$.
Explicitly, we will utilize this metric for assessing the error floor w.r.t.
the $E[C]$, which may not be visible from the main plots. Additionally, note
that we examined both $E[P_{d}]$ and $E[C]$ versus the parallel and sequential
complexity imposed up to the maximum value observed by the EQPO algorithm. As
far as the EQPO algorithm’s average Pareto completion versus the parallel
complexity is concerned, observe in Fig. 5c that the EQPO is capable of
identifying a higher portion of the true OPF, when compared to the rest of the
algorithms examined, while considering the same number of CFEs in the parallel
complexity domain. Explicitly, the EQPO algorithm succeeds in identifying
almost the entire set of Parero-optimal routes, since it is only incapable of
identifying as few as 0.1% of the entire true OPF. This error floor is reached
after 1301 and 14651 CFEs in the parallel and sequential complexity domains,
respectively, as it can be verified by Figs. 5c and 5d.

By contrast, this trend is not echoed in the sequential complexity domain. To
elaborate further, observe in Fig. 5b that the EQPO algorithm remains more
efficient than its classical counterparts. On the other hand, while it is
indeed more efficient than the NDQO algorithm up to a complexity budget of
2147 sequential CFEs, it identifies less Pareto-optimal routes than the NDQO
algorithm. The same trend is observed for the NDQIO algorithm as well for a
complexity budget of 4794 sequential CFEs. Nevertheless, this discrepancy
between the parallel and sequential complexity is expected to be decreased, as
the number of nodes increases. This is justified by the fact that the EQPO
algorithm imposes a lower sequential complexity as the nodes proliferate, as
seen in Fig. 4b.

Last but not least, the results portrayed on Fig. 5 rely on the intelligent
central node having perfect knowledge both of the nodes’ geo-locations and of
the interference power levels experienced by them. This fundamental
assumption, albeit impractical, provides us with the upper bound of the
achievable performance of the routing schemes considered. Explicitly, despite
its impractical nature, it facilitates a fair comparison of the EQPO algorithm
to its predecessors in terms of their complexity and heuristic accuracy, which
is the main focus of this treatise. Intuitively, a practical network
information update process would result in both approximated and outdated
network information, thus degrading the results of Fig. 5, while maintaining
the complexity per routing routing optimization at a similar order. Note that
we plan on characterizing these imperfections and conceive a practical network
information update scheme in our future work.

##  VI Conclusions

In this treatise we have exploited the correlations in the formation of the
Pareto-optimal routes for the sake of achieving a routing complexity
reduction. In this context, we have first developed an optimal dynamic
programming framework, which transforms the multi-objective routing problem
into a decoding problem. However, this optimal framework imposes a high
complexity. For this reason, we relaxed the aforementioned framework and
proposed the EQPO algorithm, which is empowered by the P-NDQIO algorithm and
thus jointly exploits the synergies between the QP and the HP along with the
potential correlation in the formation of the Pareto-optimal routes. We then
analytically characterized the complexity imposed by the EQPO algorithm showed
that it is capable of solving the multi-objective routing problem in near-
polynomial time. In fact, the EQPO achieved a parallel complexity reduction of
almost an order of magnitude and a sequential complexity reduction by a factor
of 3 for 9-node WMHNs. Finally, we demonstrated with the aid of simulations
that this complexity reduction only imposes an almost negligible error, which
was found to be 0.2% and 0.1% in terms of the average Pareto distance and the
average Pareto completion probability for 7-node WMHNs.

##  Appendix A Proof of Proposition 1

###### Proof.

Let us consider the route
$x^{(j)}_{g}=\\{SN{\rightarrow}\bar{R}_{i}{\rightarrow}R_{j}{\rightarrow}DN\\}$
generated by the route $x$. Based on Eq. (9), the UFs associated with this
specific route are equal to:

$f_{k}(x^{(j)}_{g})=f_{k}(SN{\rightarrow}\bar{R}_{i})+f_{k}(\bar{R}_{i}{\rightarrow}R_{j})+f_{k}(R_{j}{\rightarrow}DN).$
(32)

Additionally, the sub-route $x^{\prime}$ is associated with the following UFs

$f_{k}(x^{\prime})=f_{k}(SN{\rightarrow}\bar{R}_{i}).$ (33)

Since we have $f_{k}(x)>0,\;\forall x$ from Eq. (9), the sub-route
$x^{\prime}$ strongly dominates the route $x^{(j)}_{g}$ based on Eqs. (32) and
(33), i.e. we have $\mathbf{f}(x^{\prime})\succ\mathbf{f}(x^{(j)}_{g})$. Since
now there is a specific route $x_{d}$ from the SN to DN that weakly dominates
the sub-route $x^{\prime}$, i.e. we have
$\mathbf{f}(x_{d})\succeq\mathbf{f}(x^{\prime})$, the route $x_{d}$ strongly
dominates the route $x^{(j)}_{g}$ as well, yielding:

$\displaystyle\mathbf{f}(x_{d})$
$\displaystyle\succeq\mathbf{f}(x^{\prime})\succ\mathbf{f}(x^{(j)}_{g}),$ (34)
$\displaystyle\mathbf{f}(x_{d})$ $\displaystyle\succ\mathbf{f}(x^{(j)}_{g})$
(35)

Consequently, based on Eq. (35) the route $x^{(j)}_{g}$ cannot be Pareto-
optimal, since it is strongly dominated by the route $x_{d}$. ∎

## References

  * [1] Z. Jiao, B. Zhang, C. Li, and H. T. Mouftah, “Backpressure-based routing and scheduling protocols for wireless multihop networks: A survey,” IEEE Wireless Communications, vol. 23, pp. 102–110, February 2016.
  * [2] B. Alawieh, Y. Zhang, C. Assi, and H. Mouftah, “Improving spatial reuse in multihop wireless networks - a survey,” IEEE Communications Surveys Tutorials, vol. 11, pp. 71–91, Aug 2009.
  * [3] Y. Chen, S. Zhang, S. Xu, and G. Y. Li, “Fundamental trade-offs on green wireless networks,” IEEE Communications Magazine, vol. 49, pp. 30–37, June 2011.
  * [4] H. Yetgin, K. T. K. Cheung, M. El-Hajjar, and L. Hanzo, “Network-lifetime maximization of wireless sensor networks,” IEEE Access, vol. 3, pp. 2191–2226, 2015.
  * [5] A. Abdulla, H. Nishiyama, J. Yang, N. Ansari, and N. Kato, “Hymn: A novel hybrid multi-hop routing algorithm to improve the longevity of wsns,” IEEE Transactions on Wireless Communications, vol. 11, no. 7, pp. 2531–2541, 2012.
  * [6] L. Tan, Z. Zhu, F. Ge, and N. Xiong, “Utility maximization resource allocation in wireless networks: Methods and algorithms,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 45, pp. 1018–1034, July 2015.
  * [7] Y. Shi, Y. T. Hou, and H. Sherali, “Cross-layer optimization for data rate utility problem in UWB-based ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 7, pp. 764–777, June 2008.
  * [8] M. Caleffi, I. F. Akyildiz, and L. Paura, “Opera: Optimal routing metric for cognitive radio ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 11, pp. 2884–2894, August 2012.
  * [9] R. Banirazi, E. Jonckheere, and B. Krishnamachari, “Heat-Diffusion: Pareto optimal dynamic routing for time-varying wireless networks,” in IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, pp. 325–333, April 2014.
  * [10] S. Dasgupta, C. H. Papadimitriou, and U. Vazirani, Algorithms.  McGraw-Hill, Inc., 2006.
  * [11] D. Ramirez and B. Aazhang, “Optimal routing and power allocation for wireless networks with imperfect full-duplex nodes,” IEEE Transactions on Wireless Communications, vol. 12, pp. 4692–4704, September 2013.
  * [12] J. Zuo, C. Dong, H. V. Nguyen, S. X. Ng, L. L. Yang, and L. Hanzo, “Cross-layer aided energy-efficient opportunistic routing in ad hoc networks,” IEEE Transactions on Communications, vol. 62, pp. 522–535, February 2014.
  * [13] C. Luo, S. Guo, S. Guo, L. T. Yang, G. Min, and X. Xie, “Green communication in energy renewable wireless mesh networks: Routing, rate control, and power allocation,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, pp. 3211–3220, Dec 2014.
  * [14] Q. You, Y. Li, M. S. Rahman, and Z. Chen, “A near optimal routing scheme for multi-hop relay networks based on Viterbi algorithm,” in 2012 IEEE International Conference on Communications (ICC), pp. 4531–4536, June 2012.
  * [15] Y. Wang, M. Z. Bocus, and J. P. Coon, “Dynamic programming for route selection in multihop fixed gain amplify-and-forward relay networks,” IEEE Communications Letters, vol. 17, pp. 932–935, May 2013.
  * [16] J. Yao, S. Feng, X. Zhou, and Y. Liu, “Secure routing in multihop wireless ad-hoc networks with decode-and-forward relaying,” IEEE Transactions on Communications, vol. 64, pp. 753–764, Feb 2016.
  * [17] K. Deb, “Multi-objective optimization,” in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (E. K. Burke and G. Kendall, eds.), pp. 403–449, Boston, MA: Springer US, 2014\.
  * [18] H. Yetgin, K. Cheung, and L. Hanzo, “Multi-objective routing optimization using evolutionary algorithms,” in IEEE Wireless Communications and Networking Conference (WCNC), pp. 3030–3034, 2012.
  * [19] D. Alanis, P. Botsinis, S. X. Ng, and L. Hanzo, “Quantum-assisted routing optimization for self-organizing networks,” IEEE Access, vol. 2, pp. 614–632, 2014.
  * [20] B. Gurakan, O. Ozel, and S. Ulukus, “Optimal energy and data routing in networks with energy cooperation,” IEEE Transactions on Wireless Communications, vol. 15, pp. 857–870, Feb 2016.
  * [21] M. Camelo, C. Omaña, and H. Castro, “QoS routing algorithm based on multi-objective optimization for wireless mesh networks,” in 2010 IEEE Latin-American Conference on Communications (LATINCOM), pp. 1–6, 2010.
  * [22] F. Martins, E. Carrano, E. Wanner, R. H. C. Takahashi, and G. Mateus, “A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks,” IEEE Sensors Journal, vol. 11, no. 3, pp. 545–554, 2011.
  * [23] M. Lopez-Ibanez and T. Stutzle, “The automatic design of multiobjective ant colony optimization algorithms,” IEEE Transactions on Evolutionary Computation, vol. 16, pp. 861–875, Dec 2012.
  * [24] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212–219, ACM, 1996.
  * [25] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschritte der Physik, vol. 46, no. 4-5, pp. 493–505, 1998\.
  * [26] C. Durr and P. Høyer, “A quantum algorithm for finding the minimum,” arXiv preprint quant-ph/9607014, 1996.
  * [27] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information.  Cambridge university press, 2010.
  * [28] C. Wang, H. Chen, and E. Jonckheere, “Quantum versus simulated annealing in wireless interference network optimization,” Scientific Reports, vol. 6, no. 25797, 2016.
  * [29] C. Wang, E. Jonckheere, and T. Brun, “Differential geometric treewidth estimation in adiabatic quantum computation,” Quantum Information Processing, vol. 15, pp. 3951–3966, Oct 2016.
  * [30] D. Alanis, P. Botsinis, Z. Babar, S. X. Ng, and L. Hanzo, “Non-dominated quantum iterative routing optimization for wireless multihop networks,” IEEE Access, vol. 3, pp. 1704–1728, 2015.
  * [31] C. Zalka, “Grover’s quantum searching algorithm is optimal,” Physical Review A, vol. 60, no. 4, p. 2746, 1999.
  * [32] D. Alanis, J. Hu, P. Botsinis, Z. Babar, S. X. Ng, and L. Hanzo, “Quantum-assisted joint multi-objective routing and load balancing for socially-aware networks,” IEEE Access, vol. 4, pp. 9993–10028, 2016.
  * [33] D. H. Lehmer, “Teaching combinatorial tricks to a computer,” in Proc. Sympos. Appl. Math. Combinatorial Analysis, vol. 10, pp. 179–193, 1960.
  * [34] R. Steele and L. Hanzo, Mobile radio communications: second and third generation cellular and WATM systems.  Wiley - IEEE, J. Wiley, 1999.
  * [35] L. Hanzo, S. X. Ng, W. Webb, and T. Keller, Quadrature amplitude modulation: From basics to adaptive trellis-coded, turbo-equalised and space-time coded OFDM, CDMA and MC-CDMA systems.  IEEE Press-John Wiley, 2004.
  * [36] S. Yang, X. Xu, D. Alanis, S. X. Ng, and L. Hanzo, “Is the low-complexity mobile relay aided FFR-DAS capable of outperforming the high-complexity CoMP?,” IEEE Transactions on Vehicular Technology, vol. 65, pp. 2154–2169, April 2016.
  * [37] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions: with formulas, graphs, and mathematical tables, vol. 55.  Courier Corporation, 1964.
  * [38] W. Zhang, M. F. Brejza, T. Wang, R. G. Maunder, and L. Hanzo, “Irregular trellis for the near-capacity unary error correction coding of symbol values from an infinite set,” IEEE Transactions on Communications, vol. 63, pp. 5073–5088, Dec 2015.
  * [39] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.